使用索引向量重新排序向量

Question

我想对向量中的项目重新排序，使用另一个向量指定顺序：

char   A[]     = { 'a', 'b', 'c' };
size_t ORDER[] = { 1, 0, 2 };

vector<char>   vA(A, A + sizeof(A) / sizeof(*A));
vector<size_t> vOrder(ORDER, ORDER + sizeof(ORDER) / sizeof(*ORDER));

reorder_naive(vA, vOrder);

// A is now { 'b', 'a', 'c' }

以下是需要复制向量的低效实现：

void reorder_naive(vector<char>& vA, const vector<size_t>& vOrder)  
{   
    assert(vA.size() == vOrder.size());  
    vector vCopy = vA; // Can we avoid this?  
    for(int i = 0; i < vOrder.size(); ++i)  
        vA[i] = vCopy[ vOrder[i] ];  
}  

是否有更有效的方法，例如使用 swap()？

Answer 1

该算法基于 chmike 的算法，但重新排序索引的向量是 const。 这个函数和他的11个都一致！ [0..10] 的排列。 复杂度为 O(N^2)，取 N 作为输入的大小，或者更准确地说，最大 轨道。

请参阅下文，了解修改输入的优化 O(N) 解决方案。

template< class T >
void reorder(vector<T> &v, vector<size_t> const &order )  {   
    for ( int s = 1, d; s < order.size(); ++ s ) {
        for ( d = order[s]; d < s; d = order[d] ) ;
        if ( d == s ) while ( d = order[d], d != s ) swap( v[s], v[d] );
    }
}

这是我投入更多精力的 STL 风格版本。 它大约快了 47%（也就是说，几乎是 [0..10] 的两倍！），因为它尽早完成所有交换，然后返回。 重新排序向量由多个轨道组成，每个轨道在到达其第一个成员时都会重新排序。 当最后几个元素不包含轨道时，速度会更快。

template< typename order_iterator, typename value_iterator >
void reorder( order_iterator order_begin, order_iterator order_end, value_iterator v )  {   
    typedef typename std::iterator_traits< value_iterator >::value_type value_t;
    typedef typename std::iterator_traits< order_iterator >::value_type index_t;
    typedef typename std::iterator_traits< order_iterator >::difference_type diff_t;
    
    diff_t remaining = order_end - 1 - order_begin;
    for ( index_t s = index_t(), d; remaining > 0; ++ s ) {
        for ( d = order_begin[s]; d > s; d = order_begin[d] ) ;
        if ( d == s ) {
            -- remaining;
            value_t temp = v[s];
            while ( d = order_begin[d], d != s ) {
                swap( temp, v[d] );
                -- remaining;
            }
            v[s] = temp;
        }
    }
}

---

最后，为了一劳永逸地回答这个问题，一个变体确实破坏了重新排序向量（用-1填充它）。 对于[0..10]的排列，它比之前的版本快了大约16%。 因为覆盖输入可以实现动态编程，所以它是 O(N)，对于某些序列较长的情况渐近更快。

template< typename order_iterator, typename value_iterator >
void reorder_destructive( order_iterator order_begin, order_iterator order_end, value_iterator v )  {
    typedef typename std::iterator_traits< value_iterator >::value_type value_t;
    typedef typename std::iterator_traits< order_iterator >::value_type index_t;
    typedef typename std::iterator_traits< order_iterator >::difference_type diff_t;
    
    diff_t remaining = order_end - 1 - order_begin;
    for ( index_t s = index_t(); remaining > 0; ++ s ) {
        index_t d = order_begin[s];
        if ( d == (diff_t) -1 ) continue;
        -- remaining;
        value_t temp = v[s];
        for ( index_t d2; d != s; d = d2 ) {
            swap( temp, v[d] );
            swap( order_begin[d], d2 = (diff_t) -1 );
            -- remaining;
        }
        v[s] = temp;
    }
}

Answer 2

向量的就地重新排序

警告：排序索引的语义存在歧义。 两者都在这里得到解答

将向量的元素移动到索引的位置

交互式版本此处。

#include <iostream>
#include <vector>
#include <assert.h>

using namespace std;

void REORDER(vector<double>& vA, vector<size_t>& vOrder)  
{   
    assert(vA.size() == vOrder.size());

    // for all elements to put in place
    for( int i = 0; i < vA.size() - 1; ++i )
    { 
        // while the element i is not yet in place 
        while( i != vOrder[i] )
        {
            // swap it with the element at its final place
            int alt = vOrder[i];
            swap( vA[i], vA[alt] );
            swap( vOrder[i], vOrder[alt] );
        }
    }
}

