1 つのベクトルのみを使用する基準を使用して、2 つのベクトルを同じ方法で並べ替えるにはどうすればよいですか?
たとえば、同じサイズの 2 つのベクトルがあるとします。
vector<MyObject> vectorA;
vector<int> vectorB;
次にvectorA、比較関数を使用して並べ替えます。その並べ替えが並べ替えられvectorAました。に同じ並べ替えを適用するにはどうすればよいvectorBですか?
1 つのオプションは、構造体を作成することです。
struct ExampleStruct {
MyObject mo;
int i;
};
次に、コンテンツを含むベクターをソートし、1 つのベクターvectorAにvectorB圧縮します。
// vectorC[i] is vectorA[i] and vectorB[i] combined
vector<ExampleStruct> vectorC;
これは理想的な解決策とは思えません。特にC++ 11では、他のオプションはありますか?
std::vector<T>と の比較が与えられたT場合、この比較を使用してベクトルをソートする場合に使用する順列を見つけられるようにしたいと考えています。
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;
}
a と a の順列が与えられた場合、順列に従って並べ替えられstd::vector<T>た new を構築できるようにしたいと考えています。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もちろん、新しい並べ替えられたコピーを返すのではなく、指定したベクトルを変更するように変更することもできます。このアプローチは依然として線形時間の複雑さであり、ベクトル内の項目ごとに 1 ビットを使用します。理論的には、依然として線形空間の複雑さです。しかし、実際には、sizeof(T)が大きい場合、メモリ使用量が大幅に削減される可能性があります。(詳細を見る)
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);
ティモシーのような順列を使用しますが、データが大きすぎて、並べ替えられたベクターにこれ以上メモリを割り当てたくない場合は、インプレースで行う必要があります。permutation を使用した O(n) (線形複雑度) インプレース ソートの例を次に示し ます。
秘訣は、順列と逆順列を取得して、最後の並べ替えステップで上書きされたデータをどこに置くかを知ることです。
template <class K, class T>
void sortByKey(K * keys, T * data, size_t size){
std::vector<size_t> p(size,0);
std::vector<size_t> rp(size);
std::vector<bool> sorted(size, false);
size_t i = 0;
// Sort
std::iota(p.begin(), p.end(), 0);
std::sort(p.begin(), p.end(),
[&](size_t i, size_t j){ return keys[i] < keys[j]; });
// ----------- Apply permutation in-place ---------- //
// Get reverse permutation item>position
for (i = 0; i < size; ++i){
rp[p[i]] = i;
}
i = 0;
K savedKey;
T savedData;
while ( i < size){
size_t pos = i;
// Save This element;
if ( ! sorted[pos] ){
savedKey = keys[p[pos]];
savedData = data[p[pos]];
}
while ( ! sorted[pos] ){
// Hold item to be replaced
K heldKey = keys[pos];
T heldData = data[pos];
// Save where it should go
size_t heldPos = rp[pos];
// Replace
keys[pos] = savedKey;
data[pos] = savedData;
// Get last item to be the pivot
savedKey = heldKey;
savedData = heldData;
// Mark this item as sorted
sorted[pos] = true;
// Go to the held item proper location
pos = heldPos;
}
++i;
}
}
個々のベクトルからペアのベクトルを作成します。
ペアのベクトルを初期化する ペア
のベクトルに追加する
カスタム ソート コンパレータの作成:
カスタム オブジェクトのベクトルのソート
http://rosettacode.org/wiki/Sort_using_a_custom_comparator#C.2B.2B
ペアのベクトルを並べ替えます。
ペアのベクトルを個々のベクトルに分割します。
これらすべてを関数に入れます。
コード：
std::vector<MyObject> vectorA;
std::vector<int> vectorB;
struct less_than_int
{
inline bool operator() (const std::pair<MyObject,int>& a, const std::pair<MyObject,int>& b)
{
return (a.second < b.second);
}
};
sortVecPair(vectorA, vectorB, less_than_int());
// make sure vectorA and vectorB are of the same size, before calling function
template <typename T, typename R, typename Compare>
sortVecPair(std::vector<T>& vecA, std::vector<R>& vecB, Compare cmp)
{
std::vector<pair<T,R>> vecC;
vecC.reserve(vecA.size());
for(int i=0; i<vecA.size(); i++)
{
vecC.push_back(std::make_pair(vecA[i],vecB[i]);
}
std::sort(vecC.begin(), vecC.end(), cmp);
vecA.clear();
vecB.clear();
vecA.reserve(vecC.size());
vecB.reserve(vecC.size());
for(int i=0; i<vecC.size(); i++)
{
vecA.push_back(vecC[i].first);
vecB.push_back(vecC[i].second);
}
}
vectorA と vectorB の長さは等しいと仮定しています。別のベクトルを作成できます。それを pos と呼びましょう。
pos[i] = the position of vectorA[i] after sorting phase
次に、pos を使用して vectorB をソートできます。つまり、vectorBsorted を作成します。
vectorBsorted[pos[i]] = vectorB[i]
次に、vectorBsorted は、vectorA と同じインデックス順列で並べ替えられます。
これが機能するかどうかはわかりませんが、このようなものを使用します。たとえば、2 つのベクトルを並べ替えるには、降順のバブル ソート方法とベクトルのペアを使用します。
降順バブル ソートの場合、ベクトル ペアを必要とする関数を作成します。
void bubbleSort(vector< pair<MyObject,int> >& a)
{
bool swapp = true;
while (swapp) {
int key;
MyObject temp_obj;
swapp = false;
for (size_t i = 0; i < a.size() - 1; i++) {
if (a[i].first < a[i + 1].first) {
temp_obj = a[i].first;
key = a[i].second;
a[i].first = a[i + 1].first;
a[i + 1].first = temp_obj;
a[i].second = a[i + 1].second;
a[i + 1].second = key;
swapp = true;
}
}
}
}
その後、2 つのベクトル値を 1 つのベクトル ペアにします。同時に値を追加できる場合は、これを使用してバブル ソート関数を呼び出します。
vector< pair<MyObject,int> > my_vector;
my_vector.push_back( pair<MyObject,int> (object_value,int_value));
bubbleSort(my_vector);
2 つのベクトルに追加した後に値を使用する場合は、このベクトルを使用して、バブル ソート関数を呼び出すことができます。
vector< pair<MyObject,int> > temp_vector;
for (size_t i = 0; i < vectorA.size(); i++) {
temp_vector.push_back(pair<MyObject,int> (vectorA[i],vectorB[i]));
}
bubbleSort(temp_vector);
これが役立つことを願っています。よろしく、 カナー