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

Question

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

Псевдо код:

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

Подход friol хорош в сочетании с вашим. Во-первых, построить вектор, состоящий из чисел 1 ... п, наряду с элементами из вектора диктующих порядок сортировки:

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

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

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

Answer 3

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

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

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

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 4

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

Answer 5

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 6

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

Answer 7

ltjax является большой подход - который на самом деле реализуется в zip_iterator BOOST в http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html

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

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

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

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 ---> 1; 1 ---> 3; 2 ---> 4; 4 ---> 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

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

C++, Sort One Vector Based On Another One