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

user_1131907 0
Viewed 169

I have a vector containing instances of a class, let's say std::vector<A> a. I want to order this vector according to weights stored in a std::vector<float> weights, with weights[i] being the weight associated to a[i]; after sorting, a elements must be ordered by increasing weight.

I know how to do this explicitly, but I'd like to use C++14 STL algorithms in order to benefit from an eventual optimal implementation. Up to now, I haven't been able to figure how to use weights in a lambda comparison expression for std::sort, nor how to keep a and weights aligned every time two elements of a are swapped by std::sort, so I'm beginning to think that it might be not possible.

Thanks in advance for any help.

c++14 c++
3 Answers

Sort an index vector, then rearrange according to the result:

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);
}
user_68685430
  1. Transform the two vectors in a std::pair<A,float> vector and then sort based on the weight ( second member of the pair ) . Recreate the two vectors afterwards
  2. Add a new member to the A class so that it contains the weight and sort based on that weight
  3. make a custom comparison function based on a global array containing the weights like described here: std::sort and custom swap function

I would go for 3 as it is the most efficient. That is valid if you don't have multi-threading which would require some synchronization.

user_131360

With my comment I was alluding exactly to what @AndreaRossini summarised with their comment. Something like this:

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

A few things about the libraries that I've used:

  • res is not a std::vector but just a view; if you want a vector, you can do 
    #include <range/v3/range/conversion.hpp>
auto res = vw | transform(fst) | to_vector;
  • std::less<>{} ^on^ snd is equivalent to the following f 
    auto f = [](auto const& x, auto const& y){
    return std::less<>{}(snd(x), snd(y));
};
    so you can think of it as a function that takes x and y and gives back snd(x) < snd(y).
user_58252940
Related