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

W>Здравствуйте. Есть список объектов. Он имеет разный размер: иногда это буквально пара элементов, иногда — пол сотни. По этому списку очень часто происходит поиск (точнее, по одному из полей хранимых объектов). Хотелось бы добиться максимальной скорости при небольших накладных расходах. Сама операция сравнения в поиске тривиальна (буквально два указателя), но поиск происходит очень и очень часто. По определенным причинам, организовать это в виде std::map не получится, контейнер должен оставаться листом.
W>Единственная идея — отсортировать элементы по возрастанию и организовать бинарный поиск. Но как его организовать, если у нас list? Ведь поиск центра будет последовательным, а, значит, мы потеряем больше, чем приобретем. С другой стороны, зная, что последовательность отсортирована, мы можем прерывать линейный перебор, если текущий "ключ" уже больше искомого. Но это тоже сомнительное ускорение. Организовать параллельную мапу? Но это слишком прожорливо и трудно поддерживать синхронизацию, по-моему. Какие есть решения, заточенные под подобную проблему? Попытаться заменить лист на вектор? Или на таких размерах коллекций я ничего не выиграю вообще?

instrusive list + intrusive set/hashmap. Ну или multiindex, который по сути то же самое, только без заморочек с аллокацией.
С intrusive гибче, например не удаляя из списка выдернуть из индекса, заменить ключ, вставить обратно.

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

W>В процессе работы оных практически не возникает, но в процессе загрузки, когда десятки документов сливаются в единую структуру, работа проводится колоссальная То есть, заменив лист на вектор, я могу получить адовы тормоза при старте, чего тоже не хотелось бы.

Загрузка в два этапа? Формируешь промежуточные структуры данных, и по завершени загрузки сливаешь их в рабочую модель.