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

Question

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

Я имею в виду, я действительно хочу вставить, например, 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

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

Answer 1

Вы не можете переопределить их, не наследуя от multiset, который is not recommended. Так что вам нужна логика для отслеживания позиций элементов в вашем 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 для вашего типа, а при замене двух элементов вы поменяете свои позиции в векторе положения.

Answer 2

В качестве альтернативы, вы можете захотеть взглянуть на структуру данных order statistic tree, который имеет следующие функциональные возможности всех работающих в O (журнал N) Время:

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

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

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

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