С++ как std::set обрабатывает динамическое упорядочение элементов

У меня есть набор, объявленный с моей собственной функцией comp:

set<int, my_comp> my_set;

Функция сравнения использует некоторые данные, хранящиеся в другом месте, чтобы решить, какое целое число больше. Если указанные данные изменяются, меняется и порядок элементов множества.

Как set справляется с этим? Если я знаю, что относительное положение int могло измениться, нужно ли мне удалять и снова вставлять его?

Подробности: в частности, my_comp использует целые числа в качестве индексов для доступа к вектору и сравнивает значения, содержащиеся в векторе. Указанные значения обязательно изменятся.


c++ set stdset
person user2460978    schedule 01.10.2013    source источник
comment
Нет простого решения. Насколько std::set может судить, даже самое незначительное изменение порядка может привести к перебалансировке дерева до корневого узла. Пользовательское красно-черное дерево может сэкономить время, не перезагружая память старого узла, но это все.   -  person MSalters    schedule 02.10.2013

Ответы (1)


arrow_upward
1
arrow_downward

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

Функция сравнения должна быть моделью строгого слабого упорядочения:

Строгий слабый порядок обладает следующими свойствами. Для всех x, y и z в S,

  • Для всех x это не тот случай, когда x ‹ x (иррефлексивность).
  • Для всех x, y, если x ‹ y, то это не тот случай, когда y< /em> ‹ x (асимметрия).
  • Для всех x, y и z, если x ‹ y и y ‹ z, затем x ‹ z (транзитивность).
  • Для всех x, y и z, если x несравнимо с y , а y несравнимо с z, то x несравнимо с z (транзитивность несравнимости).

Возможно, лучшим решением было бы отсортированное std::vector вместе с std::sort (для сортировки), std::lower_bound (для поиска и вставки элементов), std::inplace_merge (для вставки элементов).

person dalle    schedule 01.10.2013
comment
Я предполагаю, что функция сравнения используется только при вставке и удалении элементов. Следовательно, могу ли я по-прежнему использовать набор, но перемещать элементы вручную, удаляя и снова вставляя их? - person user2460978; 02.10.2013
comment
С вектором у меня было бы линейное время для перемещения элементов. Мне нужны логарифмические затраты набора. - person user2460978; 02.10.2013
comment
О скольких элементах идет речь? Перемещение элементов в std::vector<int> происходит не так уж и медленно. - person dalle; 02.10.2013
comment
@ user2460978: Мне нужно проверить, чтобы быть уверенным на 100%, но я считаю, что это может понадобиться и для других операций. Как очевидный пример, размещение элементов в наборе. - person MSalters; 02.10.2013
comment
@dalle: от 100 до 300. Но это чрезвычайно важная операция. - person user2460978; 02.10.2013
comment
@MSalters: ты прав! Я запомню это. Мое намерение сейчас состоит в том, чтобы сохранить набор согласованным, удаляя и повторно вставляя элементы, чье «величие» могло измениться. - person user2460978; 02.10.2013