int main()
{
    std::vector<double> vec {7, 5, 9, 6};
    std::vector<size_t> inds {1, 3,  0, 2};
    REORDER(vec, inds);
    for (size_t vv = 0; vv < vec.size(); ++vv)
    {
        std::cout << vec[vv] << std::endl;
    }
    return 0;
}

输出

9
7
6
5

请注意，您可以保存一个测试，因为如果 n-1 个元素就位，那么最后的第 n 个元素肯定就位。

退出时 vA 和 vOrder 已正确排序。

该算法最多执行 n-1 次交换，因为每次交换都会将元素移动到其最终位置。 我们最多必须对 vOrder 进行 2N 次测试。

从索引的位置绘制向量元素

此处进行交互尝试。

#include <iostream>
#include <vector>
#include <assert.h>

template<typename T>
void reorder(std::vector<T>& vec, std::vector<size_t> vOrder)
{
    assert(vec.size() == vOrder.size());
            
    for( size_t vv = 0; vv < vec.size() - 1; ++vv )
    {
            if (vOrder[vv] == vv)
            {
                continue;
            }
            size_t oo;
            for(oo = vv + 1; oo < vOrder.size(); ++oo)
            {
                if (vOrder[oo] == vv)
                {
                    break;
                }
            }
            std::swap( vec[vv], vec[vOrder[vv]] );
            std::swap( vOrder[vv], vOrder[oo] );
    }
}

int main()
{
    std::vector<double> vec {7, 5, 9, 6};
    std::vector<size_t> inds {1, 3,  0, 2};
    reorder(vec, inds);
    for (size_t vv = 0; vv < vec.size(); ++vv)
    {
        std::cout << vec[vv] << std::endl;
    }
    return 0;
}

输出

5
6
7
9

Answer 3

在我看来，vOrder 包含一组按所需顺序排列的索引（例如按索引排序的输出）。 这里的代码示例遵循 vOrder 中的“循环”，其中遵循索引的子集（可以是 vOrder 的全部）将循环遍历该子集，最后回到子集的第一个索引处。

关于“循环”的 Wiki 文章

https://en.wikipedia.org/wiki/Cyclic_permutation

在下面的示例中，每个交换都至少将一个元素放置在其正确的位置。 此代码示例根据 vOrder 有效地对 vA 重新排序，同时“取消排序”或“取消排列”vOrder 回到其原始状态 (0 :: n-1)。 如果 vA 按顺序包含值 0 到 n-1，则重新排序后，vA 将位于 vOrder 开始的位置。

template <class T>
void reorder(vector<T>& vA, vector<size_t>& vOrder)  
{   
    assert(vA.size() == vOrder.size());

    // for all elements to put in place
    for( size_t i = 0; i < vA.size(); ++i )
    { 
        // while vOrder[i] is not yet in place 
        // every swap places at least one element in it's proper place
        while(       vOrder[i] !=   vOrder[vOrder[i]] )
        {
            swap( vA[vOrder[i]], vA[vOrder[vOrder[i]]] );
            swap(    vOrder[i],     vOrder[vOrder[i]] );
        }
    }
}

---

使用移动而不是交换也可以更有效地实现这一点。 需要一个临时对象来在移动过程中保存元素。 示例 C 代码，根据 I[] 中的索引对 A[] 重新排序，同时对 I[] 进行排序：

void reorder(int *A, int *I, int n)
{    
int i, j, k;
int tA;
    /* reorder A according to I */
    /* every move puts an element into place */
    /* time complexity is O(n) */
    for(i = 0; i < n; i++){
        if(i != I[i]){
            tA = A[i];
            j = i;
            while(i != (k = I[j])){
                A[j] = A[k];
                I[j] = j;
                j = k;
            }
            A[j] = tA;
            I[j] = j;
        }
    }
}

Answer 4

我认为，如果可以修改 ORDER 数组，那么对 ORDER 向量进行排序并在每个排序操作中交换相应值向量元素的实现就可以解决问题。

Answer 5

对现有答案的调查

您询问是否有“更有效的方法”。 但高效是什么意思？您的要求是什么？

Potatoswatter 的答案在O(N²)时间内工作，O(1) em> 额外的空间并且不会改变重新排序向量。

