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

Question

我有一个向量，包含一个类的实例，假设是std::vector<A> a。我想根据存储在std::vector<float> weights中的权重来排序这个向量，其中weights[i]是与a[i]相关的权重;排序后，a元素必须按权重递增排序。

我知道如何显式地做到这一点，但我想使用c++ 14 STL算法，以便从最终的最佳实现中受益。到目前为止，我还没能弄清楚如何在std::sort的lambda比较表达式中使用weights，也不知道如何在a的两个元素被std::sort交换时保持a和weights对齐，所以我开始认为这可能是不可能的。

提前感谢您的帮助。

Answer 1

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

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);
}

Answer 2

1. 在std::pair<a,float>向量，然后根据权重(对的第二个成员)排序。之后重新创建两个矢量
2. 为a类添加一个新成员，使其包含基于该权重的权重和排序
3. 创建一个基于全局数组的自定义比较函数，包含如下所述的权重:std::sort和自定义交换函数

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

Answer 3

我的评论完全暗指@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，只是一个视图;如果你想要一个向量，你可以这样做

  #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)。