C ++ Stl Set Поведение
Я пытался запустить приведенный ниже код. То, что я нахожу, — то, что есть разница в результатах. Я понимаю, что есть проблема с механизмом упорядочения, используемым в функциональности компаратора. Что я в основном ищу:
1) Как Set хранит данные внутри.
2) Как я могу решить эту проблему или лучший способ скопировать данные в другой набор.
3) Как именно порядок создает эту проблему.
#include <iostream>
#include <set>
using namespace std;
struct Comparator {
bool operator()( const int& a, const int& b ) {
if( a <= b )
return true;
else
return false;
}
};
int main()
{
set< int, Comparator > customSet;
for( unsigned k = 0, index = 2; k < 10; ++k ) {
customSet.insert( index );
}
set< int, Comparator >::iterator iter = customSet.begin();
for(; iter != customSet.end(); ++iter ) {
cout<<*iter<<endl;
}
cout<<"---------------------------------"<<endl;
set< int, Comparator > tempCustomSet ;//= customSet;
tempCustomSet.insert( customSet.begin(), customSet.end() );
iter = tempCustomSet.begin();
for(; iter != tempCustomSet.end(); ++iter ) {
cout<<*iter<<endl;
}
return 0;
}
Решение
1) Как Set хранит данные
Единственными требованиями являются следующие элементы:
- заказано по данным компаратора, так что если
Comp(a,b), затемaпоявляется раньшеbпри итерации множества; - уникальны, поэтому нет четких элементов, для которых
Comp(a,b)а такжеComp(b,a)держать.
и что операции отвечают определенным требованиям сложности.
На практике они обычно хранятся в бинарном дереве поиска; но это не имеет значения для пользователя.
2) Как я могу решить эту проблему или лучший способ скопировать данные в другой набор
Чтобы соответствовать требованиям, компаратор должен быть строгий слабый порядок, лайк <, чтобы Comp(a,a) всегда ложно, а не как строгий порядок <=, поскольку < по умолчанию, это означает, что вам вообще не нужен пользовательский компаратор.
3) Как именно заказ создает эту проблему
Обратите внимание, что ваш первый цикл вставляет значение 2 десять раз; Я не уверен, является ли это намерением или нет.
Учитывая требуемый строгий порядок, insert(b) может искать точку вставки, находя первый элемент a такой, что Comp(a,b) ложно; то есть первый элемент, который b не должен прийти после. Затем он проверит уникальность, проверив Comp(b,a), Если оба являются ложными, то это означает, что эти два значения эквивалентны, поэтому b не будет вставлен.
Поскольку ваше сравнение не является строгим, этот тест на уникальность может не пройти; так что вы можете получить дубликат записи. Или что-то еще может случиться — поведение не определено.
Другие решения
Видеть это ссылка для более подробной информации о std::set, Реализация не должна касаться вас (они могут отличаться от платформы к платформе), поскольку интерфейс и гарантии сложности — все, что имеет значение для Стандарта. Типичные реализации используют красно-черно-деревья.
Вы должны сделать свой Comparator использование operator< и не operator<=, Причина в том, что std::set будет считать элементы эквивалентными, если !Comparator(a, b) && !Comparator(b, a) оценивает true (т. е. ни один строго не меньше, чем другой).
Но с <=, у тебя есть a <= a равно true, чтобы !(a<=a) && !(a<=a) дает false для равных элементов. Тогда как с < у тебя есть a < a равно false так !(a<a) && !(a<a) дает true,
Право на то, чтобы сделать это:
struct Comparator
{
bool operator()(int const& lhs, int const& rhs) const
{
return lhs < rhs;
}
};
Это гарантирует, что равные элементы считаются эквивалентными. Обратите внимание, что это подробно обсуждается в Эффективный STL, «Пункт 19. Понять разницу между равенством и эквивалентностью».
Проблема, скорее всего, потому что ваше сравнение не реализует строгий слабый порядок. Механизм внутреннего упорядочения на съемочной площадке опирается на это. Вы можете получить SWO, изменив сравнение на менее чем:
struct Comparator {
bool operator()( const int& a, const int& b ) const {
return ( a < b );
}
};
С другой стороны, std::set будет использовать этот критерий сравнения по умолчанию, поэтому вам не нужно его указывать.
В моем ответе есть некоторая информация этот вопрос (и миллионы других вопросов SO).
Вы получаете разные результаты в двух случаях, потому что вы inserting in different ways, В случае 1 вы вставляете элемент 2 десять раз. В этом случае, когда вы вставляете целое число 2 после первого раза, ваш Comparator() функция будет вызвана, чтобы решить, куда вставить. В другом случае вы вставляете диапазон. Здесь вызываемая функция принимает первый аргумент, i, e customSet.begin() и проверяет это с другим аргументом я, е customSet.end(), если эти два не равны, то вставляется только элемент, иначе элемент не будет вставлен.
detector