chmike 和 rcgldr 给出的答案使用 O(N) 时间和 O(1) 额外空间，但他们通过改变重新排序向量来实现这一点。

您的原始答案分配新空间，然后将数据复制到其中，而 Tim MB 建议使用移动语义。 然而，移动仍然需要一个地方来移动东西，并且像 std::string 这样的对象同时具有长度变量和指针。 换句话说，基于移动的解决方案需要为任何对象进行 O(N) 分配，并为新向量本身进行 O(1) 分配。 我在下面解释为什么这很重要。

保留重新排序向量

我们可能需要该重新排序向量！ 排序成本O(N log N)。 但是，如果您知道将以相同的方式对多个向量进行排序，例如在 数组结构中(SoA) 上下文中，您可以排序一次，然后重用结果。 这可以节省很多时间。

您可能还想对数据进行排序然后取消排序。 拥有重新排序向量可以让您做到这一点。 这里的一个用例是在 GPU 上执行基因组测序，其中通过批量处理相似长度的序列来获得最大速度效率。 我们不能依赖用户按此顺序提供序列，因此我们先排序然后取消排序。

那么，如果我们想要最好的结果呢：O(N) 处理，无需额外分配的成本，而且也不改变我们的排序向量（我们可能会在之后全部，想重复使用）？ 为了找到那个世界，我们需要问：

为什么额外的空间不好？

您可能不想分配额外空间有两个原因。

首先是你没有太多的工作空间。 这可能在两种情况下发生：您使用的是内存有限的嵌入式设备。 通常这意味着您正在处理小型数据集，因此 O(N²) 解决方案在这里可能没问题。 但当您使用非常的数据集时，也可能会发生这种情况。 在这种情况下，O(N²) 是不可接受的，您必须使用 O(N) 变异解决方案之一。

额外空间不好的另一个原因是分配成本很高。 对于较小的数据集，其成本可能高于实际计算。 因此，实现效率的一种方法是消除分配。

概述

当我们改变排序向量时，我们这样做是为了指示元素是否处于其排列位置。 我们可以使用位向量来指示相同的信息，而不是这样做。 然而，如果我们每次都分配位向量，那就会很昂贵。

相反，我们可以每次将位向量重置为零来清除位向量。 但是，每次使用函数都会产生额外的 O(N) 成本。

相反，我们可以将“版本”值存储在向量中，并在每次使用函数时递增该值。 这为我们提供了 O(1) 访问权限、O(1) 清除以及摊销分配成本。 这与持久数据结构类似。 缺点是，如果我们过于频繁地使用排序函数，则需要重置版本计数器，尽管这样做的 O(N) 成本是摊销的。

这就提出了一个问题：版本向量的最佳数据类型是什么？ 位向量可以最大化缓存利用率，但每次使用后都需要完全O(N)重置。 64 位数据类型可能永远不需要重置，但缓存利用率较差。 实验是解决这个问题的最好方法。

两种类型的排列

我们可以将排序向量视为具有两种含义：向前和向后。 从前向意义上讲，向量告诉我们元素去了哪里。 从向后的意义上讲，向量告诉我们元素来自哪里。 由于排序向量隐式是一个链表，因此后向意义需要 O(N) 额外空间，但是，我们可以再次摊销分配成本。 按顺序应用这两种感觉使我们回到原来的顺序。

性能

在我的“Intel(R) Xeon(R) E-2176M CPU @ 2.70GHz”上运行单线程时，以下代码对于长度为 32,767 个元素的序列每次重新排序大约需要 0.81 毫秒。

代码

完全注释了两种意义的代码并进行了测试：

#include <algorithm>
#include <cassert>
#include <random>
#include <stack>
#include <stdexcept>
#include <vector>

