std::vector not sorted as intended by std::sort

Question

I want to sort a vector of integers based on a vector of real numbers. E.g. I have a vector of integers (1,2,3) and a corresponding vector of real numbers (0.3,0.2,0.1). Now I want to sort the integers so that the integer corresponding to the smallest real number comes first, the integer corresponding to the second smallest real number comes second and so on i.e. the vector of integers should be sorted like (3,2,1). The code is:

int main()
{
    const unsigned int M = 5;
    const unsigned int N = 10;
    Eigen::MatrixXd samples = Eigen::MatrixXd::Random(M,N);
    std::vector<unsigned int> indices(N);
    std::iota(indices.begin(),indices.end(),0);
    std::shuffle(indices.begin(),indices.end(),std::default_random_engine(1.0));
    const unsigned int S = 4;
    std::vector<unsigned int> A(indices.begin(),indices.begin()+S);
    std::vector<unsigned int> B(indices.begin()+S,indices.end());

    std::default_random_engine generator;
    std::uniform_int_distribution<unsigned int> distribution(0,N-1);
    const unsigned int index = distribution(generator);

    std::vector<double> distances(A.size());
    for(unsigned int l=0; l<A.size(); ++l)
    {
        distances[l] = (samples.col(index)-samples.col(A[l])).norm();
    } 
    std::sort(A.begin(),A.end(),[&distances](unsigned int i, unsigned int j){return 
    distances[i]<distances[j];});

    distances.resize(B.size());
    for(unsigned int i=0; i<B.size(); ++i)
    {
        distances[i] = (samples.col(index)-samples.col(B[i])).norm();
    }
    std::cout << "distances:" << std::endl;
    for(unsigned int i=0; i<B.size(); ++i)
    {
        std::cout << distances[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "indices before sorting:" << std::endl;
    for(unsigned int i=0; i<B.size(); ++i)
    {
        std::cout << B[i] << " ";
    }
    std::cout << std::endl;
    std::sort(B.begin(),B.end(),[&distances](unsigned int i, unsigned int j){return 
    distances[i]<distances[j];});
    std::cout << "indices after sorting:" << std::endl;
    for(unsigned int i=0; i<B.size(); ++i)
    { 
        std::cout << B[i] << " ";
    } 
    std::cout << std::endl;

    return 0;
}

The output is:

distances:

2.42122 0.940923 1.45279 1.81009 1.96321 1.76887

indices before sorting:

2 5 4 9 8 7

indices after sorting:

7 8 9 2 5 4

Why is the output NOT as follows?

distances:

2.42122 0.940923 1.45279 1.81009 1.96321 1.76887

indices before sorting:

2 5 4 9 8 7

indices after sorting:

5 4 7 9 8 2

Answer 1

You're getting confused with the different indices for the different containers.

By your code, distance[0] does not contain the distance of "index" 0, but the distance of index B[0] which is index 2.

Try using this with your sorting function:

auto sort_lambda = [&samples, &index] (unsigned int l, unsigned int r) {
  auto l_value = (samples.col(index)-samples.col(l)).norm();
  auto r_value = (samples.col(index)-samples.col(r)).norm();
  return l_value < r_value;
};

---

As for the general case where you have a vector of indices and a vector of values: You can create a map of correspondences, and use that to get the value from some index:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <unordered_map>
#include <vector>

int main()
{
    using vi = std::vector<int>;
    using vf = std::vector<float>;

    vi indices = {2, 4, 8, 1};
    vf values = {1.5, 0.5, 2.5, 4.5};

    std::unordered_map<int, float> correspondences;
    std::transform(begin(indices), end(indices), begin(values),
        std::inserter(correspondences, end(correspondences)),
        [](int i, float v) { return std::make_pair(i, v); });
    std::sort(begin(indices), end(indices),
        [&correspondences](int l, int r) {
            return correspondences.at(l) < correspondences.at(r);
        });
    // Note that now using values is basically impossible because it wasn't sorted as well ... you'd need to sort it now, too!
    std::copy(begin(indices), end(indices), std::ostream_iterator<int>(std::cout, ", "));
}

(ideone link)

If inidices and / or values have a more complex type, then you might want to use std::reference_wrapper to avoid making copies when building the correspondences map.

It probably doesn't make that much sense to keep values and indices separate when you need to do this often!

---

More general, allows duplicate values for the "to be sorted" vector:

#include <algorithm>
#include <functional>
#include <iterator>
#include <vector>



template<typename A, typename B>
void sort_according_to(std::vector<A> & to_sort, std::vector<B> const & ref)
{
    using pair_t = std::pair<A, std::reference_wrapper<const B>>;
    std::vector<pair_t> work;
    work.reserve(to_sort.size());
    std::transform(
        std::make_move_iterator(begin(to_sort)),
        std::make_move_iterator(end(to_sort)),
        begin(ref),
        std::back_inserter(work),
        [](A&& a, B const & b) {
            return std::make_pair(std::move(a), std::cref(b));
        });
    std::sort(
        begin(work), end(work),
        [](pair_t const & l, pair_t const & r) {
            return l.second.get() < r.second.get();
        });
    std::transform(
        begin(work), end(work),
        begin(to_sort),
        [](pair_t & p) {
            return std::move(p.first);
        });
}



#include <iostream>


int main()
{
    std::vector<int> ints = {1, 1, 2, 2, 3};
    std::vector<float> floats = {0.1, 1.1, 0.2, 2.2, -3.14};

    sort_according_to(ints, floats);

    std::copy(
        begin(ints), end(ints),
        std::ostream_iterator<int>(std::cout, ", "));

}

(It doesn't make copies but moves the data instead)