Does STL or BOOST provide any clean way to get the sort order without reordering original sequence?

I'd like to find the sort order of a vector, for example, without reordering the vector.

I can think of several ways to do this, I'm wondering if I'm missing some built-in STL or BOOST way to do this.

I imagine if the functionality were available the code would end up looking something like this:

std::vector<float> unsortedSeq;
unsortedSeq.pu开发者_如何学运维sh_back( 1.1 );
unsortedSeq.push_back( 1.0 );
unsortedSeq.push_back( 0.5 );
unsortedSeq.push_back( 1.2 );
unsortedSeq.push_back( 1.15 );

std::list<std::size_t> sortOrder;

std::sort_indices( unsortedSeq.begin(), unsortedSeq.end(), sortOrder.begin() );

BOOST_FOREACH( std::size_t index, sortOrder )
{
    std::cout << index << "\n"
}



2
1
0
4
3

Anyone know any STL or BOOST-sims that would do what I'm asking about as simply as shown?

std::vector<float> v;
// filled somewhere else

std::vector<std::size_t> indices(v.size());
// iota is from <numeric>, C++0x
std::iota(indices.begin(), indices.end(), 0);

std::sort(indices.begin(), indices.end(), [&v](std::size_t left, std::size_t right)
{
    return v[left] < v[right];
});

You would do something like this:

template<typename T>
class SortOrder
{
public:
    SortOrder(const std::vector<T> *_sortArray) : sortArray(_sortArray) {;}

    bool operator()(int lhs, int rhs) const
    {
        return sortArray[lhs] < sortArray[rhs];
    }

private:
    const std::vector<T> *sortArray;
};

//To do the sorting:

#include <boost/range/counting_range.hpp>
auto countRange = boost::range::counting_range(0, myListOfStuff.size());

//Build a vector<int> that has one index for every value in your actual vector.
vector<int> indexList(countRange.begin(), countRange.end());

std::sort(indexList.begin(), indexList.end(), SortOrder(&myListOfStuff));

This generates a vector of indices, and then sorts them based on the vector of actual stuff.

No; you have to do it yourself.

Fortunately, it's quite easy! (which may be why it's not provided)

• Consider input vector v
• Create a vector of indexes 0..n, where n is the size of your input v
• std::sort the vector of indexes, providing a reference to the input v, and a custom comparator that returns v[left] < v[right].

Another example, using boost::ref...

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

#include <boost/ref.hpp>

int main()
{
    int n[] = { 3, 4, 1, 7, 10 };
    std::vector<int> v(n, n + 5);

    // print the original sequence
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    // fill another vector with references to the data in the original
    std::vector<boost::reference_wrapper<int> > vp;
    std::transform(v.begin(), v.end(), std::back_inserter(vp), &boost::ref<int>);

    // sort the references
    std::sort(vp.begin(), vp.end());

    // print the filtered version.
    std::copy(vp.begin(), vp.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    // print the original sequence again to show it hasnt changed
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
}

With just a few modifications to Nicol Bolas' answer, this allows any random access iterator to be used as input (as long as it is a random iterator and has a reference type member). The comparison function could also be provided (just like in std::sort, the default being std::less).

template<typename const_iterator>
class SortOrder
{
public:
    using Compare = std::function<bool(typename const_iterator::reference, typename const_iterator::reference)>;
    SortOrder(const_iterator to_sort, Compare comp = std::less<typename const_iterator::reference>()) :
        to_sort_(to_sort),
        comp_(comp)
    {}

    bool operator()(int lhs, int rhs) const
    {
        return comp_(*(to_sort_ + lhs), *(to_sort_ + rhs));
    }

private:
    const_iterator to_sort_;
    Compare comp_;
};

vector<double> to_sort{1, 5, 9, 2, 6, 17, 2, 8.5};

// Create integers, one value for each to_sort element
auto count_range = boost::counting_range(size_t(0), to_sort.size());
vector<int> indices(count_range.begin(), count_range.end());
// indices = 0 1 2 3 4 5 6 7

auto it = to_sort.begin();
sort(indices.begin(), indices.end(), SortOrder<decltype(it)>(it));
// indices = 0 3 6 1 4 7 2 5

A working example could be find here.