Предоставляет ли STL или BOOST какой-либо простой способ получить порядок сортировки без изменения порядка следования?

Question

Я бы хотел найти порядок сортировки вектора, например, без переупорядочения вектора.

Я могу придумать несколько способов сделать это, мне интересно, не хватает ли мне какого-нибудь встроенного STL или BOOST способа сделать это.

Я думаю, что если бы функциональность была доступна, код в конечном итоге выглядел бы примерно так:

std::vector<float> unsortedSeq;
unsortedSeq.push_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

Кто-нибудь знает любые STL или BOOST-симы, которые будут делать то, о чем я спрашиваю, так же просто, как показано?

Answer 1

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

Answer 2

Вы бы сделали что-то вроде этого:

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

Это генерирует вектор индексов, а затем сортирует их на основе вектора фактического материала.

Answer 3

Нет; ты должен сделать это сам.

К счастью, это довольно просто! (возможно, поэтому он не предоставляется)

• Рассмотрим входной вектор v
• Создать вектор индексов 0 .. n , где n - размер вашего ввода v
• std::sort вектор индексов, предоставляющий ссылку на вход v, и пользовательский компаратор, который возвращает v[left] < v[right].

Answer 4

Другой пример, используя 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;
}

Answer 5

С помощью всего лишь нескольких модификаций ответа Никола Боласа это позволяет использовать любой итератор произвольного доступа в качестве входных данных (при условии, что он является случайным итератором и имеет член типа reference). Также может быть предоставлена ​​функция сравнения (как в std::sort, по умолчанию используется 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

Рабочий пример может быть найден здесь .