///@brief Reorder a vector by moving its elements to indices indicted by another 
///       vector. Takes O(N) time and O(N) space. Allocations are amoritzed.
///
///@param[in,out] values   Vector to be reordered
///@param[in]     ordering A permutation of the vector
///@param[in,out] visited  A black-box vector to be reused between calls and
///                        shared with with `backward_reorder()`
template<class ValueType, class OrderingType, class ProgressType>
void forward_reorder(
  std::vector<ValueType>          &values,
  const std::vector<OrderingType> &ordering,
  std::vector<ProgressType>       &visited
){
  if(ordering.size()!=values.size()){
    throw std::runtime_error("ordering and values must be the same size!");
  }

  //Size the visited vector appropriately. Since vectors don't shrink, this will
  //shortly become large enough to handle most of the inputs. The vector is 1
  //larger than necessary because the first element is special.
  if(visited.empty() || visited.size()-1<values.size());
    visited.resize(values.size()+1);

  //If the visitation indicator becomes too large, we reset everything. This is
  //O(N) expensive, but unlikely to occur in most use cases if an appropriate
  //data type is chosen for the visited vector. For instance, an unsigned 32-bit
  //integer provides ~4B uses before it needs to be reset. We subtract one below
  //to avoid having to think too much about off-by-one errors. Note that
  //choosing the biggest data type possible is not necessarily a good idea!
  //Smaller data types will have better cache utilization.
  if(visited.at(0)==std::numeric_limits<ProgressType>::max()-1)
    std::fill(visited.begin(), visited.end(), 0);

  //We increment the stored visited indicator and make a note of the result. Any
  //value in the visited vector less than `visited_indicator` has not been
  //visited.
  const auto visited_indicator = ++visited.at(0);

  //For doing an early exit if we get everything in place
  auto remaining = values.size();

  //For all elements that need to be placed
  for(size_t s=0;s<ordering.size() && remaining>0;s++){
    assert(visited[s+1]<=visited_indicator);

    //Ignore already-visited elements
    if(visited[s+1]==visited_indicator)
      continue;

    //Don't rearrange if we don't have to
    if(s==visited[s])
      continue;

    //Follow this cycle, putting elements in their places until we get back
    //around. Use move semantics for speed.
    auto temp = std::move(values[s]);
    auto i = s;
    for(;s!=(size_t)ordering[i];i=ordering[i],--remaining){
      std::swap(temp, values[ordering[i]]);
      visited[i+1] = visited_indicator;
    }
    std::swap(temp, values[s]);
    visited[i+1] = visited_indicator;
  }
}



///@brief Reorder a vector by moving its elements to indices indicted by another 
///       vector. Takes O(2N) time and O(2N) space. Allocations are amoritzed.
///
///@param[in,out] values   Vector to be reordered
///@param[in]     ordering A permutation of the vector
///@param[in,out] visited  A black-box vector to be reused between calls and
///                        shared with with `forward_reorder()`
template<class ValueType, class OrderingType, class ProgressType>
void backward_reorder(
  std::vector<ValueType>          &values,
  const std::vector<OrderingType> &ordering,
  std::vector<ProgressType>       &visited
){
  //The orderings form a linked list. We need O(N) memory to reverse a linked
  //list. We use `thread_local` so that the function is reentrant.
  thread_local std::stack<OrderingType> stack;

  if(ordering.size()!=values.size()){
    throw std::runtime_error("ordering and values must be the same size!");
  }

  //Size the visited vector appropriately. Since vectors don't shrink, this will
  //shortly become large enough to handle most of the inputs. The vector is 1
  //larger than necessary because the first element is special.
  if(visited.empty() || visited.size()-1<values.size());
    visited.resize(values.size()+1);

  //If the visitation indicator becomes too large, we reset everything. This is
  //O(N) expensive, but unlikely to occur in most use cases if an appropriate
  //data type is chosen for the visited vector. For instance, an unsigned 32-bit
  //integer provides ~4B uses before it needs to be reset. We subtract one below
  //to avoid having to think too much about off-by-one errors. Note that
  //choosing the biggest data type possible is not necessarily a good idea!
  //Smaller data types will have better cache utilization.
  if(visited.at(0)==std::numeric_limits<ProgressType>::max()-1)
    std::fill(visited.begin(), visited.end(), 0);

  //We increment the stored visited indicator and make a note of the result. Any
  //value in the visited vector less than `visited_indicator` has not been
  //visited.  
  const auto visited_indicator = ++visited.at(0);

  //For doing an early exit if we get everything in place
  auto remaining = values.size();

  //For all elements that need to be placed
  for(size_t s=0;s<ordering.size() && remaining>0;s++){
    assert(visited[s+1]<=visited_indicator);

    //Ignore already-visited elements
    if(visited[s+1]==visited_indicator)
      continue;

    //Don't rearrange if we don't have to
    if(s==visited[s])
      continue;

    //The orderings form a linked list. We need to follow that list to its end
    //in order to reverse it.
    stack.emplace(s);
    for(auto i=s;s!=(size_t)ordering[i];i=ordering[i]){
      stack.emplace(ordering[i]);
    }

    //Now we follow the linked list in reverse to its beginning, putting
    //elements in their places. Use move semantics for speed.
    auto temp = std::move(values[s]);
    while(!stack.empty()){
      std::swap(temp, values[stack.top()]);
      visited[stack.top()+1] = visited_indicator;
      stack.pop();
      --remaining;
    }
    visited[s+1] = visited_indicator;
  }
}



