& Quot; обратное & Quot; ассоциативный контейнер?

Question

& Quot; обратное & Quot; ассоциативный контейнер?

существует ли в stl своего рода «обратный» ассоциативный контейнер или вообще?
Например, я хотел бы иметь контейнер, в котором один и тот же элемент является общим для набора ключей.

Допустим, мой ключ intтогда я бы, например:

container.at(3) -> some object A
container.at(4) -> same object A
container.at(1) -> other object B

Этот контейнер должен (в идеале) иметь ту же сложность, что и std :: map для различных операций. Это возможно?

Я думал об использовании сначала std::map<int, T*> где несколько индексов указывают на один и тот же объект, но затем при удалении элемента с карты время выполнения составляет O (n), потому что вам нужно будет проверить другие элементы, чтобы увидеть, нужно ли удалять T object

Уже есть этот вид контейнера «изначально» в STL или в Boost?

редактировать :
некоторые примеры использования:

container<int, myClass> myContainer;
myClass obj(...); //new object
myContainer.insert(3, obj); //insert object for specific key
myContainer.insert(2, obj); //insert same object for specific key, since both objects would compare equal we would actually not "insert" a new object but have it shared by both keys
myContainer.duplicate_object(2,5); //key 5 also has the same object as key 2 (and 3)
myContainer.getAllKeys(2); //would return 2,3 and 5 since they all reference the same object as key 2
myContainer.removeKey(3);
myContainer.removeKey(2);
myContainer.removeKey(5); //would destroy the object here, not before

3

c++std stl

Решение

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

Вы можете посмотреть на Boost.MultiIndex; описание говорит:

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

0

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

Там нет стандартного контейнера, который делает это. Но если вы хотите написать один самостоятельно, вы можете сделать это, поддерживая две внутренние структуры данных:

станд :: Карта который сопоставляет ключи со значениями
Второй станд :: MultiMap который сопоставляет значения с наборами ключей, указывающих на них

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

-1

Источник

Accepted Answer

Вы могли бы использовать

std::map<int,std::shared_ptr<myclass>>

В C ++ 11 это часть стандарта. В противном случае используйте общие указатели, предоставляемые библиотекой Boost.

Идея разделяемого указателя состоит в том, что он внутренне хранит счетчик ссылок, то есть он отслеживает, сколько раз была сделана копия указателя. Когда вы удаляете запись на карте, деструктор объекта общего указателя обеспечит уменьшение счетчика. Как только он достигнет нуля, объект будет удален.

(Изменить 🙂 Чтобы сделать ответ более полным, приведем несколько примеров использования:

#include <map>
#include <memory>

struct myclass
{

};int main()
{
std::map<int,std::shared_ptr<myclass>> mymap;

/* std::make_shared() calls the constructor and creates a shared_ptr: */
std::shared_ptr<myclass> object1 { std::make_shared<myclass>() };
std::shared_ptr<myclass> object2 { std::make_shared<myclass>() };
std::shared_ptr<myclass> object3 { std::make_shared<myclass>() };

mymap[1] = object1;
mymap[2] = object2;
mymap[3] = object3;
mymap[4] = object2;
mymap[5] = object1;

mymap.erase(2); // erases the (2,object2) entry
// therefore, decreases the counter
// for object2
// but (4,object2) is still intact

return 0;
}

6