Наиболее подходящий ассоциативный контейнер STL, когда ключ является частью объекта [C ++] - PullRequest
Новая
       29

Наиболее подходящий ассоциативный контейнер STL, когда ключ является частью объекта [C ++]

5 голосов
/ 24 октября 2011

У меня есть такой класс: 

struct Thing
{
    unsigned index;
    // more data members
};

Я использую std::map<Thing> для хранения моих Thing с. Код вызова выглядит примерно так: 

Thing myThing(/*...*/);
std::map<Thing> things;
things[myThing.index] = myThing;
// ...
Thing &thing3 = things[3];

Мне было интересно, существует ли подход, который мог бы использовать Thing::index напрямую, без необходимости неявно копировать его в pair::first.

Полагаю, мне нужно было бы предоставить какой-то оператор сравнения Thing, но это нормально. std::set может работать, но мне понадобится целый объект Thing в качестве ключа: 

std::set<Thing> things;
Thing &thing3 = *things.find(Thing(3));

Кроме рефакторинга Thing в std::pair, могу ли я добиться большего успеха с STL?

Ответы [ 4 ]

2 голосов
/ 24 октября 2011

Не понимаю, почему 

inline bool operator<(const Thing& a,const Thing& b) {
  return (a.index<b.index);
}

std::set<Thing> things;  // Uses comparison operator above

Thing &thing3 = *things.find(Thing(3));

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

Обновление в свете комментариев ниже:

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

inline bool operator<(const shared_ptr<Thing>& a,const shared_ptr<Thing>& b) {
  return (a->index < b->index);
}

std::set<shared_ptr<Thing>> things;  // Uses comparison operator above

shared_ptr<Thing> key3(new Thing(3));   

Thing &thing3 = *things.find(key3);

, хотя сравнение значений указателей с ИМХО довольно вредно, и было бы лучше пойти более подробным путем явного аргумента «Сравнить» к заданным аргументам шаблона.

Следует иметь в виду одну вещь (из моего собственного опыта с очередями с большим приоритетом для тяжеловесных объектов): у контейнеров на основе std::pair<trivial_key,shared_ptr<heavyweight_object>> могут быть существенные преимущества перед std::pair<trivial_key,heavyweight_object> из-за того, что обходыпервое касание только клавиш (например, find) может быть намного более эффективным кешированием по сравнению с последним, которое также извлекает в кэш-память большое количество ненужных / не относящихся к делу heavyweight_object байт (зависит от деталей и чиселконечно, но на самом деле этот эффект может легко затопить относительно небольшие затраты на дублирование ключа).

1 голос
/ 24 октября 2011

I Напомним, что boost :: flyweight поддерживает экстракторы ключей , чтобы избежать сохранения дополнительного хранилища для ключа, когда его легко получить из объекта.

Я не предлагаю использовать навеску во всех случаях, когда достаточно map или unordered_map, мне трудно поверить, что эти классы не будут поддерживать подобный шаблон извлечения ключей, хотя я могу 'Я не могу найти упоминания в документации или Google.В любом случае это может быть полезно для вас

1 голос
/ 24 октября 2011

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

0 голосов
/ 24 октября 2011

Как насчет использования адреса памяти вашего объекта в качестве ключа на вашей карте ??

std::map< void*, std::shared_ptr<MyObject> > myMap;
myMap.insert( std::pair<void*, std::shared_ptr<MyObject> >(object.get(), object) );

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

...