int main(){
  std::mt19937 gen;
  std::uniform_int_distribution<short> value_dist(0,std::numeric_limits<short>::max());
  std::uniform_int_distribution<short> len_dist  (0,std::numeric_limits<short>::max());
  std::vector<short> data;
  std::vector<short> ordering;
  std::vector<short> original;

  std::vector<size_t> progress;

  for(int i=0;i<1000;i++){
    const int len = len_dist(gen);
    data.clear();
    ordering.clear();
    for(int i=0;i<len;i++){
      data.push_back(value_dist(gen));
      ordering.push_back(i);
    }

    original = data;

    std::shuffle(ordering.begin(), ordering.end(), gen);

    forward_reorder(data, ordering, progress);

    assert(original!=data);

    backward_reorder(data, ordering, progress);

    assert(original==data);
  }  
}

Answer 6

永远不要过早优化。 测量并确定需要优化的位置和内容。 您可能会以复杂的代码结束，这些代码在性能不是问题的许多地方难以维护并且容易出现错误。

话虽如此，不要过早悲观。 无需更改代码，您可以删除一半的副本：

    template <typename T>
    void reorder( std::vector<T> & data, std::vector<std::size_t> const & order )
    {
       std::vector<T> tmp;         // create an empty vector
       tmp.reserve( data.size() ); // ensure memory and avoid moves in the vector
       for ( std::size_t i = 0; i < order.size(); ++i ) {
          tmp.push_back( data[order[i]] );
       }
       data.swap( tmp );          // swap vector contents
    }

此代码创建一个空（足够大）的向量，其中按顺序执行单个副本。 最后，交换有序向量和原始向量。 这会减少副本，但仍然需要额外的内存。

如果您想就地执行移动，一个简单的算法可能是：

template <typename T>
void reorder( std::vector<T> & data, std::vector<std::size_t> const & order )
{
   for ( std::size_t i = 0; i < order.size(); ++i ) {
      std::size_t original = order[i];
      while ( i < original )  {
         original = order[original];
      }
      std::swap( data[i], data[original] );
   }
}

应检查和调试此代码。 简单来说，算法每一步都将元素定位在第 i 个位置。 首先，我们确定该位置的原始元素现在放置在数据向量中的位置。 如果原始位置已经被算法触及（它在第 i 个位置之前），则原始元素被交换到 order[original] 位置。 话又说回来，该元素可能已经被移动了...

该算法的整数运算数量大约为 O(N^2)，因此理论上与初始 O(N) 算法相比，性能时间更差。 但如果 N^2 交换操作（最坏情况）的成本低于 N 复制操作或者您确实受到内存占用的限制，它可以进行补偿。

Answer 7

在 O(1) 空间要求下进行重新排序是一项有趣的智力练习，但在 99.9% 的情况下，更简单的答案将满足您的需求：

void permute(vector<T>& values, const vector<size_t>& indices)  
{   
    vector<T> out;
    out.reserve(indices.size());
    for(size_t index: indices)
    {
        assert(0 <= index && index < values.size());
        out.push_back(std::move(values[index]));
    }
    values = std::move(out);
}

除了内存要求之外，我认为速度较慢的唯一方法是由于out 的内存与 values 和 indices 位于不同的缓存页面中。

Answer 8

我想你可以递归地完成它 - 像这样（未经检查，但它给出了想法）：

// Recursive function
template<typename T>
void REORDER(int oldPosition, vector<T>& vA, 
             const vector<int>& vecNewOrder, vector<bool>& vecVisited)
{
    // Keep a record of the value currently in that position,
    // as well as the position we're moving it to.
    // But don't move it yet, or we'll overwrite whatever's at the next
    // position. Instead, we first move what's at the next position.
    // To guard against loops, we look at vecVisited, and set it to true
    // once we've visited a position.
    T oldVal = vA[oldPosition];
    int newPos = vecNewOrder[oldPosition];
    if (vecVisited[oldPosition])
    {
        // We've hit a loop. Set it and return.
        vA[newPosition] = oldVal;
        return;
    }
    // Guard against loops:
    vecVisited[oldPosition] = true;

    // Recursively re-order the next item in the sequence.
    REORDER(newPos, vA, vecNewOrder, vecVisited);

    // And, after we've set this new value, 
    vA[newPosition] = oldVal;
}

