对(双精度)实数的向量进行排序并获得它们的 [英] Sorting a vector of (double precision) reals and obtain their

问题描述

在C ++中，想对一个长的(2^20)实数向量进行排序，显然sort()可以解决问题.在我习惯了不错的order()函数之前使用过R，该函数会产生导致排序矢量的置换.

In C++ would like to sort a lengthy (2^20) vector of reals, obviously sort() does the trick. Having used R before I was used to the nice order() function which yields the permutation that leads to the sorted vector.

示例:

x = {24, 55, 22, 1}

然后排列

perm = {3, 2, 0, 1}

按升序将原始x映射到已排序的x.

Maps the original x to the sorted x in ascending order.

我可能可以实现一些冒泡排序，该冒泡排序不仅对x进行排序，而且对向量{0,1,2,...}执行相同的换位并输出两者，但我相信有人一定对此有所考虑，尤其是有效地做到了. >

I can probably implement some bubble sort which does not only sort x but performs the same transpositions on the vector {0,1,2,...} and outputs both, but I believe someone must have thought about it and especially have done it efficiently.

推荐答案

编辑

在不使用辅助向量的情况下比以前更好:( 基于ideone的源):

Better than before approach without using helper vectors: (source on 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，但可以将其替换为简单的functor对象:

I am using lambda from C++0x, but it can be replaced with simple functor object:

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

Source of old solution with std::map: ideone

这篇关于对(双精度)实数的向量进行排序并获得它们的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！