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