Как отсортировать std::vector по значениям другого std::vector?

Question

У меня есть несколько std::vector, все одинаковой длины.Я хочу отсортировать один из этих векторов и применить то же преобразование ко всем остальным векторам.Есть ли аккуратный способ сделать это?(желательно использовать STL или Boost)?Некоторые из векторов имеют место intи некоторые из них std::stringс.

Псевдокод:

std::vector<int> Index = { 3, 1, 2 };
std::vector<std::string> Values = { "Third", "First", "Second" };

Transformation = sort(Index);
Index is now { 1, 2, 3};

... magic happens as Transformation is applied to Values ...
Values are now { "First", "Second", "Third" };

Answer 1

Подход фриола хорош в сочетании с твоим. Сначала создайте вектор, состоящий из чисел 1 & # 8230; n , наряду с элементами вектора, определяющими порядок сортировки:

typedef vector<int>::const_iterator myiter;

vector<pair<size_t, myiter> > order(Index.size());

size_t n = 0;
for (myiter it = Index.begin(); it != Index.end(); ++it, ++n)
    order[n] = make_pair(n, it);

Теперь вы можете отсортировать этот массив с помощью пользовательского сортировщика:

struct ordering {
    bool operator ()(pair<size_t, myiter> const& a, pair<size_t, myiter> const& b) {
        return *(a.second) < *(b.second);
    }
};

sort(order.begin(), order.end(), ordering());

Теперь вы зафиксировали порядок перестановки внутри order (точнее, в первом компоненте элементов). Теперь вы можете использовать этот порядок для сортировки других ваших векторов. Вероятно, в то же время работает очень умный вариант на месте, но пока кто-то другой не придет с ним, вот один вариант, который не на месте. Он использует order в качестве справочной таблицы для нового индекса каждого элемента.

template <typename T>
vector<T> sort_from_ref(
    vector<T> const& in,
    vector<pair<size_t, myiter> > const& reference
) {
    vector<T> ret(in.size());

    size_t const size = in.size();
    for (size_t i = 0; i < size; ++i)
        ret[i] = in[reference[i].first];

    return ret;
}

Answer 2

Поместите свои значения в мультииндексный контейнер повышения. затем итерируйте, чтобы прочитать значения в нужном вам порядке. Вы даже можете скопировать их в другой вектор, если хотите.

Answer 3

typedef std::vector<int> int_vec_t;
typedef std::vector<std::string> str_vec_t;
typedef std::vector<size_t> index_vec_t;

class SequenceGen {
  public:
    SequenceGen (int start = 0) : current(start) { }
    int operator() () { return current++; }
  private:
    int current;
};

class Comp{
    int_vec_t& _v;
  public:
    Comp(int_vec_t& v) : _v(v) {}
    bool operator()(size_t i, size_t j){
         return _v[i] < _v[j];
   }
};

index_vec_t indices(3);
std::generate(indices.begin(), indices.end(), SequenceGen(0));
//indices are {0, 1, 2}

int_vec_t Index = { 3, 1, 2 };
str_vec_t Values = { "Third", "First", "Second" };

std::sort(indices.begin(), indices.end(), Comp(Index));
//now indices are {1,2,0}

Теперь вы можете использовать " индексы " вектор для индексации в «значения» вектор.

Answer 4

Мне приходит в голову только одно грубое решение: создать вектор, который является суммой всех других векторов (вектор структур, таких как {3, Third, ...}, {1, First, ...}) затем отсортируйте этот вектор по первому полю, а затем снова разделите структуры.

Вероятно, есть лучшее решение внутри Boost или с использованием стандартной библиотеки.

Answer 5

Вероятно, вы можете определить собственный " фасад " итератор, который делает то, что вам нужно здесь. Он будет хранить итераторы для всех ваших векторов или, альтернативно, извлекать итераторы для всех, кроме первого вектора, из смещения первого. Сложность заключается в том, к чему этот итератор обращает внимание: придумайте что-то вроде boost :: tuple и умело используйте boost :: tie. (Если вы хотите расширить эту идею, вы можете рекурсивно создавать эти типы итераторов, используя шаблоны, но вы, вероятно, никогда не захотите записывать тип этого - так что вам нужен либо c ++ 0x auto, либо функция-обертка для сортировки, которая принимает диапазоны)

Answer 6

Я думаю, что вам действительно нужно (но поправьте меня, если я ошибаюсь), это способ получить доступ к элементам контейнера в некотором порядке.

Вместо того, чтобы переставлять мою первоначальную коллекцию, я бы позаимствовал концепцию из базы данных: сохранить индекс, упорядоченный по определенному критерию. Этот индекс является дополнительным косвенным указателем, который предлагает большую гибкость.

Таким образом, можно генерировать несколько индексов в соответствии с различными членами класса.

using namespace std;

template< typename Iterator, typename Comparator >
struct Index {
    vector<Iterator> v;

