3

只是要知道，我现在说的是 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 来实现这一点吗？

4

6 回答 6

3

没有现成的功能可以实现这一点，但有一些变通方法。例如，您可以保留一个包含原始位置的用户定义结构数组：

A = { {4,0}, {1,1}, {5,2}, {2,3}, {3,4}}

然后使用自定义比较器函数对其进行排序，该函数按值而不是原始索引排序。

A_sorted = {{1,1}, {2,3}, {3,4}, {4,0}, {5,2}}
于 2012-11-06T09:37:18.000 回答
3

试试这个：如果你想转换为矢量：

 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;
  }
于 2012-11-06T09:41:21.827 回答
2

如果您无法修改存储在 中的内容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新位置。Astd::find(indices, indices+5, i) - indices

于 2012-11-06T09:51:05.130 回答
1 
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());
}
于 2012-11-06T09:35:56.700 回答
1

好的，索引通常会告诉您向量的第 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，依此类推。

于 2012-11-06T10:01:00.580 回答
0

您可以使用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 现在显示相应数组中的索引。

于 2012-11-06T09:40:09.490 回答