对(双精度)实数的矢量进行排序并获得它们

Question

在C++中,我想对reals的long(2^20)向量进行排序,显然sort()可以解决这个问题.在我习惯了很好的order()函数之前使用了R,它产生了导致排序向量的排列.

例:

x = {24, 55, 22, 1}

然后是排列

perm = {3, 2, 0, 1}

将原始图像x按x升序排列.

我可以实现一些冒泡排序,它不仅可以排序x,而且可以在向量上执行相同的转置{0,1,2,...}并输出两者,但我相信有人必须考虑它,特别是有效地完成它.

Answer 1

我想说最好的方法是创建一个int 0..N的向量,然后用比较函数对该数组进行排序,该函数比较你试图找到排序排列的向量的相应元素.就像是:

#include <vector>
#include <algorithm>

template<class T> class sorter {
    const std::vector<T> &values;
public:
    sorter(const std::vector<T> &v) : values(v) {}
    bool operator()(int a, int b) { return values[a] < values[b]; }
};

template<class T> std::vector<int> order(const std::vector<T> &values)
{
    std::vector<int> rv(values.size());
    int idx = 0;
    for (std::vector<int>::iterator i = rv.begin(); i != rv.end(); i++)
        *i = idx++;
    std::sort(rv.begin(), rv.end(), sorter<T>(values));
    return rv;
}

这样可以最大限度地减少分配开销,因为我们不会创建任何大型临时对象,我们会对其进行排序,然后提取最终的权限 - 返回的相同向量是排序的临时值.

Answer 2

编辑

比以前的方法更好，无需使用辅助向量：（ideone 上的来源）：

#include <vector>
#include <algorithm>
#include <iostream>

template<class Vals>
void sortingPermutation(const Vals& values, std::vector<int>& v){
  int size = values.size(); 
  v.clear(); v.reserve(size);
  for(int i=0; i < size; ++i)
    v.push_back(i);

  std::sort(v.begin(), v.end(), [&values](int a, int b) -> bool { 
    return values[a] < values[b];
  });
}

int main()
{
    std::vector<double> values;
    values.push_back(24);
    values.push_back(55);
    values.push_back(22);
    values.push_back(1);

    std::vector<int> permutation;
    sortingPermutation(values, permutation);

    typedef std::vector<int>::const_iterator I;
    for (I p = permutation.begin(); p != permutation.end(); ++p)
        std::cout << *p << " ";
    std::cout << "\n";
}

我正在使用 C++0x 中的 lambda，但它可以用简单的函子对象替换：

template<class T>
struct CmpPairs{
  CmpPairs(const std::vector<T> &v): v_(v) {}
  std::vector<T> v_;
  bool operator()(int a, int b){ return v_[a] < v_[b]; }
};

template<class T>
CmpPairs<T> CreateCmpPairs(const std::vector<T> & v) { return CmpPairs<T>(v); }
//in sortingPermutation:
std::sort(v.begin(), v.end(), CreateCmpPairs(values));

旧解决方案的来源std::map：ideone