只是要知道,我现在说的是 C++。
假设我有一个数组A = {4, 1, 5, 2, 3}
并将其排序在A_sorted = {1, 2, 3, 4, 5}
. 我想保留以下信息:e
排序数组 A_sorted 中的元素(来自数组 A)现在在哪里?例如:A ( 5
) 中索引为 2 的元素现在在 A_sorted 中具有索引 4。
问题更像是:可以使用 STL 来实现这一点吗?
没有现成的功能可以实现这一点,但有一些变通方法。例如,您可以保留一个包含原始位置的用户定义结构数组:
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]
as ,要么根据索引A[indices[i]]
重新排列。is的第i个元素的A
新位置。A
std::find(indices, indices+5, i) - indices
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());
}
好的,索引通常会告诉您向量的第 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 );
}
现在“order”将在有序集合中具有序数位置。
当然,在 C++11 中,谓词可以写成 lambda 表达式,而不必创建类 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,依此类推。
您可以使用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 现在显示相应数组中的索引。