значения мусора добавляется к вектору после операции сортировки

Question

У меня есть vector называемых ключей, для сортировки, которые у меня есть struct comp:

typedef std::list<std::vector<WayPoint> >::iterator pathIt; 
typedef std::pair<double, pathIt> Pair; 
struct comp{ 
    bool operator()(const Pair& lhs,const Pair& rhs) const 
    { 
     return lhs.first*1000000 <= rhs.first*1000000; 
    } 
}; 
std::list<std::vector<WayPoint> > paths; 
std::vector<Pair> keys; 

во время программы, у меня есть std::sort операция по keys:

std::sort(keys.begin(), keys.end(),comp()); 

Я распечатал контейнер (первое значение Pair элементов) до и после sort и заметил, что после сортировки добавляется некоторый мусор keys. Я делаю что-то не так в ? Примечание: Я вычислил в функции comp, умножая на 1000000, было бы хорошим способом сравнить удвоения в достаточно хорошей степени. правильно?

благодаря

UPDATE: Помимо проблемы с <= в компараторе, который должен был быть заменен <, мне нужно больше разъяснений относительно сравнения двойных значений: Может быть, я запутался, но почему так много вопросов в SO, анализирующих методы сравнения значений double? Если процессор может правильно сравнить удвоения, почему строго рекомендуется не использовать double в качестве ключа в std::map? Я смешиваю две несвязанные темы? было указанное выше умножение Unnecessary или A wrong way to implement a necessary requirement?

Answer 1

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

#include <cstdio> 

#include <vector> 
#include <list> 
#include <algorithm> 

struct WayPoint { 
    int x; 
    WayPoint(int x); 
}; 

typedef std::vector<WayPoint> Path; 
typedef std::list<Path> PathList; 
typedef std::pair<double,PathList::iterator> Pair; 
typedef std::vector<Pair> PairList; 

struct PairComp { 

    bool operator()(const Pair& lhs, const Pair& rhs) const { 
     return lhs.first < rhs.first; 
    } 

}; 

int main(void) { 

    PathList pathList{ 
     Path{WayPoint(1),WayPoint(2),WayPoint(3)}, 
     Path{WayPoint(4),WayPoint(5),WayPoint(6)}, 
     Path{WayPoint(7),WayPoint(8),WayPoint(9)}, 
     Path{WayPoint(10),WayPoint(11),WayPoint(12)} 
    }; 

    PathList::iterator pathListIt = pathList.begin(); 
    Pair pair1{7.0,pathListIt++}; 
    Pair pair2{2.0,pathListIt++}; 
    Pair pair3{14.0,pathListIt++}; 
    Pair pair4{9.0,pathListIt++}; 
    PairList pairList{pair1,pair2,pair3,pair4}; 

    std::sort(pairList.begin(), pairList.end(), PairComp()); 

    for (PairList::iterator it = pairList.begin(); it != pairList.end(); ++it) { 
     Pair& pair = *it; 
     std::printf("%f\n", pair.first); 
    } // end for 

} // end main() 

WayPoint::WayPoint(int x) : x(x) {} 

Выход:

2.000000 
7.000000 
9.000000 
14.000000 

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

Edit: Хорошо, вот модифицированная программа, которая использует неправильный оператор сравнения и гарантирует множество дубликатов:

#include <cstdio> 
#include <cstdlib> 

#include <vector> 
#include <list> 
#include <algorithm> 

struct WayPoint { 
    int x; 
    WayPoint(int x); 
}; 

typedef std::vector<WayPoint> Path; 
typedef std::list<Path> PathList; 
typedef std::pair<double,PathList::iterator> Pair; 
typedef std::vector<Pair> PairList; 

struct PairComp { 

    bool operator()(const Pair& lhs, const Pair& rhs) const { 
     return lhs.first <= rhs.first; 
    } 

}; 

double getKey(void); 

const int NUM = 30; 

int main(void) { 

    std::srand(time(0)); 

    PathList pathList; 
    PairList pairList; 

    pathList.push_back(Path({WayPoint(0)})); 
    PathList::iterator it = pathList.begin(); 
    pairList.push_back(Pair(getKey(), it)); 
    for (int i = 1; i < NUM; ++i) { 
     pathList.push_back(Path({WayPoint(i)})); 
     pairList.push_back(Pair(getKey(), ++it)); 
    } // end for 

    std::sort(pairList.begin(), pairList.end(), PairComp()); 

    for (PairList::iterator it = pairList.begin(); it != pairList.end(); ++it) { 
     Pair& pair = *it; 
     std::printf("%f\n", pair.first); 
    } // end for 

} // end main() 

