別のstd :: vectorの値でstd :: vectorをソートするにはどうすればよいですか?
質問
複数の std :: vector
があり、すべて同じ長さです。これらのベクトルのいずれかをソートし、他のすべてのベクトルに同じ変換を適用したいと思います。これを行うきちんとした方法はありますか? (できればSTLまたはBoostを使用)?いくつかのベクターは int
sを保持し、一部は std :: string
sを保持します。
擬似コード:
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&#8230; n で構成されるベクトルを、並べ替え順序を指示するベクトルの要素とともに構築します。
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);
カスタムソーターを使用してこの配列をソートできるようになりました:
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());
order
内の(より正確には、アイテムの最初のコンポーネント内の)再配置の順序をキャプチャしました。これで、この順序付けを使用して他のベクトルをソートできます。おそらく非常に巧妙なインプレースバリアントが同時に実行されますが、他の誰かがそれを思い付くまで、インプレースではないバリアントが1つあります。各要素の新しいインデックスのルックアップテーブルとして 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;
}
他のヒント
Boost Multi-Indexコンテナに値を入力しますを繰り返して、必要な順序で値を読み取ります。必要に応じて、別のベクターにコピーすることもできます。
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}
「インデックス」を使用できるようになりました。 「値」にインデックスを付けるベクトルベクトル。
大まかな解決策は1つだけです。他のすべてのベクトルの合計であるベクトルを作成します({3、Third、...}、{1、First、...}などの構造のベクトル)次に、このベクトルを最初のフィールドで並べ替えてから、構造を再度分割します。
おそらく、Boost内または標準ライブラリを使用してより良いソリューションがあります。
カスタムの「ファサード」をおそらく定義できます。ここで必要なことを行うイテレータ。すべてのベクトルのイテレータを保存するか、最初のベクトルのオフセットから最初のベクトル以外のすべてのイテレータを派生させます。トリッキーな部分は、イテレータが参照するものです:boost :: tupleのようなものを考え、boost :: tieを巧みに使用します。 (このアイデアを拡張したい場合は、テンプレートを使用してこれらのイテレータ型を再帰的に構築できますが、おそらくその型を書き留めたくないでしょう-したがって、c ++ 0x autoまたは範囲を取るソートのラッパー関数が必要です)
あなたが本当に必要とする のは(間違っているなら私を修正する)は、コンテナの要素に何らかの順序でアクセスする方法だと思います。
元のコレクションを再配置するのではなく、データベース設計から概念を借用します。特定の基準に従ってインデックスを保持します。このインデックスは、優れた柔軟性を提供する追加の間接性です。
これにより、クラスの異なるメンバーに応じて複数のインデックスを生成できます。
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 );
}
ltjaxの答えは素晴らしいアプローチです-これは実際にはboostのzip_iterator http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html
提供するイテレータが何であれ、タプルにパッケージ化されます。
その後、タプル内のイテレータ値の任意の組み合わせに基づいて、ソート用の独自の比較関数を作成できます。この質問では、タプルの最初のイテレータになります。
このアプローチの優れた機能は、個々のベクトルのメモリを連続させておくことができることです(ベクトルを使用していて、それが必要な場合)。また、intの個別のインデックスベクトルを保存する必要もありません。
単一の keys
ベクトルに基づいてすべてのベクトルを反復処理する場合のxtoflの答えのわずかにコンパクトなバリアント。順列ベクトルを作成し、これを使用して他のベクトルにインデックスを付けます。
#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 ---&gt; 1; 1 ---&gt; 3; 2 ---&gt; 4; 4 ---&gt; 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;
}
}
};
ages
を順序付けられたものと一致させるために使用される、順序付けられた名前と順序付けられていない names
との間の index mapping 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";
}
}
}
and:
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`
}**
C ++ 11ラムダおよびKonrad RudolphとGabriele D'Antonaからの回答に基づくSTLアルゴリズムを使用:
template< typename T, typename U >
std::vector<T> sortVecAByVecB( std::vector<T> & a, std::vector<U> & b ){
// zip the two vectors (A,B)
std::vector<std::pair<T,U>> zipped(a.size());
for( size_t i = 0; i < a.size(); i++ ) zipped[i] = std::make_pair( a[i], b[i] );
// sort according to B
std::sort(zipped.begin(), zipped.end(), []( auto & lop, auto & rop ) { return lop.second < rop.second; });
// extract sorted A
std::vector<T> sorted;
std::transform(zipped.begin(), zipped.end(), std::back_inserter(sorted), []( auto & pair ){ return pair.first; });
return sorted;
}
非常に多くの人がこの質問をしましたが、満足のいく答えを出す人はいませんでした。これは、1つのベクトルの値のみを考慮して、2つのベクトルを同時にソートできるstd :: sortヘルパーです。このソリューションは、カスタムRadomIt(ランダムイテレーター)に基づいており、一時的なコピー、構造の再配置、または追加のインデックスなしで、元のベクターデータに対して直接動作します。