Фасад std :: unordered_map для std :: unordered_set — как?

Question

Фасад std :: unordered_map для std :: unordered_set — как?

у меня есть std::unordered_set элементов типа Tи функция U key_of(const T& t), Теперь я хочу иметь конструкцию C ++, которая:

поддерживает некоторые из std::unordered_mapметоды; по крайней мере: operator [] const, find и итераторы.
не требует хранения фактического построения карты (даже с T * s)
поддерживается набором, то есть есть одна запись карты для каждого элемента e в наборе, есть запись карты (key_of (e), e).

Какой идиоматический способ (если есть) сделать это с (современным) C ++?

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

2

c++c++11 idiomatic idioms unordered-set

Решение

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

Я чувствую себя очень близоруким, но где проблема с использованием итераторов неупорядоченного множества, используя станд :: найти имитировать карты найти, а с помощью найти реализацию operator[] тривиально. Конечно, производительность не очень хорошая, но без необходимости хранить дополнительный указатель, я не вижу, как можно улучшить производительность.

Или используйте карту и измените вставку, чтобы проверить наличие дублирующих записей, что должно быть тривиально, так как ключ key_of(value) и заблокировать это.

Псевдокод (C ++ 14 для лямбды, можно легко обойти, используя вспомогательную функцию):

template<typename S, typename K> //set contained type, key type
class mapView {
typedef std::unordered_set<S> set_t;
set_t& set;
public:
mapView(const set_t& set) : set(set) {}
set_t::iterator find(const K& key) {
return std::find(set.begin(), set.end(), [&](element){return key_of(element)==key;});
}
S& operator[](U&& key) {
return *find(key);
}
//const declarations of above
//forward begin/end etc. to return sets iterators i.e.
set::iterator begin() {
return set.begin();
}
};

0

Источник

Accepted Answer

Понятие, которое дано std::unordered_set<T>мы строим std::unordered_map<K, V> такой, что K = key_of(const T& t), V = T накладывает огромное ограничение на key_of,

key_of является биективен. Инъективность, т.е. for any x, y E T : key_of(x) == key_of(y) -> x == y необходимо удовлетворить ключевую уникальность карты. также может потребоваться сюръективность, в противном случае ваша карта не может содержать элемент z, который не вычисляется с использованием key_of. Вы не указали, как будет построена эта структура, поэтому давайте ее отбросим.
key_of следует сохранить вероятность столкновения Hash_v(T x), Это не такая уж большая проблема, потому что если биективно, вы можете построить Hash_u(U k) такой, что вероятность столкновения точно такая же.

Если эти критерии удовлетворены, это ничем не отличается от std::unordered_map<K, V> используя std::unordered_set<std::pair<K, V>>, Что, кстати, вполне возможно, учитывая, что оба требуют Container, AllocatorAwareContainer, UnorderedAssociativeContainer,

примечание: равенство KeyEqual_u = std::equal_to<U>, KeyEqual_v = std::equal_to<V>

0