C ++ Stl Set Поведение

Question

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

c++equivalence set stl strict-weak-ordering

Решение

Другие решения

Видеть это ссылка для более подробной информации о 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. Понять разницу между равенством и эквивалентностью».

2

Проблема, скорее всего, потому что ваше сравнение не реализует строгий слабый порядок. Механизм внутреннего упорядочения на съемочной площадке опирается на это. Вы можете получить SWO, изменив сравнение на менее чем:

struct Comparator {
bool operator()( const int& a, const int& b ) const {
return ( a < b );
}
};

С другой стороны, std::set будет использовать этот критерий сравнения по умолчанию, поэтому вам не нужно его указывать.

В моем ответе есть некоторая информация этот вопрос (и миллионы других вопросов SO).

2

Вы получаете разные результаты в двух случаях, потому что вы inserting in different ways, В случае 1 вы вставляете элемент 2 десять раз. В этом случае, когда вы вставляете целое число 2 после первого раза, ваш Comparator() функция будет вызвана, чтобы решить, куда вставить. В другом случае вы вставляете диапазон. Здесь вызываемая функция принимает первый аргумент, i, e customSet.begin() и проверяет это с другим аргументом я, е customSet.end(), если эти два не равны, то вставляется только элемент, иначе элемент не будет вставлен.

0

Источник

Accepted Answer

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 не будет вставлен.

Поскольку ваше сравнение не является строгим, этот тест на уникальность может не пройти; так что вы можете получить дубликат записи. Или что-то еще может случиться — поведение не определено.

2