SegFault desconcertante que implica el algoritmo de ordenación STL

Question

Estoy tratando de volver a crear el programa en la Columna 15 de perlas de programación utilizando el STL. Estoy tratando de crear una matriz de sufijos usando una cadena y un vector de índices. Grabo la lista de palabras que leo en una cadena llamada entrada que actúa como una lista de palabras separadas por '' que leo de stdin al comienzo del programa. Todo funciona como se espera hasta que llegue a la parte de ordenación del código. Me gustaría utilizar el algoritmo de ordenamiento de STL, pero estoy completamente perplejo ante un fallo seg que parece estar creando.

que tengo:

vector<unsigned int> words; 

y variable global

string input; 

defino mi costumbre comparar la función:

bool wordncompare(unsigned int f, unsigned int s) { 
    int n = 2; 

    while (((f < input.size()) && (s < input.size())) 
     && (input[f] == input[s])) { 
    if ((input[f] == ' ') && (--n == 0)) { 
     return false; 
    } 

    f++; 
    s++; 
    } 

    return true; 
} 

Cuando ejecuto el código:

sort(words.begin(), words.end()); 

El programa sale sin problemas.

Sin embargo, cuando ejecuto el código:

sort(words.begin(), words.end(), wordncompare); 

genero una violación de segmento en lo profundo de la STL.

El código de back-BGF traza se parece a esto:

#0 0x00007ffff7b79893 in std::string::size() const() from /usr/lib/gcc/x86_64-pc-linux-gnu/4.3.4/libstdc++.so.6 
#1 0x0000000000400f3f in wordncompare (f=90, s=0) at text_gen2.cpp:40 
#2 0x000000000040188d in  std::__unguarded_linear_insert<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, unsigned int, bool (*)(unsigned int, unsigned int)> (__last=..., __val=90, __comp=0x400edc <wordncompare(unsigned int, unsigned int)>) 
at /usr/lib/gcc/x86_64-pc-linux-gnu/4.3.4/include/g++-v4/bits/stl_algo.h:1735 
#3 0x00000000004018df in std::__unguarded_insertion_sort<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, bool (*)(unsigned int, unsigned int)> (__first=..., __last=..., __comp=0x400edc <wordncompare(unsigned int, unsigned int)>) 
at /usr/lib/gcc/x86_64-pc-linux-gnu/4.3.4/include/g++-v4/bits/stl_algo.h:1812 
#4 0x0000000000402562 in std::__final_insertion_sort<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, bool (*)(unsigned int, unsigned int)> (__first=..., __last=..., __comp=0x400edc <wordncompare(unsigned int, unsigned int)>) 
at /usr/lib/gcc/x86_64-pc-linux-gnu/4.3.4/include/g++-v4/bits/stl_algo.h:1845 
#5 0x0000000000402c20 in std::sort<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, bool (*)(unsigned int, unsigned int)> (__first=..., __last=..., __comp=0x400edc <wordncompare(unsigned int, unsigned int)>) 
at /usr/lib/gcc/x86_64-pc-linux-gnu/4.3.4/include/g++-v4/bits/stl_algo.h:4822 
#6 0x00000000004012d2 in main (argc=1, args=0x7fffffffe0b8) at text_gen2.cpp:70 

Tengo un código similar en otro programa, pero en ese programa que estoy utilizando un vector en lugar de vectores. Por mi vida no puedo entender lo que estoy haciendo mal. ¡Gracias!

Answer 1

Lo más probable es que su comparador no satisfaga estrictos pedidos débiles; por ejemplo, viola la transitividad porque existe un anillo de valores tal que A < B, B < C y C < A. Aquí están los requirements. No lo veo fuera de mi cabeza, pero voy a seguir mirándolo por unos minutos.