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

Ответ 1

friol хорош в сочетании с вашим. Сначала постройте вектор, состоящий из чисел 1... 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;
}

Ответ 2

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

Ответ 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}

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

Ответ 4

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

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

Ответ 5

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

Ответ 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 );

}

Ответ 7

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

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

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

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

Ответ 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;
}

Ответ 9

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

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

Вот вариант на месте с немного более высокой временной сложностью, который связан с примитивной операцией проверки булева. Дополнительная пространственная сложность представляет собой вектор, который может быть пространственной эффективностью, зависящей от компилятора. Сложность вектора может быть устранена, если данный порядок может быть изменен. Это пример того, что делает алгоритм. Если порядок равен 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;
}
}
};

Ответ 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...

Ответ 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`
}**

Ответ 12

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

template< typename T, typename U >
std::vector<T> sortVecAByVecB( std::vector<T> & a, std::vector<U> & 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] ); // zip the two vectors (A,B)

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

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

    return sorted;
}

Ответ 13

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

С++, Сортировка одного вектора на другом