Хорошо ли это использовать вложенный вектор / мультикарту / карту? - PullRequest
Новая
       39

Хорошо ли это использовать вложенный вектор / мультикарту / карту?

1 голос
/ 22 сентября 2010

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

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

Итак, я сделал это: 

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

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

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

Чтобы выполнить эту операцию 2, мне нужно перебрать карты в векторе, проверяя Foo s на их значения 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>).

Ответы [ 2 ]

2 голосов
/ 22 сентября 2010

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

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

1 голос
/ 22 сентября 2010

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

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

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

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

...