Блог

Следующий код представляет собой упрощенный пример, который создает проблему.

В набор вставляется несколько строк (char *), многие из которых не являются уникальными. Должны быть обнаружены повторяющиеся строки и должен быть возвращен указатель на вставленный оригинал; однако иногда этого не происходит, и уже вставленная строка вставляется снова, как если бы ее еще не было.

Результирующий набор должен состоять из: «aa», «bb», «cc». Вывод показывает, что набор заканчивается: «bb», «cc», «aa», «bb». Изменение того, какая строка вставляется первой, похоже, изменяет, какой дубликат «разрешен».

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

Использование компаратора по умолчанию и строк без префикса работает, как и ожидалось, но при этом сравниваются только указатели; добавление префикса к строкам приводит к появлению уникальных указателей, и все строки вставляются.

 #include <iostream>
#include <set>
#include <cstring>

using std::cout;
using std::endl;
using std::set;
using std::pair;

typedef set<const char*>::const_iterator set_iter;

struct cmp_op {
    int operator() (const char* x,const char* y) const {
        int r = strcmp(x,y);
        //cout << "cmp: " << x << ((r)?((r>0)?" > ":" < "):" == ") << y << endl;
        return r;
    }
};

int main() {
    //first char ignored, just ensures unique pointers
    const char* a[] = {"1bb","2aa","3aa","4bb","5cc","6aa","7bb","8cc","9bb"};
    const size_t n = sizeof(a)/sizeof(*a);

    //using custom (strcmp) comparator
    set<const char*,cmp_op> s;

    for (int i=0; i<n;   i) {
        cout << "insert(" << (void*)(a[i] 1) << "=" << (a[i] 1) << ")" << endl;
        pair<set_iter,bool> r = s.insert(a[i] 1);
        if (r.second) cout << "OK";
        else {cout << "dup => " << (void*)(*r.first) << "=" << (*r.first);}
        cout << endl << endl;
    }

    cout << n << " strings, " << s.size() << " unique:" << endl;
    set_iter it=s.begin();
    cout << (void*)(*it) << "=" << *it;
    while (  it!=s.end())
        cout << ", " << (void*)(*it) << "=" << *it;
    cout << endl;

    return 0;
}
  

Я использую MinGW с GCC 4.8.1 в Windows; тестирование с Ubuntu дает тот же результат.

Ваша функция сравнения не реализует строгий слабый порядок, поскольку она возвращается true всякий раз, когда LHS не равно RHS. Вам нужно изменить логику, чтобы возвращать true, когда один «меньше» другого. Это один из примеров, который кажется естественным выбором:

 return r < 0;
  

Обратите внимание, что для прояснения намерения было бы лучше вернуть bool :

 bool operator() (const char* x, const char* y) const 
{
  return strcmp(x, y) < 0;
}