我最好的例子是，我想根据他们的分数对名字进行排序。
vector <string> Names {"Karl", "Martin", "Paul", "Jennie"};
vector <int> Score{45, 5, 14, 24};
所以如果我将得分排序为{5，14，24，45}，则名称也应根据其得分进行排序。
7个回答
40
将名称和分数合并为单个结构的另一种选择是创建索引列表并对其进行排序：
std::vector<int> indices(Names.size());
std::iota(indices.begin(), indices.end(), 0);
std::sort(indices.begin(), indices.end(),
[&](int A, int B) -> bool {
return Score[A] < Score[B];
});
现在可以使用 indices 来按照所需的排序顺序索引 Names 和 Scores。
- wcochran
17
正如其他回答中已经建议的那样：将每个人的名字和分数组合起来可能是最简单的解决方案。
一般来说，这可以通过所谓的“zip”操作实现：将两个向量合并成一对向量 - 以及相应的“unzip”操作。
通用地实现，代码如下：
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <iterator>
// Fill the zipped vector with pairs consisting of the
// corresponding elements of a and b. (This assumes
// that the vectors have equal length)
template <typename A, typename B>
void zip(
const std::vector<A> &a,
const std::vector<B> &b,
std::vector<std::pair<A,B>> &zipped)
{
for(size_t i=0; i<a.size(); ++i)
{
zipped.push_back(std::make_pair(a[i], b[i]));
}
}
// Write the first and second element of the pairs in
// the given zipped vector into a and b. (This assumes
// that the vectors have equal length)
template <typename A, typename B>
void unzip(
const std::vector<std::pair<A, B>> &zipped,
std::vector<A> &a,
std::vector<B> &b)
{
for(size_t i=0; i<a.size(); i++)
{
a[i] = zipped[i].first;
b[i] = zipped[i].second;
}
}
int main(int argc, char* argv[])
{
std::vector<std::string> names {"Karl", "Martin", "Paul", "Jennie"};
std::vector<int> score {45, 5, 14, 24};
// Zip the vectors together
std::vector<std::pair<std::string,int>> zipped;
zip(names, score, zipped);
// Sort the vector of pairs
std::sort(std::begin(zipped), std::end(zipped),
[&](const auto& a, const auto& b)
{
return a.second > b.second;
});
// Write the sorted pairs back to the original vectors
unzip(zipped, names, score);
for(size_t i=0; i<names.size(); i++)
{
std::cout << names[i] << " : " << score[i] << std::endl;
}
return 0;
}
- Marco13
2
1考虑到
std::pair 已经定义了按字典序比较的 operator<，你可以使用 std::pair<B, A> 代替 std::pair<A, B> 来节省代码行数。这样你就可以写成 zip(score, names, zipped) 而不是 zip(names, score, zipped)，并且可以使用 std::sort(std::begin(zipped), std::end(zipped)) 而无需定义一个 lambda 函数进行比较。 - Jasha1@Jasha 说得好，但只适用于这种特定情况。对于一个不可比较的“first”，或者进行降序排序，仍需要自己编写比较器，因此在这个（本应该是通用的）答案中包含这一点可能并不是错误的。 - Marco13
9
最好的方法是创建一个结构体，将姓名和分数组合在一起并使用一个向量存储。
struct Person
{
std::string Name;
int Score;
};
然后您可以声明您的向量：
std::vector<Person> people{ { "Karl", 45 }, { "Martin", 5 }, { "Paul", 14 } };
使用来自于<algorithm>的std::sort函数进行排序非常容易：
std::sort(people.begin(), people.end(),
[](const auto& i, const auto& j) { return i.Score < j.Score; } );
如果你想按降序排序，可以改变 lambda：
std::sort(people.begin(), people.end(),
[](const auto& i, const auto& j) { return i.Score > j.Score; } );
- DeiDei
2
为什么结构体的名称是复数形式？它应该是Person，而向量应该命名为people。 - saloomi2012
因为现在已经太晚了，我已经无法清晰地思考了。所有问题都已经解决了。 - DeiDei
5
有很多人问了这个问题，但没有人给出令人满意的答案。这里提供了一个 std::sort 辅助程序，可以同时对两个向量进行排序，只考虑其中一个向量的值。该解决方案基于自定义的 RadomIt（随机迭代器），直接操作原始向量数据，无需临时副本、结构重排或附加索引：
namespace std {
namespace sort_helper {
template <typename _Data, typename _Order>
struct value_reference_t;
template <typename _Data, typename _Order>
struct value_t {
_Data data;
_Order val;
inline value_t(_Data _data, _Order _val) : data(_data), val(_val) {}
inline value_t(const value_reference_t<_Data,_Order>& rhs);
};
template <typename _Data, typename _Order>
struct value_reference_t {
_Data* pdata;
_Order* pval;
value_reference_t(_Data* _itData, _Order* _itVal) : pdata(_itData), pval(_itVal) {}
inline value_reference_t& operator = (const value_reference_t& rhs) { *pdata = *rhs.pdata; *pval = *rhs.pval; return *this; }
inline value_reference_t& operator = (const value_t<_Data,_Order>& rhs) { *pdata = rhs.data; *pval = rhs.val; return *this; }
inline bool operator < (const value_reference_t& rhs) { return *pval < *rhs.pval; }
};
template <typename _Data, typename _Order>
struct value_iterator_t :
iterator< random_access_iterator_tag, value_t<_Data,_Order>, ptrdiff_t, value_t<_Data,_Order>*, value_reference_t<_Data,_Order> >
{
_Data* itData;
_Order* itVal;
value_iterator_t(_Data* _itData, _Order* _itVal) : itData(_itData), itVal(_itVal) {}
inline ptrdiff_t operator - (const value_iterator_t& rhs) const { return itVal - rhs.itVal; }
inline value_iterator_t operator + (ptrdiff_t off) const { return value_iterator_t(itData + off, itVal + off); }
inline value_iterator_t operator - (ptrdiff_t off) const { return value_iterator_t(itData - off, itVal - off); }
inline value_iterator_t& operator ++ () { ++itData; ++itVal; return *this; }
inline value_iterator_t& operator -- () { --itData; --itVal; return *this; }
inline value_iterator_t operator ++ (int) { return value_iterator_t(itData++, itVal++); }
inline value_iterator_t operator -- (int) { return value_iterator_t(itData--, itVal--); }
inline value_t<_Data,_Order> operator * () const { return value_t<_Data,_Order>(*itData, *itVal); }
inline value_reference_t<_Data,_Order> operator * () { return value_reference_t<_Data,_Order>(itData, itVal); }
inline bool operator < (const value_iterator_t& rhs) const { return itVal < rhs.itVal; }
inline bool operator == (const value_iterator_t& rhs) const { return itVal == rhs.itVal; }
inline bool operator != (const value_iterator_t& rhs) const { return itVal != rhs.itVal; }
};
template <typename _Data, typename _Order>
inline value_t<_Data,_Order>::value_t(const value_reference_t<_Data,_Order>& rhs)
: data(*rhs.pdata), val(*rhs.pval) {}
template <typename _Data, typename _Order>
bool operator < (const value_t<_Data,_Order>& lhs, const value_reference_t<_Data,_Order>& rhs) {
return lhs.val < *rhs.pval; }
template <typename _Data, typename _Order>
bool operator < (const value_reference_t<_Data,_Order>& lhs, const value_t<_Data,_Order>& rhs) {
return *lhs.pval < rhs.val; }
template <typename _Data, typename _Order>
void swap(value_reference_t<_Data,_Order> lhs, value_reference_t<_Data,_Order> rhs) {
std::swap(*lhs.pdata, *rhs.pdata);
std::swap(*lhs.pval, *rhs.pval); }
} // namespace sort_helper
} // namespace std
以下是一个使用示例，它基于年龄值对姓名和年龄进行排序，并使用标准的std::sort函数：
char* Names[] = { "Karl", "Paul", "Martin", "Jennie" };
int Age[] = { 45, 14, 5, 24 };
typedef std::sort_helper::value_iterator_t<char*,int> IndexIt;
std::sort(IndexIt(Names, Age), IndexIt(Names+4, Age+4));
排序为：
{ "Martin", "Paul", "Jennie", "Karl" };
{ 5, 14, 24, 45 };
代码已在 Visual Studio 2017 和 GCC 5.4.0 上进行测试。
- cDc
3
很不幸，即使在我修复了
value_iterator_t 中的 typedef 使用后，它似乎仍然无法在 GCC 下工作。此外，您不应该使用以 _[A-Z] 开头的名称或将东西放入 namespace std中。这两者都会导致代码行为不确定。 - HolyBlackCat1谢谢你发现了这个问题，我已经修复了，并且现在可以在GCC上运行。 - cDc
这在VS 16.8中停止工作了。以下是问题和我的建议修复方法：https://dev59.com/uqv2oIgBc1ULPQZFRhLD#69767844 - stfx
5
如果您不能将数据合并为成对的向量或同时包含两者的结构体，则可以创建一个迭代器向量，或从0到size-1的索引。然后使用自定义比较器对其进行排序。最后，创建一个新向量，使用迭代器或索引填充它。
template<class T1, class A1, class T2, class A2>
std::vector<T1, A1> sort_by(
std::vector<T1,A1> const& vin, std::vector<T2,A2> const& keys
){
std::vector<std::size_t> is;
is.reserve(vin.size());
for (auto&& unused:keys)
is.push_back(is.size());
std::sort(begin(is),end(is),[&](std::size_t l, std::size_t r){
return keys[l]<keys[r];
});
std::vector<T1, A1> r;
r.reserve(vin.size());
for(std::size_t i:is)
r.push_back(vin[i]);
return r;
}
- Yakk - Adam Nevraumont
2
如果您能展示一个例子，我将不胜感激。 - Krillex
1
std::iota 被冷落了吗？ - Barry3
您可以通过将姓名和分数存储在一个数据结构中（例如std::vector<std::pair<std::string,int>>）来完成此操作，然后按以下方式进行排序：
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
//...
std::vector<std::pair<std::string, int>> names_scores_vec;
// ... populate names_scores_vec...
// lambda for sorting, change to > for descending order
auto sort_by_scores = [](const std::pair<string,int>& _lhs,
const std::pair<string,int>& _rhs) { return _lhs.second < _rhs.second; };
std::sort(names_scores_vec.begin(), names_scores_vec.end(), sort_by_scores);
如果希望重复使用键（即允许重复名称），可以使用像std::map或std::multimap之类的存储。
- sjrowlinson
1
这个能否通过自定义迭代器类型来实现？
编辑：
我想，最简单的形式是：根据第一个向量对一对向量进行排序 - 拥有一个迭代器，其函数如解引用、下标、成员访问、相等和排序比较将调用第一个迭代器上对应的函数，所有其他函数（复制、算术、交换等）作用于两个迭代器。
template <typename Driver, typename Passenger>
struct duo_iterator { . . . };
template <typename D, typename P>
auto make_duo_iterator(D d, P p) -> duo_iterator<D, P> { . . . }
sort(make_duo_iterator(begin(v1), begin(v2)),
make_duo_iterator(end(v1), end(v2)));
迭代器可以扩展为
multi_iterator，以适用于任何重新排序算法，指向任意数量的额外附加序列。这可能是一个有趣的小项目。或者类似的东西已经存在于Boost或其他地方。
编辑2：
忘记上面的内容吧。
Eric Niebler的Range-v3库有一个
view::zip包装器，"给定N个范围，返回一个新的范围，其中第M个元素是调用所有N个范围的第M个元素的make_tuple的结果。"使用对元组第一个元素进行谓词排序可能会起到作用。
- Garp
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
std::vector<std::pair<int,std::string>>呢？ - πάντα ῥεῖstd::vector<size_t>进行排序，提供自定义比较器comp(i, j) := Score[i] < Score[j]。 - quant_dev