Существует ли уже некоторая реализация набора/карты на основе std::vector?

Для небольших наборов или карт обычно намного быстрее использовать отсортированный вектор вместо дерева set/map - особенно для чего-то вроде 5-10 элементов. LLVM имеет несколько классов в этом духе, но нет реального адаптера, который предоставил бы интерфейс std::map, поддерживаемый с помощью std::vector.

Любая (свободная) реализация этого там?

Изменить. Спасибо за все альтернативные идеи, но меня действительно интересует векторный набор/карта. У меня есть конкретные случаи, когда я, как правило, создаю огромное количество наборов/карт, которые содержат обычно менее 10 элементов, и я действительно хочу иметь меньшее давление памяти. Подумайте, например, о соседних краях для вершины в треугольной сетке, вы легко можете заполнить 100 тыс. Наборов по 3-4 элемента каждый.

Ответ 1

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

Я рекомендую отличную (с открытым исходным кодом) библиотеку с именем Loki. Он имеет векторную реализацию ассоциативного контейнера, который является заменой замены для std:: map, называемой AssocVector.

Он обеспечивает лучшую производительность для доступа к элементам (и наихудшая производительность для вставки/удаления).

Библиотека была написана Andrei Alexandrescu автор Современный С++ Дизайн.

Он также содержит некоторые другие действительно отличные вещи.

Ответ 2

Если вы не можете найти что-либо подходящее, я бы просто обернул std::vector, чтобы сделать sort() для вставки, и реализовать find(), используя lower_bound(). Он должен быть прямым и таким же эффективным, как и пользовательское решение.

Ответ 3

Я не знаю такой реализации, но есть некоторые функции, которые помогают работать с отсортированными векторами уже в STL, например lower_bound и upper_bound.

Ответ 4

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

Сказав это, вы можете попробовать hash_map. Поиск по ключам гарантированно выполняется в постоянное время.

Ответ 5

Старый пост, я знаю, но для более свежих посетителей Boost flat_set и flat_map выглядят так, как вам нужно. Подробнее см. https://theboostcpplibraries.com/boost.container.

Ответ 6

Возможно, вы ищете неупорядоченную карту и неупорядоченный набор. Попробуйте взглянуть на неупорядоченные контейнеры TR1, которые полагаются на хеширование, или Boost.Unordered библиотека контейнеров. Под интерфейсом я не уверен, действительно ли они используют std::vector, но я бы поставил перед собой задачу взглянуть на него.