WayPoint::WayPoint(int x) : x(x) {} 

double getKey(void) { 
    static double sample[] = {1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0}; 
    return sample[std::rand()%(sizeof(sample)/sizeof(sample[0]))]; 
} // end getKey() 

Это работает для меня, пример вывода:

1.000000 
1.000000 
1.000000 
1.000000 
2.000000 
2.000000 
2.000000 
2.000000 
2.000000 
2.000000 
3.000000 
3.000000 
3.000000 
3.000000 
4.000000 
4.000000 
4.000000 
4.000000 
5.000000 
5.000000 
5.000000 
5.000000 
5.000000 
5.000000 
6.000000 
6.000000 
7.000000 
8.000000 
8.000000 
8.000000 

Edit: Aha! Я много раз запускал модифицированную версию тестовой программы и в итоге получил segfault в PairComp::operator(), как вызвано от std::sort(). Вот полная трассировка от БГДА (предупреждение: многословный C++ трассировка следующим образом):

Program received signal SIGSEGV, Segmentation fault. 
0x0000000100402144 in PairComp::operator()(std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > const&, std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > const&) const() 
(gdb) bt 
#0 0x0000000100402144 in PairComp::operator()(std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > const&, std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > const&) const() 
#1 0x0000000100401f87 in bool __gnu_cxx::__ops::_Iter_comp_iter<PairComp>::operator()<__gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, __gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > > >(__gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, __gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >)() 
#2 0x00000001004042ea in __gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > > std::__unguarded_partition<__gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, __gnu_cxx::__ops::_Iter_comp_iter<PairComp> >(__gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, __gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, __gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, __gnu_cxx::__ops::_Iter_comp_iter<PairComp>)() 
#3 0x0000000100404852 in __gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > > std::__unguarded_partition_pivot<__gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, __gnu_cxx::__ops::_Iter_comp_iter<PairComp> >(__gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, __gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, __gnu_cxx::__ops::_Iter_comp_iter<PairComp>)() 
#4 0x00000001004041cd in void std::__introsort_loop<__gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, long, __gnu_cxx::__ops::_Iter_comp_iter<PairComp> >(__gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, __gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, long, __gnu_cxx::__ops::_Iter_comp_iter<PairComp>)() 
#5 0x00000001004041f0 in void std::__introsort_loop<__gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, long, __gnu_cxx::__ops::_Iter_comp_iter<PairComp> >(__gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, __gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, long, __gnu_cxx::__ops::_Iter_comp_iter<PairComp>)() 
#6 0x0000000100404b9e in void std::__sort<__gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, __gnu_cxx::__ops::_Iter_comp_iter<PairComp> >(__gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, __gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, __gnu_cxx::__ops::_Iter_comp_iter<PairComp>)() 
#7 0x00000001004049e4 in void std::sort<__gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, PairComp>(__gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, __gnu_cxx::__normal_iterator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >*, std::vector<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > >, std::allocator<std::pair<double, std::_List_iterator<std::vector<WayPoint, std::allocator<WayPoint> > > > > > >, PairComp)() 
#8 0x00000001004012e8 in main() 

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

Я предполагаю, что общий урок здесь заключается в том, что, когда вы нарушаете требование, от которого зависит слепой (доверительный) алгоритм, все ставки отключены. Он может вводить данные об мусоре, он может segfault или может дать вам правильный результат. Вы должны быть осторожны.

Это была забавная проблема для работы, +1 для вопроса. :)

Answer 2

Неправильная функция компаратора. Он вычисляет меньше или равно. Компаратор должен строго рассчитывать меньше. Если ваш вектор содержит несколько элементов с одинаковым значением, это может привести к ошибкам.

Я не знаю, является ли это источником вашего мусора, но это первое, что я исправит. Дайте мне знать в комментарии, если это не поможет.

Кроме того, как указано в комментариях, умножение в компараторе совершенно не нужно.