Гарантии уникальности ключа в std :: unordered_multimap

Я задавался вопросом об уникальности ключевого объекта внутри std::unordered_multimap при работе с итерацией.

Я попытаюсь объяснить суть: мне нужно связать некоторые данные с типом ключа на карте, эти данные не следует рассматривать в Hash или же KeyEqual элементы, но мне нужно, чтобы избежать сохранения отдельной карты с ним (для целей оптимизации).

Итак, код, связанный с моей идеей, следующий:

struct Key {
void* data;
mutable bool attribute;

Key(void* data) : data(data), attribute(false) { }
bool operator==(const Key& other) const {
return data == other.data;
}
};

struct KeyHash {
size_t operator()(const Key& key) const {
return std::hash<void*>()(key.data);
}
};

class Foo {
public:
int i;
Foo(int i) : i(i) { }
};

std::unordered_multimap<Key, Foo, KeyHash> map;

Проблема возникает из-за того, что хотя это работает нормально, нет никаких гарантий относительно того факта, что ключ извлекается как первый элемент std::pair<const Key, Foo> отображение на один элемент всегда одинаково. Быть pair из const Key похоже, что каждый элемент на карте имеет свою копию ключа по значению, так что если я сделаю

void* target = new int();
map.emplace(std::make_pair(target, Foo(1)));
map.emplace(std::make_pair(target, Foo(2)));auto pit = map.equal_range(target);
pit.first->first.attribute = true;
std::cout << std::boolalpha << (++pit.first)->first.attribute << endl;

Это дает false что подтверждает то, что я думал. Так что на самом деле много места теряется для хранения ключей, если у вас есть несколько значений с одним и тем же ключом (что вам и нужно, так как вы используете std::unordered_map).

Я не вижу другого решения, кроме

struct Value
{
std::vector<Foo> foos;
bool attribute;
};

std::unordered_map<void*, Value> map;

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

Есть ли другие решения, которых я не вижу?

6

Решение

23.5.5.1 Обзор класса unordered_multimap [unord.multimap.overview]

1 unordered_multimap — это неупорядоченный ассоциативный контейнер, который поддерживает эквивалентные ключи (экземпляр
unordered_multimap может содержать несколько копий каждого значения ключа), и это связывает значения другого
введите mapped_type с ключами. Класс unordered_multimap поддерживает прямые итераторы.

unordered_multimap может содержать несколько копий ключа, если вы хотите одну копию ключа, то потенциально unordered_map<K, vector<V>> может быть более подходящим.

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]