0

我有一个函数，它接受两个与参数大小相同的向量：

void mysort(std::vector<double>& data, std::vector<unsigned int>& index)
{
   // For example :
   // The data vector contains : 9.8 1.2 10.5 -4.3
   // The index vector contains : 0 1 2 3
   // The goal is to obtain for the data : -4.3 1.2 9.8 10.5
   // The goal is to obtain for the index : 3 1 0 2
   // Using std::sort and minimizing copies
}

如何解决最小化所需副本数量的问题？

一种明显的方法是制作一个向量std::pair<double, unsigned int>并指定比较器[](std::pair<double, unsigned int> x, std::pair<double, unsigned int> y){return x.first < y.first;}，然后将结果复制到两个原始向量中，但这不会有效。

注意：函数的签名是固定的，我不能传递std::pair.

4

5 回答 5

6

在函数内部，positions = [0,1,2,3...] 使用比较器对位置进行矢量排序(int x, int y){return data[x]<data[y];}。

然后迭代位置，做result.push_back(index[*it]);

这假设 in 的值index可以是任意的。如果保证已经[0,1,2..]如您的示例中那样，那么您不要制作positions数组，只需index在其位置使用并跳过最后一个副本。

于 2012-11-28T16:42:42.677 回答
2

http://www.boost.org/doc/libs/1_52_0/libs/iterator/doc/index.html#iterator-facade-and-adaptor

写一个迭代器std::pair<double&, signed int&>，实际上将一对迭代器包装到每个向量中。唯一棘手的部分是确保std::sort实现结果是随机访问迭代器。

如果你不能使用 boost，就自己写一个等价的。

在执行此操作之前，请确定是否值得您费心。zip、sort 和 unzip 更容易编写，并且程序员的时间可以在很多地方换取性能：直到你知道它的最佳使用位置，也许你应该做一个足够好的工作，然后在你需要的地方进行基准测试加快速度。

于 2012-11-28T16:42:29.853 回答
1

您可以使用仿函数类来保存对值数组的引用，并将其用作比较器来对索引数组进行排序。然后将这些值复制到一个新的值数组并交换内容。

struct Comparator
{
    Comparator(const std::vector<double> & data) : m_data(data) {}
    bool operator()(int left, int right) const { return data[left] < data[right]; }
    const std::vector<double> & m_data;
};

void mysort(std::vector<double>& data, std::vector<unsigned int>& index)
{
    std::sort(index.begin(), index.end(), Comparator(data));
    std::vector<double> result;
    result.reserve(data.size());
    for (std::vector<int>::iterator it = index.begin(), e = index.end();  it != e;  ++it)
        result.push_back(data[*it]);
    data.swap(result);
}
于 2012-11-28T16:42:25.143 回答
1

您可以使用自定义迭代器类，它并行迭代两个向量。其内部成员将包括

  1. 两个引用（或指针），每个向量一个
  2. 指示当前位置的索引

迭代器的值类型应该是 a pair<double, unsigned>。这是因为std::sort不仅会交换项目，而且在某些情况下还会临时存储单个值。我在这个问题的第 3 节中写了更多详细信息。

引用类型必须是某个类，它再次保存对向量和当前索引的引用。因此，如果您小心的话，您可以使引用类型与迭代器类型相同。引用类型的operator=必须允许从值类型赋值。并且该swap函数应该专门用于此引用，以允许通过分别交换两个列表来交换这些列表项。

于 2012-11-28T16:45:42.023 回答
-1

这应该这样做：

std::sort(index.begin(), index.end(), [&data](unsigned i1, unsigned i2)->bool
{ return data[i1]<data[i2]; });

std::sort(data.begin(), data.end());
于 2012-11-28T16:44:27.693 回答