现有答案的调查
您问是否有“更有效的方法”。但是，您所说的有效率是什么意思，您的要求是什么？
Potatoswatter的答案在O(N²)时间内使用O(1)附加空间，并且不改变重新排序向量。
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(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>
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!");
}
if(visited.empty() || visited.size()-1<values.size());
visited.resize(values.size()+1);
if(visited.at(0)==std::numeric_limits<ProgressType>::max()-1)
std::fill(visited.begin(), visited.end(), 0);
const auto visited_indicator = ++visited.at(0);
auto remaining = values.size();
for(size_t s=0;s<ordering.size() && remaining>0;s++){
assert(visited[s+1]<=visited_indicator);
if(visited[s+1]==visited_indicator)
continue;
if(s==visited[s])
continue;
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;
}
}
template<class ValueType, class OrderingType, class ProgressType>
void backward_reorder(
std::vector<ValueType> &values,
const std::vector<OrderingType> &ordering,
std::vector<ProgressType> &visited
){
thread_local std::stack<OrderingType> stack;
if(ordering.size()!=values.size()){
throw std::runtime_error("ordering and values must be the same size!");
}
if(visited.empty() || visited.size()-1<values.size());
visited.resize(values.size()+1);
if(visited.at(0)==std::numeric_limits<ProgressType>::max()-1)
std::fill(visited.begin(), visited.end(), 0);
const auto visited_indicator = ++visited.at(0);
auto remaining = values.size();
for(size_t s=0;s<ordering.size() && remaining>0;s++){
assert(visited[s+1]<=visited_indicator);
if(visited[s+1]==visited_indicator)
continue;
if(s==visited[s])
continue;
stack.emplace(s);
for(auto i=s;s!=(size_t)ordering[i];i=ordering[i]){
stack.emplace(ordering[i]);
}
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);
}
}
#define可以这样做。 - GManNickG