Здравствуйте, Went, Вы писали:


W>Единственная идея — отсортировать элементы по возрастанию и организовать бинарный поиск. Но как его организовать, если у нас list?
Skip list — стандартный подход для такой ситуации. Работает хорошо.

W>Организовать параллельную мапу? Но это слишком прожорливо
Отличный вариант. Да и прожорливого там особенно ничего нет — просто хранишь указатели/итераторы в ней на оригинальные элементы в списке.

W>но поиск происходит очень и очень часто.
А изменения насколько часты? Если их мало, а исходный список вообще никак трогать не хочется, то заводи параллельный вектор из указателей на элементы списка: его сортируй и по нему ищи. Дополнительной памяти совсем мало требуется, а стоимость поддержания сортированности будет мала, если изменения исходного списка будут редки.

W>и трудно поддерживать синхронизацию, по-моему.
Чтобы было легко — заверни в контейнер и работай через него.
Например, посмотри на boost::multi_index — там и список и словарь можно поднять над одними данными.

W> Попытаться заменить лист на вектор? Или на таких размерах коллекций я ничего не выиграю вообще?
Ну если тебе не нужно операций и свойств, которые специфичны для списков, вроде splice за O(1) или персистентности итераторов, то вектор часто лучше.