これを実現する既製の機能はありませんが、回避策があります。たとえば、元の位置も含むユーザー定義の構造体の配列を保持できます。
A = { {4,0}, {1,1}, {5,2}, {2,3}, {3,4}}
そして、元のインデックスではなく値でソートするカスタム コンパレータ関数を使用して、これをソートします。
A_sorted = {{1,1}, {2,3}, {3,4}, {4,0}, {5,2}}
これを試してください: ベクトルに変換したい場合:
int A[] = {4, 1, 5, 2, 3};
int A_sorted [] = {1, 2, 3, 4, 5};
std::vector<int> v(A_sorted, A_sorted + 5);
for (int i=0; i<5; i++)
{
std::vector<int>::iterator low = lower_bound (v.begin(), v.end(), A[i]);
std::cout << "Element: " << A[i] << " is at: " << distance(v.begin(), low) << std::endl;
}
生の配列で作業したい場合：
int A[] = {4, 1, 5, 2, 3};
int A_sorted [] = {1, 2, 3, 4, 5};
for (int i=0; i<5; i++)
{
int* low = std::lower_bound (&A_sorted[0], &A_sorted[5], A[i]);
cout << "Element: " << A[i] << " is at: " << distance(&A_sorted[0], low) << endl;
}
に格納されているものを変更できない場合はA、インデックス配列を作成し、特別な述語で並べ替えることができます。
int A[] = {4, 1, 5, 2, 3};
size_t indices[] = {0, 1, 2, 3, 4};
bool sortBefore(size_t i, size_t j) {
return A[i] < A[j];
}
std::sort(indices, indices + 5, sortBefore);
sorted_A[i]次に、としてアクセスするか、インデックスに従ってA[indices[i]]再配置します。isのi番目の要素のA新しい位置。Astd::find(indices, indices+5, i) - indices
わかりました、インデックスは通常、ベクトルの n 番目に並べ替えられた要素が何であるかを示します。しかし、これは逆になるため、ベクトルの n 番目の要素がソート順で m 番目であることがわかります。
これは、ソートされていないベクトルにインデックスのベクトルを作成することによって行われています。もちろん、ソートされたコピーやインデックスを作成することもできます。
a < b if v[a] < v[b] の述語から始めます。
template< typename T >
class PredByIndex
{
private:
std::vector< T > const & theColl;
public:
PredByIndex( std::vector<T> const& coll ) : theColl( coll )
{
}
bool operator()( size_t i, size_t j ) const
{
return theColl[i] < theColl[j];
}
};
template< typename T >
void makeOrdered( std::vector< T > const& input, std::vector< size_t > & order )
{
order.clear();
size_t len = input.size();
order.reserve( len );
for( size_t i = 0; i < len; ++i )
{
order.push_back( i );
}
PredByIndex<T> pred( input );
std::sort( order.begin(), order.end(), pred );
}
そして今、「注文」は、注文されたコレクション内で序数の位置を持ちます。
もちろん、C++11 では PredByIndex クラスを作成するのではなく、述語をラムダ式として記述できます。
まだ終わりではありません。「ソートされたベクトルで私を見つける」ではなく、インデックスが作成されました。ただしtranspose、次のようにインデックスを作成できます。
void transpose_index( std::vector< size_t > const & index,
std::vector< size_t > & trans )
{
// for this to work, index must contain each value from 0 to N-1 exactly once.
size_t size = index.size();
trans.resize( index.size() );
for( size_t i = 0; i < size; ++i )
{
assert( index[i] < size );
// for further assert, you could initialize all values of trans to size
// then as we go along, ensure they still hold that value before
// assigning
trans[ index[i] ] = i;
}
}
これで、転置されたインデックスが必要なものを提供し、転置自体は次のようになります。O(N)
少し異なるデータの例では、入力が[ 5, 3, 11, 7, 2 ]
「ソートされた」順序は[ 2, 3, 5, 7, 11 ]
「インデックス」の順序は[4, 1, 0, 3, 2]、要素 4 が最小で、次に要素 1 などです。
「転置」順序を入力します
[ _, _, _, _, _ ]
[ _, _, _, _, 0 ]
[ _, 1, _, _, 0 ]
[ 2, 1, _, _, 0 ]
[ 2, 1, _, 3, 0 ]
[ 2, 1, 4, 3, 0 ]
これは私たちが望んでいるように見えます。元のデータ5はソートされたデータの位置2、3は位置1、11は位置4などです。
template<class T>
struct ValueWithIndex
{
T Value;
int index;
};
template<class T>
bool operator < (const ValueWithIndex<T>& v1, const ValueWithIndex<T>& v2)
{
return v1.value < v2.value;
}
template<class T> ValueWithIndex<T>
MakeValueWithIndex(const T& value, int index)
{
ValueWithIndex<T> ret;
ret.value = value;
ret.index = index;
return ret;
}
のコンテナをソートしますValueWithIndex。元のインデックスに関する情報は失われません。
int main()
{
std::vector<ValueWithIndex<int>> v;
for(int i = 0; i < n; ++i)
{
int value;
std::cin >> value;
v.push_back(MakeValueWithIndex(value, i));
}
std::sort(v.begin(), v.end());
}
find要素の検索に使用できます。
int *p1 = std::find(&A[0], &A[5], 5);
int *p2 = std::find(&A_sorted[0], &A_sorted[5], 5);
距離を使用してインデックスを表示します。
int i1 = p1 - A;
int i2 = p2 - A_sorted;
i1 と i2 は、対応する配列のインデックスを表示するようになりました。