// The "main" function
template<typename T>
void REORDER(vector<T>& vA, const vector<int>& newOrder)
{
    // Initialise vecVisited with false values
    vector<bool> vecVisited(vA.size(), false);

    for (int x = 0; x < vA.size(); x++)
    {
        REORDER(x, vA, newOrder, vecVisited);
    }
}

当然，你确实有 vecVisited 的开销。 有人对这种方法有什么想法吗？

Answer 9

你的代码被破坏了。 您无法分配给 vA 并且需要使用模板参数。

vector<char> REORDER(const vector<char>& vA, const vector<size_t>& vOrder)  
{   
    assert(vA.size() == vOrder.size());  
    vector<char> vCopy(vA.size()); 
    for(int i = 0; i < vOrder.size(); ++i)  
        vCopy[i] = vA[ vOrder[i] ];  
    return vA;
} 

上面的效率稍微高一些。

Answer 10

标题和问题并不清楚是否应该使用与排序 vOrder 相同的步骤对向量进行排序，或者 vOrder 是否已包含所需顺序的索引。
第一种解释已经有了令人满意的答案（参见chmike和Potatoswatter），我补充一些关于后者的想法。
如果对象 T 的创建和/或复制成本相关

template <typename T>
void reorder( std::vector<T> & data, std::vector<std::size_t> & order )
{
 std::size_t i,j,k;
  for(i = 0; i < order.size() - 1; ++i) {
    j = order[i];
    if(j != i) {
      for(k = i + 1; order[k] != i; ++k);
      std::swap(order[i],order[k]);
      std::swap(data[i],data[j]);
    }
  }
}

如果对象的创建成本很小并且内存不是问题（请参阅 dribeas）：

template <typename T>
void reorder( std::vector<T> & data, std::vector<std::size_t> const & order )
{
 std::vector<T> tmp;         // create an empty vector
 tmp.reserve( data.size() ); // ensure memory and avoid moves in the vector
 for ( std::size_t i = 0; i < order.size(); ++i ) {
  tmp.push_back( data[order[i]] );
 }
 data.swap( tmp );          // swap vector contents
}

请注意，dribeas 答案中的两段代码执行不同的操作。

Answer 11

我试图使用 @Potatoswatter 的解决方案将多个向量按第三个排序，但对犰狳的 sort_index 的索引向量输出使用上述函数的输出感到非常困惑。 要将 sort_index（下面的 arma_inds 向量）的向量输出切换为可与 @Potatoswatter 的解决方案（下面的 new_inds）一起使用的向量输出，您可以执行以下操作：

vector<int> new_inds(arma_inds.size());
for (int i = 0; i < new_inds.size(); i++) new_inds[arma_inds[i]] = i;

Answer 12

我提出了这个解决方案，其空间复杂度为O(max_val - min_val + 1)，但它可以与std::sort集成code> 并受益于 std::sort 的 O(n log n) 不错的时间复杂度。

std::vector<int32_t> dense_vec = {1, 2, 3};
std::vector<int32_t> order = {1, 0, 2};

int32_t max_val = *std::max_element(dense_vec.begin(), dense_vec.end());
std::vector<int32_t> sparse_vec(max_val + 1);

int32_t i = 0;
for(int32_t j: dense_vec)
{
    sparse_vec[j] = order[i];
    i++;
}

std::sort(dense_vec.begin(), dense_vec.end(),
    [&sparse_vec](int32_t i1, int32_t i2) {return sparse_vec[i1] < sparse_vec[i2];});

编写此代码时做出以下假设：

• 向量值从零开始。
• 向量不包含重复值。
• 为了使用 std::sort 我们有足够的内存可以牺牲

Answer 13

这应该避免复制向量：

void REORDER(vector<char>& vA, const vector<size_t>& vOrder)  
{   
    assert(vA.size() == vOrder.size()); 
    for(int i = 0; i < vOrder.size(); ++i)
        if (i < vOrder[i])
            swap(vA[i], vA[vOrder[i]]);
}