Это использование вложенного вектора / MultiMap / Map хорошо?

Question

Я ищу идеальную структуру данных для следующего сценария:

У меня есть индекс i, и для каждого мне нужно поддерживать следующее Операция 1.: Быстро выглядеть Foo объекты (см. Ниже), каждый из которых связан с double стоимость.

Так что я сделал это:

struct Foo {
  int a, b, c;
};

typedef std::map<Foo, double> VecElem;
std::vector<VecElem> vec;

Но оказывается неэффективным, потому что я также должен обеспечить очень быструю поддержку для следующих Операция 2.: Убрать все FooS, что имеет определенное значение для a а также b (вместе со связанными двойными значениями).

Чтобы выполнить эту операцию 2, я должен повторять карты в векторе, проверяя Fooдля их a а также b Значения и стирание их один за другим с карты, что, кажется, очень дорогой.

Поэтому я сейчас рассматриваю эту структуру данных:

struct Foo0 {
  int a, b;
};

typedef std::multimap<Foo0, std::map<int, double> > VecElem;
std::vector<VecElem> vec;

Это должно обеспечить быструю поддержку как для операций 1 и 2 выше. Это разумно? Есть ли много накладных расходов из вложенных контейнеров?

Примечание. Каждый из мультимапсов обычно имеет только одну или две клавиши (типа Foo0), каждый из которых будет иметь около 5-20 значений (типа std::map<int,double>).

Answer 1

Чтобы ответить на вопрос заголовка: Да, вложенные контейнеры STL идеально подходят. В зависимости от профиля вашего использования это может привести к чрезмерному копированию сцен, хотя. Лучший вариант может быть обертывание содержимого всего, кроме контейнера верхнего уровня, используя Boost::shared_ptr, Таким образом, эта уборка контейнера не требует глубокой копии всего содержимого вашего вложенного контейнера. Это было бы так, если вы планируете проводить много времени вставки и удаления VecElem в точке vector - дорого, если VecElem является прямым multimap.

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

Answer 2

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

Например, это тип Foo Metable? Если это так, то вам нужно быть осторожным о создании типа Foo0 (Хм ... другое имя может быть хорошей идеей, чтобы избежать путаницы), поскольку изменения в Foo может быть недействительным Foo0.

Во-вторых, вам необходимо решить, нужна ли вам эта структура, чтобы хорошо работать для вкладышей / обновлений. Если население Foo Статический и неизменный - это не проблема, но если это не так, вы можете потратить много времени поддержания Vec а также VecElem.

Что касается вопроса о вложенных контейнерах STL, это нормально - и часто используется для создания произвольно сложных структур.