C ++ ассоциативный контейнер с двумя критериями поиска

Question

Я ищу контейнер для хранения моих объектов класса, называемый Link, в котором есть переменная-член: "std :: string linkID". Размер контейнера может достигать нескольких миллионов, поэтому предпочтительнее быстрый поиск. 1-Позже мне нужно искать контейнер, используя linkID 2-но, по ряду причин, также важен порядок добавления объектов.

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

Спасибо Вахид

Answer 1

Для меня это выглядит как идеальный вариант использования для boost :: multi_index_container

ваше объявление типа должно выглядеть примерно так (не проверено)Решение опубликовано Фрерих Раабе.Но я думаю с меньшими подводными камнями и, вероятно, более оптимизирован.Прочитайте учебник на странице поддержки, чтобы узнать, как получить доступ к элементам, хранящимся в s.

Ваш комментарий ...

На самом деле, я разрабатываю уже существующий проект, в котором они использовали std :: vector только для хранения элементов (как вы указали),так что теперь я могу использовать вектор «хранения» как есть и просто добавить карты, как вы предложили?

Это невозможно.Векторные итераторы остаются недействительными.Они могут стать неопределенными при добавлении или удалении элементов в векторе.

Answer 2

Это звучит идеально, чтобы использовать Boost Bimap .

Answer 3

Если свойства, по которым вы хотите искать ссылки, меняются не очень часто, вы можете выбрать std::list<Link> в качестве основного контейнера для хранения объектов ссылок.Затем для каждого критерия у вас есть один std::map, который отображает значение на итератор, указывающий на список.Например,

typedef std::list<Link> LinkList;

LinkList links = ...;
std::map<std::string, LinkList::iterator> linkByName;
std::map<unsigned int, LinkList::iterator> linkByPopularity;

Приятной особенностью std::list является то, что он обладает очень сильными гарантиями аннулирования итераторов (в основном, ваш итератор в списке становится недействительным только в случае удаления элемента из списка).

Чтобы эти структуры постоянно обновлялись, вы можете обернуть все это в оболочку 'LinkCollection' или около того.