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

Question

Я пытался запустить приведенный ниже код. То, что я нахожу, - то, что есть разница в результатах. Я понимаю, что существует проблема с механизмом упорядочения, используемым в функциональности компаратора. Что я в основном ищу: 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;
}

Answer 1

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

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

Answer 2

Смотрите эту ссылку для более подробной информации о 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; 
    }
};

Это гарантирует, что равные элементы считаются эквивалентными. Обратите внимание, что это подробно обсуждается в Effective STL, "Пункт 19. Понять разницу между равенством и эквивалентностью".

Answer 3

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

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

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

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

Answer 4

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