    Index( Iterator from, Iterator end, Comparator& c ){
        v.reserve( std::distance(from,end) );
        for( ; from != end; ++from ){
            v.push_back(from); // no deref!
        }
        sort( v.begin(), v.end(), c );
    }

};

template< typename Iterator, typename Comparator >
Index<Iterator,Comparator> index ( Iterator from, Iterator end, Comparator& c ){
    return Index<Iterator,Comparator>(from,end,c);
}

struct mytype {
    string name;
    double number;
};

template< typename Iter >
struct NameLess : public binary_function<Iter, Iter, bool> {
    bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->name < t2->name; }
};

template< typename Iter >
struct NumLess : public binary_function<Iter, Iter, bool> {
    bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->number < t2->number; }
};

void indices() {

    mytype v[] =    { { "me"    ,  0.0 }
                    , { "you"   ,  1.0 }
                    , { "them"  , -1.0 }
                    };
    mytype* vend = v + _countof(v);

    Index<mytype*, NameLess<mytype*> > byname( v, vend, NameLess<mytype*>() );
    Index<mytype*, NumLess <mytype*> > bynum ( v, vend, NumLess <mytype*>() );

    assert( byname.v[0] == v+0 );
    assert( byname.v[1] == v+2 );
    assert( byname.v[2] == v+1 );

    assert( bynum.v[0] == v+2 );
    assert( bynum.v[1] == v+0 );
    assert( bynum.v[2] == v+1 );

}

Answer 7

Ответ ltjax - отличный подход, который на самом деле реализован в boost zip_iterator http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html

Он упаковывает в кортеж любые итераторы, которые вы предоставляете.

Затем вы можете создать собственную функцию сравнения для сортировки на основе любой комбинации значений итератора в вашем кортеже. Для этого вопроса это будет просто первый итератор в вашем кортеже.

Приятной особенностью этого подхода является то, что он позволяет сохранять память каждого отдельного вектора смежной (если вы используете векторы и это то, что вы хотите). Вам также не нужно хранить отдельный индексный вектор целых чисел.

Answer 8

Несколько более компактный вариант ответа xtofl, если вы просто хотите перебрать все свои векторы на основе одного вектора keys . Создайте вектор перестановки и используйте его для индексации других ваших векторов.

#include <boost/iterator/counting_iterator.hpp>
#include <vector>
#include <algorithm>

std::vector<double> keys = ...
std::vector<double> values = ...

std::vector<size_t> indices(boost::counting_iterator<size_t>(0u), boost::counting_iterator<size_t>(keys.size()));
std::sort(begin(indices), end(indices), [&](size_t lhs, size_t rhs) {
    return keys[lhs] < keys[rhs];
});

// Now to iterate through the values array.
for (size_t i: indices)
{
    std::cout << values[i] << std::endl;
}

Answer 9

Это было бы добавлением к ответу Конрада, так как это подход для варианта применения порядка сортировки к вектору на месте. Во всяком случае, так как редактирование не будет проходить, я помещу это здесь

Вот вариант на месте с немного более высокой временной сложностью, которая связана с примитивной операцией проверки логического значения. Дополнительная сложность пространства связана с вектором, который может быть зависящей от пространства реализацией, зависящей от компилятора. Сложность вектора может быть устранена, если сам данный порядок можно изменить.

Вот вариант на месте с немного более высокой временной сложностью, которая связана с примитивной операцией проверки логического значения. Дополнительная сложность пространства связана с вектором, который может быть зависящей от пространства реализацией, зависящей от компилятора. Сложность вектора может быть устранена, если сам данный порядок может быть изменен. Это пример того, что делает алгоритм. Если порядок равен 3 0 4 1 2, перемещение элементов, обозначенное индексами положения, будет равно 3 --- > 0; 0 --- & GT; 1; 1 --- & GT; 3; 2 --- & GT; 4; 4 --- & GT; 2.

template<typename T>
struct applyOrderinPlace
{
void operator()(const vector<size_t>& order, vector<T>& vectoOrder)
{
vector<bool> indicator(order.size(),0);
size_t start = 0, cur = 0, next = order[cur];
size_t indx = 0;
T tmp; 

while(indx < order.size())
{
//find unprocessed index
if(indicator[indx])
{   
++indx;
continue;
}

start = indx;
cur = start;
next = order[cur];
tmp = vectoOrder[start];

while(next != start)
{
vectoOrder[cur] = vectoOrder[next];
indicator[cur] = true; 
cur = next;
next = order[next];
}
vectoOrder[cur] = tmp;
indicator[cur] = true;
}
}
};

Answer 10

Вот относительно простая реализация с использованием сопоставление индексов между упорядоченным и неупорядоченным names который будет использоваться для сопоставления ages к заказанному names:

