我怎样才能以相同的方式对两个 vector 进行排序，而条件只使用其中一个 vector ？
例如，假设我有两个相同大小的 vector :
vector<MyObject> vectorA;
vector<int> vectorB;
然后我使用一些比较函数对 vectorA 进行排序。该排序重新排序了 vectorA。如何将相同的重新排序应用于 vectorB？
一种选择是创建一个结构:
struct ExampleStruct {
MyObject mo;
int i;
};
然后对包含 vectorA 和 vectorB 内容的 vector 进行排序，压缩成单个 vector :
// vectorC[i] is vectorA[i] and vectorB[i] combined
vector<ExampleStruct> vectorC;
这似乎不是一个理想的解决方案。还有其他选择吗，尤其是在 C++11 中？
最佳答案
寻找排序排列
给定一个 std::vector<T>和 T 的比较's，如果您要使用此比较对 vector 进行排序，我们希望能够找到您将使用的排列。
template <typename T, typename Compare>
std::vector<std::size_t> sort_permutation(
const std::vector<T>& vec,
Compare& compare)
{
std::vector<std::size_t> p(vec.size());
std::iota(p.begin(), p.end(), 0);
std::sort(p.begin(), p.end(),
[&](std::size_t i, std::size_t j){ return compare(vec[i], vec[j]); });
return p;
}
应用排序排列
给定一个 std::vector<T>和一个排列，我们希望能够构建一个新的 std::vector<T>根据排列重新排序。
template <typename T>
std::vector<T> apply_permutation(
const std::vector<T>& vec,
const std::vector<std::size_t>& p)
{
std::vector<T> sorted_vec(vec.size());
std::transform(p.begin(), p.end(), sorted_vec.begin(),
[&](std::size_t i){ return vec[i]; });
return sorted_vec;
}
你当然可以修改apply_permutation改变你给它的 vector ，而不是返回一个新的排序拷贝。这种方法仍然是线性时间复杂度，并且在 vector 中每个项目使用一位。理论上，它仍然是线性空间复杂度；但是，在实践中，当 sizeof(T)很大，内存使用量的减少可能会非常显着。 (See details)
template <typename T>
void apply_permutation_in_place(
std::vector<T>& vec,
const std::vector<std::size_t>& p)
{
std::vector<bool> done(vec.size());
for (std::size_t i = 0; i < vec.size(); ++i)
{
if (done[i])
{
continue;
}
done[i] = true;
std::size_t prev_j = i;
std::size_t j = p[i];
while (i != j)
{
std::swap(vec[prev_j], vec[j]);
done[j] = true;
prev_j = j;
j = p[j];
}
}
}
示例
vector<MyObject> vectorA;
vector<int> vectorB;
auto p = sort_permutation(vectorA,
[](T const& a, T const& b){ /*some comparison*/ });
vectorA = apply_permutation(vectorA, p);
vectorB = apply_permutation(vectorB, p);
资源
关于c++ - 如何使用仅使用其中一个 vector 的标准以相同的方式对两个 vector 进行排序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17074324/