С ++ сортировка по вектору с использованием объекта функции

Question

Я пытаюсь отсортировать вектор v1, используя другой вектор v2.Я не могу обернуть голову вокруг этой ошибки:

завершить вызов после выброса экземпляра 'std :: out_of_range'
what (): vector :: _ M_range_check
Прервать прерывание

при выполнении этого кода:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Comp
{
    public:
        Comp(vector<double>& inVec): _V(inVec) {}
        bool operator()(int i, int j) {return (_V.at(i)<_V.at(j));}
    private:
        vector<double> _V;
};

int main(int argc, char** argv)
{
    double x1[] = {90.0, 100.0, 80.0};
    double x2[] = {9.0, 3.0, 1.0};
    vector<double> v1(x1,x1+3);
    vector<double> v2(x2,x2+3);

    sort(v1.begin(), v1.end(), Comp(v2));  // sort v1 according to v2

    for(unsigned int i=0; i<v1.size(); i++)
    {
        cout << v1.at(i) << " " << v2.at(i) << endl;
    }

    return 0;
}

v1 и v2 имеют одинаковый размер.Почему ошибка out_of_range?

Заранее спасибо за любые указатели.

Answer 1

Я считаю, что ваша проблема в этой строке:

bool operator()(int i, int j) {return (_V.at(i)<_V.at(j));}

Проблема в том, что когда алгоритм std::sort использует пользовательский обратный вызов, он передает фактические значения, хранящиеся в vector в определенных местоположениях, а не индексы этих местоположений в vector. В результате при звонке

sort(v1.begin(), v1.end(), Comp(v2));  // sort v1 according to v2

Компаратор Comp, который вы написали, будет передан в качестве параметров значениям, хранящимся в векторе v1, и затем попытается проиндексировать эти позиции в векторе v2. Поскольку значения в v1 больше, чем размер v2, вызов _V.at(i) вызовет исключение out_of_range.

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

Answer 2

Размер v1 равен 3, но вы используете каждое значение v2 в качестве индекса v1. И поскольку v2 имеет одно значение 9, которое больше, чем размер v1, то это дает ошибку std::out_of_range здесь:

bool operator()(int i, int j) {return (_V.at(i)<_V.at(j));}

std::vector::at функция выдает std::out_of_range исключение индекса, переданного ей в качестве аргумента, больше, чем размер вектора. То есть индекс должен быть меньше vector::size().

Answer 3

Хорошо, теперь вы, вероятно, знаете о том факте, что i и j являются фактическими значениями, содержащимися в vector, а не в индексах. Для этого есть веская причина: сортировка - это значения, а не индексы. Обратите внимание, что вы передаете итераторы методу sort, поэтому он не может извлечь индекс для вас. Конечно, вы можете получить индекс относительно первого итератора, но для этого нет никаких оснований.

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

v1 = {20,10}; v2 = {2,1}

Я тайно предполагаю, что вы хотите следующий вывод:

v1 = {10, 20}

право? Теперь представьте, что вы вызываете функцию сортировки, и я делаю следующие шаги:

• v2[0] < v2[1] ложно, поэтому swap(&v1[0], &v1[1])

Это отсортировано, не так ли? Но подождите, я сумасшедшая функция сортировки, поэтому я хочу убедиться, что она отсортирована, поэтому я делаю следующее:

• v2[0] < v2[1] ложно, swap(&v1[0], &v1[1])

И снова:

• v2[0] < v2[1] ложно, swap(&v1[0], &v1[1])

и снова, снова, снова ...

Вы видите проблему? У функции сортировки есть некоторые требования, и вы наверняка нарушаете фундаментальную.

Я подозреваю, что вам нужен совершенно другой контейнер (может быть std::map с ключами от vec1 и значениями от vec2) или, по крайней мере, что-то вроде vector< pair<double, double> >, так что вы можете легко сортировать по первому или второму значению. Если нет, рассмотрите возможность создания vector со значениями в диапазоне [0, v2.size()), сортировку с использованием компаратора (значения равны индексам, поэтому все будет в порядке), а затем выведите правильные значения из v1. Этот код отлично работает:

vector<size_t> indices;
for(size_t i =0; i < v1.size(); ++i)
{
  indices.push_back(i);
}

// yes, it works using your original comparator
sort(indices.begin(), indices.end(), Comp(v2));

for(size_t i =0; i < indices.size(); ++i)
{
    cout << v1.at(indices[i]) << " " << v2.at(indices[i]) << endl;
}

Answer 4

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

Вот как вы можете решить эту проблему:

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

using namespace std;

typedef pair<double, double> Zipped; // Represent an element of two lists
                                     // "zipped" together

// Compare the second values of two pairs
bool compareSeconds ( Zipped i, Zipped j )
{
    return i.second < j.second;
}

int main ( int argc, char **argv )
{
    double x1[] = { 90, 100, 80 };
    double x2[] = { 9, 3, 1 };

    vector<double> v1(x1, x1 + 3);
    vector<double> v2(x2, x2 + 3);

    vector<Zipped> zipped(v1.size()); // This will be the zipped form of v1
                                      // and v2

    for ( int i = 0; i < zipped.size(); ++i )
    {
        zipped[i] = Zipped(v1[i], v2[i]);
    }

    sort(zipped.begin(), zipped.end(), &compareSeconds);

    for ( int i = 0; i < zipped.size(); ++i )
    {
        cout << zipped[i].first << " " << zipped[i].second << endl;
    }

    for ( int i = 0; i < v1.size(); ++i )
    {
        v1[i] = zipped[i].first;
    }

    // At this point, v1 is sorted according to v2

    return 0;
}