使用 STL 算法根据存储在另一个向量中的权重对向量进行排序

Question

我有一个包含 class 实例的向量，比方说 std::vector<A> a。我想根据存储在 std::vector<float> weights 中的权重对这个向量进行排序，其中 weights[i] 是与 a[i] 关联的权重；排序后，a 个元素必须按权重递增排序。

我知道如何明确地执行此操作，但我想使用 C++14 STL 算法以便从最终的最佳实现中获益。到目前为止，我一直无法弄清楚如何在 std::sort 的 lambda 比较表达式中使用 weights，也不知道如何每次都保持 a 和 weights 对齐a 的两个元素被 std::sort 交换，所以我开始认为这可能是不可能的。

在此先感谢您的帮助。

Answer 1

转换 std::pair 向量中的两个向量，然后根据权重（对的第二个成员）进行排序。之后重新创建两个向量
向 A class 添加一个新成员，使其包含权重并根据该权重进行排序
根据包含此处所述权重的全局数组创建自定义比较函数：std::sort and custom swap function

我会选择 3，因为它是最有效的。如果您没有需要一些同步的多线程，那是有效的。

Answer 2

我的评论完全是在暗示@AndreaRossini 用他们的评论总结的内容。像这样：

#include <boost/hana/functional/on.hpp>
#include <functional>
#include <iostream>
#include <range/v3/algorithm/sort.hpp>
#include <range/v3/view/transform.hpp>
#include <range/v3/view/zip.hpp>
#include <string>
#include <vector>

using boost::hana::on;
using namespace ranges;
using namespace ranges::views;

// helpers to get first and second of a pair
auto /*C++17->*/constexpr/*<-C++17*/ fst = [](auto const& p){ return p.first; };
auto /*C++17->*/constexpr/*<-C++17*/ snd = [](auto const& p){ return p.second; };

int main(){
    std::vector<std::string> v{"one", "two", "three"}; // values
    std::vector<float> w{3,1,2};                       // weights

    // zipping the two sequences; each element of vw is a pair
    auto vw = zip(v, w);

    // sorting: using `std::less` on the `snd` element of the pairs
    sort(vw, std::less<>{} ^on^ snd);

    // extracting only the `fst` of each pair
    auto res = vw | transform(fst);

    // show result
    for (auto i : res) { std::cout << i << std::endl; }
}

关于我使用的库的一些事情：

res 不是 std::vector 而只是 view；如果你想要一个向量，你可以做

#include <range/v3/range/conversion.hpp>
auto res = vw | transform(fst) | to_vector;

std::less<>{} ^on^ snd等价于下面的f
```
auto f = [](auto const& x, auto const& y){
    return std::less<>{}(snd(x), snd(y));
};
```
所以你可以把它想象成一个接受 x 和 y 并返回 snd(x) < snd(y).

Answer 3

对索引向量进行排序，然后根据结果重新排列：

void my_sort(std::vector<A>& a, std::vector<float>& weights)
{
  std::vector<int> idx(a.size());
  std::iota(idx.begin(), idx.end(), 0);
  sort(idx.begin(), idx.end(),
     [&](int a, int b) { return weights[a] < weights[b]; });

  auto reorder = [&](const auto& o) {
     decltype(o) n(o.size());
     std::transform(idx.begin(), idx.end(), n.begin(),
         [&](int i) { return o[i]; });
     return n;
  };
  a = reorder(a);
  weights = reorder(weights);
}

使用 STL 算法根据存储在另一个向量中的权重对向量进行排序

Order a vector according to weights stored in another vector using STL algorithms

c++

c++14