Структура данных C++ для выполнения индексированного списка

Question

Я ищу наиболее эффективную структуру данных для поддержки индексированного списка. Вы можете легко просмотреть его interms из карты STL:

std::map<int,std::vector<int> > eff_ds; 

Я использую это в качестве примера, потому что я в настоящее время с помощью этой установки. Операциями, которые я хотел бы выполнить, являются:

• Вставить значения на основе ключа: аналогично eff_ds [key] .push_back (..);
• Распечатайте содержимое структуры данных в терминах каждого ключа.

Я также пытаюсь использовать неупорядоченный карту и вперед список,

std::unordered_map<int,std::forward_list<int> > eff_ds; 

Это лучшее, что я мог бы сделать с точки зрения времени, если я использую C++ или есть другие варианты?

UPDATE:

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

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

k1: v1 v2 v3 v4 
k2: v5 v6 v7 
k3: v8 
. 
. 
. 
kn: vm 

Число этих итераций довольно большой ~ 1м.

Answer 1

Есть два аспекта вашей проблемы:

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

   Цифровой ключ может поддаваться вектору для этого, однако, если ключи малонаселены, это приведет к отрыву большого количества памяти.

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

2. Что является лучшим контейнером для списка чисел, что позволяет для вставки на обоих концах и возможность извлечения списка номеров в порядке (типа значения внешней карты)

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

на основе обновленной вопрос, так как вы можете ограничить себя добавление значения в конце списка, и так как вы не обеспокоены повторяющихся записей в списках, я бы рекомендовал использовать std::unordered_map<int,vector<int> >