我有幾個std::vector，全部長度相同。我想對這些向量之一進行排序，並將相同的轉換應用於所有其他向量。有沒有一個乾淨的方式來做到這一點？ （最好使用STL或Boost）？一些載體保存了ints，其中一些保存了std::strings。如何通過不同的std :: vector的值對std :: vector進行排序？
僞代碼：
std::vector<int> Index = { 3, 1, 2 };
std::vector<std::string> Values = { "Third", "First", "Second" };
Transformation = sort(Index);
Index is now { 1, 2, 3};
... magic happens as Transformation is applied to Values ...
Values are now { "First", "Second", "Third" };
friol的方法很好，加上你的。首先，建立一個由數字1的矢量... ñ，從矢量支配排序順序的元素一起：
struct ordering {
bool operator()(pair<size_t, myiter> const& a, pair<size_t, myiter> const& b) {
return *(a.second) < *(b.second);
}
};
sort(order.begin(), order.end(), ordering());
typedef vector<int>::const_iterator myiter;
vector<pair<size_t, myiter> > order(Index.size());
size_t n = 0;
for (myiter it = Index.begin(); it != Index.end(); ++it, ++n)
order[n] = make_pair(n, it);
現在你可以使用自定義分類器進行排序這個數組
現在您已經捕獲order（更確切地說，在項目的第一個組件）內的重新排列順序。您現在可以使用此排序來排序其他向量。在同一時間內可能有一個非常聰明的就地變體，但直到有人提出它，這裏是一個不在位的變體。它使用order作爲每個元素的新索引的查找表。
template <typename T>
vector<T> sort_from_ref(
vector<T> const& in,
vector<pair<size_t, myiter> > const& reference
) {
vector<T> ret(in.size());
size_t const size = in.size();
for (size_t i = 0; i < size; ++i)
ret[i] = in[reference[i].first];
return ret;
}
是的，這是我的解決方案腦海中，我只是想知道是否有一些很好的方式將相同的轉換應用於多個矢量，但我猜不。 – 2008-10-27 15:19:20
只有一個粗略的解決方案在我腦海中：創建矢量這是所有其他載體的總和（結構的載體，如{3，第三，...} ，{1，First，...}），然後按照第一個字段對此向量進行排序，然後再次拆分結構。
在Boost或使用標準庫內可能有更好的解決方案。
我覺得你真的需要（但糾正我，如果我錯了）是訪問容器的元素以某種順序的方式。
與其重新排列我的原始集合，我會借用數據庫設計中的一個概念：保留一個索引，按照某個標準排序。這個索引是一個額外的間接性，提供了很大的靈活性。
這樣就有可能根據一個類的不同成員生成多個索引。
using namespace std;
template< typename Iterator, typename Comparator >
struct Index {
vector<Iterator> v;
Index(Iterator from, Iterator end, Comparator& c){
v.reserve(std::distance(from,end));
for(; from != end; ++from){
v.push_back(from); // no deref!
}
sort(v.begin(), v.end(), c);
}
};
template< typename Iterator, typename Comparator >
Index<Iterator,Comparator> index (Iterator from, Iterator end, Comparator& c){
return Index<Iterator,Comparator>(from,end,c);
}
struct mytype {
string name;
double number;
};
template< typename Iter >
struct NameLess : public binary_function<Iter, Iter, bool> {
bool operator()(const Iter& t1, const Iter& t2) const { return t1->name < t2->name; }
};
template< typename Iter >
struct NumLess : public binary_function<Iter, Iter, bool> {
bool operator()(const Iter& t1, const Iter& t2) const { return t1->number < t2->number; }
};
void indices() {
mytype v[] = { { "me" , 0.0 }
, { "you" , 1.0 }
, { "them" , -1.0 }
};
mytype* vend = v + _countof(v);
Index<mytype*, NameLess<mytype*> > byname(v, vend, NameLess<mytype*>());
Index<mytype*, NumLess <mytype*> > bynum (v, vend, NumLess <mytype*>());
assert(byname.v[0] == v+0);
assert(byname.v[1] == v+2);
assert(byname.v[2] == v+1);
assert(bynum.v[0] == v+2);
assert(bynum.v[1] == v+0);
assert(bynum.v[2] == v+1);
}
Boost提供此功能http://www.boost.org/doc/libs/1_36_0/libs/multi_index/doc/index.html – 2008-10-26 14:46:18
太棒了！ （我的工作場所禁止升壓:(） – xtofl 2008-10-26 19:27:40
將您的值寫入Boost Multi-Index container，然後迭代以按所需順序讀取值。如果你願意，你甚至可以將它們複製到另一個向量中。
typedef std::vector<int> int_vec_t;
typedef std::vector<std::string> str_vec_t;
typedef std::vector<size_t> index_vec_t;
class SequenceGen {
public:
SequenceGen (int start = 0) : current(start) { }
int operator()() { return current++; }
private:
int current;
};
class Comp{
int_vec_t& _v;
public:
Comp(int_vec_t& v) : _v(v) {}
bool operator()(size_t i, size_t j){
return _v[i] < _v[j];
}
};
index_vec_t indices(3);
std::generate(indices.begin(), indices.end(), SequenceGen(0));
//indices are {0, 1, 2}
int_vec_t Index = { 3, 1, 2 };
str_vec_t Values = { "Third", "First", "Second" };
std::sort(indices.begin(), indices.end(), Comp(Index));
//now indices are {1,2,0}
現在您可以使用「索引」向量來索引「值」向量。
您可以定義一個自定義的「外觀」迭代器，它可以在這裏執行您所需要的操作。它會將迭代器存儲到所有向量中，或者從第一個向量的偏移量中導出除了第一個向量之外的所有迭代器。棘手的部分是迭代器解引用的內容：想像boost :: tuple之類的東西，並巧妙地使用boost :: tie。（如果你想擴展這個想法，你可以使用模板遞歸地構建這些迭代器類型，但是你可能永遠不想寫下它的類型 - 所以你需要C++ 0x auto或者需要範圍的包裝函數來進行排序）
ltjax的回答是一個很好的做法 - 這是在提升的zip_iterator http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html
它一起打包到你提供給它的任何一個迭代器實際上元組實現。
然後，您可以根據元組中的迭代器值的任意組合創建自己的比較函數。對於這個問題，它只是你的元組中的第一個迭代器。
這種方法的一個很好的功能是，它允許你保持每個單獨的向量的內存連續（如果你使用的矢量，這就是你想要的）。您也不需要存儲單獨的索引向量。
xtofl的一個稍微緊湊的變體的答案，如果你只是想通過一個單一的keys載體遍歷所有的載體。創建一個置換矢量，並用它來索引你的其他矢量。
#include <boost/iterator/counting_iterator.hpp>
#include <vector>
#include <algorithm>
std::vector<double> keys = ...
std::vector<double> values = ...
std::vector<size_t> indices(boost::counting_iterator<size_t>(0u), boost::counting_iterator<size_t>(keys.size()));
std::sort(begin(indices), end(indices), [&](size_t lhs, size_t rhs) {
return keys[lhs] < keys[rhs];
});
// Now to iterate through the values array.
for (size_t i: indices)
{
std::cout << values[i] << std::endl;
}
這應該是Konrad的答案的附錄，因爲它是一種適用於矢量排序順序的就地變體方法。無論如何，因爲編輯將不會通過我會把它放在這裏
這是一個就地變體，具有稍高的時間複雜性是由於檢查布爾值的原始操作。額外的空間複雜性是一個向量，它可以是一個空間高效的編譯器相關實現。如果給定的訂單本身可以修改，則可以消除矢量的複雜性。
這是一個就地變體，其時間複雜度稍高，這是由於檢查布爾值的原始操作。額外的空間複雜性是一個向量，它可以是一個空間高效的編譯器相關實現。如果給定的訂單本身可以修改，則可以消除矢量的複雜性。這是算法正在做的一個例子。 如果順序爲3 0 4 1 2，則由位置索引指示的元素移動將爲3 ---> 0; 0 ---> 1; 1 ---> 3; 2 ---> 4; 4 ---> 2。
template<typename T>
struct applyOrderinPlace
{
void operator()(const vector<size_t>& order, vector<T>& vectoOrder)
{
vector<bool> indicator(order.size(),0);
size_t start = 0, cur = 0, next = order[cur];
size_t indx = 0;
T tmp;
while(indx < order.size())
{
//find unprocessed index
if(indicator[indx])
{
++indx;
continue;
}
start = indx;
cur = start;
next = order[cur];
tmp = vectoOrder[start];
while(next != start)
{
vectoOrder[cur] = vectoOrder[next];
indicator[cur] = true;
cur = next;
next = order[next];
}
vectoOrder[cur] = tmp;
indicator[cur] = true;
}
}
};
下面是使用索引映射的有序和無序的names之間將要用於匹配ages到有序names一個相對簡單的實現：
void ordered_pairs()
{
std::vector<std::string> names;
std::vector<int> ages;
// read input and populate the vectors
populate(names, ages);
// print input
print(names, ages);
// sort pairs
std::vector<std::string> sortedNames(names);
std::sort(sortedNames.begin(), sortedNames.end());
std::vector<int> indexMap;
for(unsigned int i = 0; i < sortedNames.size(); ++i)
{
for (unsigned int j = 0; j < names.size(); ++j)
{
if (sortedNames[i] == names[j])
{
indexMap.push_back(j);
break;
}
}
}
// use the index mapping to match the ages to the names
std::vector<int> sortedAges;
for(size_t i = 0; i < indexMap.size(); ++i)
{
sortedAges.push_back(ages[indexMap[i]]);
}
std::cout << "Ordered pairs:\n";
print(sortedNames, sortedAges);
}
爲了完整起見，這裏的功能populate()和print()：
void populate(std::vector<std::string>& n, std::vector<int>& a)
{
std::string prompt("Type name and age, separated by white space; 'q' to exit.\n>>");
std::string sentinel = "q";
while (true)
{
// read input
std::cout << prompt;
std::string input;
getline(std::cin, input);
// exit input loop
if (input == sentinel)
{
break;
}
std::stringstream ss(input);
// extract input
std::string name;
int age;
if (ss >> name >> age)
{
n.push_back(name);
a.push_back(age);
}
else
{
std::cout <<"Wrong input format!\n";
}
}
}
和：
void print(const std::vector<std::string>& n, const std::vector<int>& a)
{
if (n.size() != a.size())
{
std::cerr <<"Different number of names and ages!\n";
return;
}
for (unsigned int i = 0; i < n.size(); ++i)
{
std::cout <<'(' << n[i] << ", " << a[i] << ')' << "\n";
}
}
最後，main()變爲：
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
void ordered_pairs();
void populate(std::vector<std::string>&, std::vector<int>&);
void print(const std::vector<std::string>&, const std::vector<int>&);
//=======================================================================
int main()
{
std::cout << "\t\tSimple name - age sorting.\n";
ordered_pairs();
}
//=======================================================================
// Function Definitions...
**// C++ program to demonstrate sorting in vector
// of pair according to 2nd element of pair
#include <iostream>
#include<string>
#include<vector>
#include <algorithm>
using namespace std;
// Driver function to sort the vector elements
// by second element of pairs
bool sortbysec(const pair<char,char> &a,
const pair<int,int> &b)
{
return (a.second < b.second);
}
int main()
{
// declaring vector of pairs
vector< pair <char, int> > vect;
// Initialising 1st and 2nd element of pairs
// with array values
//int arr[] = {10, 20, 5, 40 };
//int arr1[] = {30, 60, 20, 50};
char arr[] = { ' a', 'b', 'c' };
int arr1[] = { 4, 7, 1 };
int n = sizeof(arr)/sizeof(arr[0]);
// Entering values in vector of pairs
for (int i=0; i<n; i++)
vect.push_back(make_pair(arr[i],arr1[i]));
// Printing the original vector(before sort())
cout << "The vector before sort operation is:\n" ;
for (int i=0; i<n; i++)
{
// "first" and "second" are used to access
// 1st and 2nd element of pair respectively
cout << vect[i].first << " "
<< vect[i].second << endl;
}
// Using sort() function to sort by 2nd element
// of pair
sort(vect.begin(), vect.end(), sortbysec);
// Printing the sorted vector(after using sort())
cout << "The vector after sort operation is:\n" ;
for (int i=0; i<n; i++)
{
// "first" and "second" are used to access
// 1st and 2nd element of pair respectively
cout << vect[i].first << " "
<< vect[i].second << endl;
}
getchar();
return 0;`enter code here`
}**
所以很多問我這個問題，沒有人想出了一個滿意的答覆。這裏是一個std :: sort幫助器，它可以同時對兩個向量進行排序，並考慮到只有一個向量的值。該解決方案是基於一個定製RadomIt（隨機迭代器），並直接作用於原始矢量數據，而臨時副本，結構重排或額外的指標：
我同意兩個答案，如果你打算可以多次執行此操作，不過您可以使用排序的數組從一開始就攜帶索引值，甚至可以創建一個類，該類可以載入您現在擁有多個向量中的所有數據，並一次對所有數據進行排序。 – 2008-10-25 11:12:32
我知道，這是2015年，但我覺得這是一個超優雅，易於實施的解決方案：http://stackoverflow.com/q/17554242/3093378它實際上與接受的答案類似，但是比較簡單的imo，所以我們可以實現一個`custom_sort`，它返回一個`std :: vector`的索引，類似於MATLAB。 –
vsoftco
2015-03-28 23:24:34
在這裏看到我對一個重複問題的答案：https://stackoverflow.com/questions/838384/reorder-vector-using-a-vector-of-indices/46370247#46370247 – cDc 2017-09-22 17:38:31