void ordered_pairs()
{
    std::vector<std::string> names;
    std::vector<int> ages;

    // read input and populate the vectors
    populate(names, ages);

    // print input
    print(names, ages);

    // sort pairs
    std::vector<std::string> sortedNames(names);
    std::sort(sortedNames.begin(), sortedNames.end());

    std::vector<int> indexMap;
    for(unsigned int i = 0; i < sortedNames.size(); ++i)
    {
        for (unsigned int j = 0; j < names.size(); ++j)
        {
            if (sortedNames[i] == names[j]) 
            {
                indexMap.push_back(j);
                break;
            }
        }
    }
    // use the index mapping to match the ages to the names
    std::vector<int> sortedAges;
    for(size_t i = 0; i < indexMap.size(); ++i)
    {
        sortedAges.push_back(ages[indexMap[i]]);
    }

    std::cout << "Ordered pairs:\n";
    print(sortedNames, sortedAges); 
}

Для полноты картины приведем функции populate() и print():

void populate(std::vector<std::string>& n, std::vector<int>& a)
{
    std::string prompt("Type name and age, separated by white space; 'q' to exit.\n>>");
    std::string sentinel = "q";

    while (true)
    {
        // read input
        std::cout << prompt;
        std::string input;
        getline(std::cin, input);

        // exit input loop
        if (input == sentinel)
        {
            break;
        }

        std::stringstream ss(input);

        // extract input
        std::string name;
        int age;
        if (ss >> name >> age)
        {
            n.push_back(name);
            a.push_back(age);
        }
        else
        {
            std::cout <<"Wrong input format!\n";
        }
    }
}

и:

void print(const std::vector<std::string>& n, const std::vector<int>& a)
{
    if (n.size() != a.size())
    {
        std::cerr <<"Different number of names and ages!\n";
        return;
    }

    for (unsigned int i = 0; i < n.size(); ++i)
    {
         std::cout <<'(' << n[i] << ", " << a[i] << ')' << "\n";
    }
}

И наконец, main() становится:

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>

void ordered_pairs();
void populate(std::vector<std::string>&, std::vector<int>&);
void print(const std::vector<std::string>&, const std::vector<int>&);

//=======================================================================
int main()
{
    std::cout << "\t\tSimple name - age sorting.\n";
    ordered_pairs();
}
//=======================================================================
// Function Definitions...

Answer 11

**// C++ program to demonstrate sorting in vector
// of pair according to 2nd element of pair
#include <iostream>
#include<string>
#include<vector>
#include <algorithm>

using namespace std;

// Driver function to sort the vector elements
// by second element of pairs
bool sortbysec(const pair<char,char> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
}

int main()
{
    // declaring vector of pairs
    vector< pair <char, int> > vect;

    // Initialising 1st and 2nd element of pairs
    // with array values
    //int arr[] = {10, 20, 5, 40 };
    //int arr1[] = {30, 60, 20, 50};
    char arr[] = { ' a', 'b', 'c' };
    int arr1[] = { 4, 7, 1 };

    int n = sizeof(arr)/sizeof(arr[0]);

    // Entering values in vector of pairs
    for (int i=0; i<n; i++)
        vect.push_back( make_pair(arr[i],arr1[i]) );

    // Printing the original vector(before sort())
    cout << "The vector before sort operation is:\n" ;
    for (int i=0; i<n; i++)
    {
        // "first" and "second" are used to access
        // 1st and 2nd element of pair respectively
        cout << vect[i].first << " "
             << vect[i].second << endl;

    }

    // Using sort() function to sort by 2nd element
    // of pair
    sort(vect.begin(), vect.end(), sortbysec);

    // Printing the sorted vector(after using sort())
    cout << "The vector after sort operation is:\n" ;
    for (int i=0; i<n; i++)
    {
        // "first" and "second" are used to access
        // 1st and 2nd element of pair respectively
        cout << vect[i].first << " "
             << vect[i].second << endl;
    }
    getchar();
    return 0;`enter code here`
}**

Answer 12

с лямбдами C ++ 11 и алгоритмами STL, основанными на ответах Конрада Рудольфа и Габриэле Д'Антоны:

template< typename T, typename U >
std::vector<T> sortVecAByVecB( std::vector<T> & a, std::vector<U> & b ){

    // zip the two vectors (A,B)
    std::vector<std::pair<T,U>> zipped(a.size());
    for( size_t i = 0; i < a.size(); i++ ) zipped[i] = std::make_pair( a[i], b[i] );

    // sort according to B
    std::sort(zipped.begin(), zipped.end(), []( auto & lop, auto & rop ) { return lop.second < rop.second; }); 

    // extract sorted A
    std::vector<T> sorted;
    std::transform(zipped.begin(), zipped.end(), std::back_inserter(sorted), []( auto & pair ){ return pair.first; }); 

    return sorted;
}

Answer 13

Очень многие задавали этот вопрос, и никто не придумал удовлетворительного ответа. Вот помощник std :: sort, который позволяет сортировать два вектора одновременно, принимая во внимание значения только одного вектора. Это решение основано на пользовательском RadomIt (случайный итератор) и работает непосредственно с исходными векторными данными, без временных копий, перестройки структуры или дополнительных индексов:

C ++, сортировка одного вектора на основе другого