Std :: multiset, отслеживать позиции вставленных элементов - PullRequest
Новая
       45

Std :: multiset, отслеживать позиции вставленных элементов

2 голосов
/ 14 февраля 2012

Могу ли я каким-то образом перегрузить любой из операторов std :: multiset (как вы делаете с '()' для создания пользовательской функции comapre), чтобы при замене двух элементов в мультимножестве связывались еще два элемента из другого вектора к тем?

Я имею в виду, я на самом деле хочу вставить, скажем, elemetns {a, b, c, d, e} в мультимножество, но я также хочу отслеживать их положение внутри мультимножества, не используя .find ( ). Поэтому я подумал о создании еще одного вектора pos, где pos [k] - это позиция элемента k в мультимножестве.

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

Я точно не знаю, как мультимножество изменяет / меняет элемент для их сортировки, но могу ли я как-то переопределить это вместо: 

swap(a,b);

У меня будет что-то вроде. 

swap(pos[a],pos[b]);
swap(a,b)

И если у вас есть какие-либо другие идеи о том, как я мог бы отслеживать положение элемента внутри мультимножества, без использования .find () (который имеет O (N) сложность для равных элементов) было бы здорово!

EDIT

Кроме того, я предполагаю, что мне нужно что-то изменить, чтобы при вставке нового элемента (n) он получил правильную инициализацию для pos[n], прежде чем будут произведены какие-либо "перестановки".

Ответы [ 2 ]

2 голосов
/ 14 февраля 2012

В качестве альтернативы вы можете обратиться к структуре статистики заказов , которая имеет следующие функциональные возможности, работающие во время O (log n):

  • Вставить
  • Удалить
  • Найти преемника
  • Найти предшественника
  • Найти по ключу
  • Найти по индексу
  • Сообщите индекс элемента (в O (1), если у вас уже есть итератор)

Другими словами, вы можете запросить у дерева элементы по позиции или по ключу,и может заставить дерево сказать вам, в каком положении находится данный элемент.Он также хранит элементы в отсортированном порядке (например, std::multiset) и может быть легко обработан для дублирования элементов.Короче говоря, его можно использовать как std::multiset, который эффективно поддерживает индексирование.

Кажется, что это может быть лучшим подходом, хотя, к сожалению, деревья статистики заказов отсутствуют в стандартной библиотеке C ++.Вам нужно найти стороннюю библиотеку для них.

Надеюсь, это поможет!

0 голосов
/ 14 февраля 2012

Вы не можете переопределить их, не наследуя от multiset, что не рекомендуется . Так что вам нужна логика для отслеживания положения элементов в вашем multiset.

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

std::multiset<your_item_type> it = your_set.insert(item);
std::size_t new_element_pos = it != your_set.begin() ? pos[*(it--)] + 1
                                                     : pos[*(it++)] - 1

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

Чтобы отследить перестановки, вы можете просто специализировать std::swap для своего типа, и когда два элемента меняются местами, вы меняете их позиции в векторе позиций.

...