Russian Qt Forum

И так и сяк кручу.
Как же объеденить свойства List со свойствами Hash - т.е. и быстрый доступ по индексу и быстрый поиск по ключу, вот такие взаимоисключения.

То лирика. Задача  - число, определить какому диапазону оно принадлежит. Понятно, диапазон есть.

P.S. Ну про брутфорс не будем.

P.P.S. И конечно же! Христос воскрес!

std::list<ValType> для быстрого доступа по индексу, std::hash<KeyType, size_t> для быстрого поиска по ключу, значения в хэше - индексы списка. Далее просто объединяем эти два объекта в одном классе. Пойдёт?

Наверное имелся ввиду QList, но причем тут Hash (QHash ?) - для поиска по диапазону он непригоден. Нужен std::lower_bound выбирайте любой контейнер который это имеет, а можно и просто сортированный массив/вектор. Если данные нужно удалять/добавлять(и это критично по скорости)  - тогда хужее. В бусте есть такой "multi" (не помню точно) и, пожертвовав еще кусочком коры мозга, постичь можно. Но я бы все-таки сделал свой

В принципе подойдёт, пока нет вставки удаления - т.е. перерасчет всего листа при произвольном удалении (вставке).


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