这里的主要问题是
std::sort
算法不能同时对多个向量进行操作。
std::vector<int> v1
和a
std::vector<char> v2
v1
为了解决这个问题,我基本上看到了三种可能的解决方案,所有这些解决方案都可以推广到任意数量的向量:
1) 将所有数据放在一个向量中。
struct
Data
,保留每个数据向量的条目。
struct Data
{
int d1;
char d2;
// extend here for more vectors
};
std::vector<Data>
从原始向量中填充:
std::vector<Data> d(v1.size());
for(std::size_t i = 0; i < d.size(); ++i)
{
d[i].d1 = v1[i];
d[i].d2 = v2[i];
// extend here for more vectors
}
由于现在所有内容都存储在单个向量中,因此可以使用
标准::排序
把它整理好。因为我们希望根据第一个条目进行排序(
d1
std::sort(d.begin(), d.end(),
[](const Data& l, const Data& r) { return l.d1 < r.d1; });
然后,将所有数据排序到
d
d
std::transform(d.begin(), d.end(), v1.begin(),
[](const Data& e) { return e.d1; });
std::transform(d.begin(), d.end(), v2.begin(),
[](const Data& e) { return e.d2; });
// extend here for more vectors
2) 使用第一个
vector
矢量
首先,将附加到第一个
他们当前的位置。然后使用
标准::排序
template<typename T>
std::vector<std::size_t> computeSortIndices(const std::vector<T>& v)
{
std::vector<std::pair<T, std::size_t>> d(v.size());
for(std::size_t i = 0; i < v.size(); ++i)
d[i] = std::make_pair(v[i], i);
std::sort(d.begin(), d.end(),
[](const std::pair<T, std::size_t>& l,
const std::pair<T, std::size_t>& r)
{
return l.first < r.first;
});
std::vector<std::size_t> indices(v.size());
std::transform(d.begin(), d.end(), indices.begin(),
[](const std::pair<T, std::size_t>& p) { return p.second; });
return indices;
}
在结果索引中说
矢量
位置处的条目
0
8
,那么这告诉您
矢量
必须转到排序中第一个位置的条目
s是那些在位置上的
8.
然后使用此信息对所有
vectors
:
template<typename T>
void sortByIndices(std::vector<T>& v,
const std::vector<std::size_t>& indices)
{
assert(v.size() == indices.size());
std::vector<T> result(v.size());
for(std::size_t i = 0; i < indices.size(); ++i)
result[i] = v[indices[i]];
v = std::move(result);
}
矢量
然后可以按如下方式排序:
const auto indices = computeSortIndices(v1);
sortByIndices(v1, indices);
sortByIndices(v2, indices);
// extend here for more vectors
通过提取排序后的
从…里面
computeSortIndices
sortByIndices
3) 实现您自己的排序功能,可以对多个
矢量
矢量
s取决于第一个中的值。
合并排序算法的核心由
multiMergeSortRec
该函数将所有向量拆分为第一部分和第二部分,递归地对两部分进行排序,并将结果合并在一起。如果需要更多详细信息,请在web上搜索有关合并排序的完整解释。
template<typename T, typename... Ts>
void multiMergeSortRec(
std::size_t b, std::size_t e,
std::vector<T>& v, std::vector<Ts>&... vs)
{
const std::size_t dist = e - b;
if(dist <= 1)
return;
std::size_t m = b + (dist / static_cast<std::size_t>(2));
// split in half and recursively sort both parts
multiMergeSortRec(b, m, v, vs...);
multiMergeSortRec(m, e, v, vs...);
// merge both sorted parts
while(b < m)
{
if(v[b] <= v[m])
++b;
else
{
++m;
rotateAll(b, m, v, vs...);
if(m == e)
break;
}
}
}
template<typename T, typename... Ts>
void multiMergeSort(std::vector<T>& v, std::vector<Ts>&... vs)
{
// TODO: check that all vectors have same length
if(v.size() < 2)
return ;
multiMergeSortRec<T, Ts...>(0, v.size(), v, vs...);
}
为了在适当位置运行,部分
s必须旋转。这是由
rotateAll
矢量
通过递归处理可变参数包。
void rotateAll(std::size_t, std::size_t)
{
}
template<typename T, typename... Ts>
void rotateAll(std::size_t b, std::size_t e,
std::vector<T>& v, std::vector<Ts>&... vs)
{
std::rotate(v.begin() + b, v.begin() + e - 1, v.begin() + e);
rotateAll(b, e, vs...);
}
注意,的递归调用
很可能被每个优化编译器内联,因此该函数仅适用于
std::rotate
到所有向量。如果保留原处并合并到其他位置,则可以避免旋转向量的部分
矢量
。我想强调的是,这既不是一个优化的,也不是一个经过充分测试的合并排序实现。它应该作为一个草图,因为你真的不想在处理大向量时使用冒泡排序。
-
1) 更容易实现,因为它依赖于现有的(高度优化和测试)
实施
-
1) 需要将所有数据复制到新的
并且可能(取决于您的用例)将其全部复制回来。
-
在1)如果需要附加额外的,则必须扩展多个位置
矢量
-
2)的实现工作一般(大于1,但小于3且更容易),但它依赖于优化和测试
标准::排序
.
-
矢量
.也许有一个现成的替代方案,但我现在想不出(至少是一个简单的方案)。
-
s
-
对于3)您需要自己实现排序,这使得正确操作更加困难。
-
3) 不需要复制所有数据。可以进一步优化实现,并可以调整以提高性能(不合适)或减少内存消耗(合适)。
-
3) 可以处理其他
s没有任何变化。只需调用
multiMergeSort
具有一个或多个附加参数。
-
矢量
std::vector<std::vector<>>
方法
矢量
因此,如果您真的需要最佳性能(和/或内存使用),您需要进行测量。
here
.
