Bối rối SegFault liên quan đến thuật toán sắp xếp STL

Question

Tôi đang cố gắng tạo lại chương trình trong Cột 15 của ngọc trai lập trình bằng cách sử dụng STL. Tôi đang cố gắng tạo ra một mảng hậu tố bằng cách sử dụng một chuỗi và một vectơ của các chỉ mục. Tôi ghi lại danh sách các từ mà tôi đã đọc trong một chuỗi được gọi là đầu vào hoạt động như một danh sách các từ được phân cách bởi '' mà tôi đọc từ stdin ở đầu chương trình. Mọi thứ hoạt động như mong đợi cho đến khi tôi nhận được phần sắp xếp của mã. Tôi muốn sử dụng thuật toán sắp xếp của STL, nhưng tôi hoàn toàn bối rối tại một lỗi seg mà tôi dường như đang tạo ra.

tôi có:

vector<unsigned int> words; 

và biến toàn cầu

string input; 

tôi xác định tùy chỉnh của tôi so sánh chức năng:

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; 
} 

Khi tôi chạy mã:

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

Chương trình thoát trơn tru.

Tuy nhiên, khi tôi chạy mã:

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

tôi tạo ra một segfault sâu bên trong STL.

Các GDB back-trace mã trông như thế này:

#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 

tôi có mã tương tự trong một chương trình khác, nhưng trong chương trình mà tôi đang sử dụng một vector thay vì vector. Đối với cuộc sống của tôi, tôi không thể tìm ra những gì tôi đang làm sai. Cảm ơn!

Answer 1

Rất có thể trình so sánh của bạn không đáp ứng được thứ tự yếu nghiêm ngặt; ví dụ: vi phạm độ nhạy vì một số giá trị tồn tại sao cho A < B, B < C và C < A. Dưới đây là requirements. Tôi không nhìn thấy nó ra khỏi đầu của tôi, nhưng tôi sẽ tiếp tục nhìn chằm chằm vào nó trong một vài phút.