Самый эффективный контейнер для карты uint16_t to uint16_t

Без некоторого дополнительного контекста о вашей карте,

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

если вы намереваетесь использовать достаточное количество данных, но недостаточно, чтобы было слишком много коллизий хешей, std :: unordered_map амортизировало O (1) поисков, и если вас это не волнует порядок, в котором они хранятся, может быть хорошим предположением.

Если вы используете не много данных и хотите, чтобы они были гибкими, std :: vector - хороший выбор.

Поскольку мы знаем только то, что это карта от uin16_t до uint16_t, нет один лучший ответ.

Обычно двоичное дерево (std::map, которое вы в настоящее время используете) обеспечивает адекватную производительность. Ваш бюджет процессора должен быть очень маленьким.

Бинарный поиск, вероятно, не будет намного быстрее. Хеш-таблица (std::unordered_map) может быть решением.

Просто убедитесь, что он правильно подобран, чтобы избежать перефразирования, и оставайтесь чуть ниже 1,0 коэффициента нагрузки.

std::unordered_map<uint16_t, uint16_t> m(503); // 503 is a prime
m.emplace(123, 234);
m.emplace(2345, 345);

std::cout << m.find(123)->second; // don't use operator[] to avoid creating entries
std::cout << m.find(2345)->second;

Чтобы проверить качество функции хеширования, выполните итерацию по всем сегментам, вызвав bucket_size() и сложив что-либо выше 1 (то есть столкновение).

• Общее количество элементов меньше 500
• Вставка выполняется только один раз

Сохранение массива фиксированного размера (500) пар ключ-значение плюс «допустимое количество элементов», если фактический размер известен только во время выполнения; заполнить его данными и отсортировать; тогда вы можете просто выполнить бинарный поиск.

Учитывая, что элементов немного, в зависимости от конкретного процессора может быть даже удобнее просто выполнять линейный поиск (возможно, сначала сохраняя наиболее часто используемые элементы, если у вас есть подсказки о наиболее часто просматриваемых значениях) ,