Добрый день

Есть контейнер элементы которого имеют какой-то атрибут, пусть цвет. Значение атрибута не уникально, напр в исходном контейнере 4 элемента с красным цветом, 2 с синим и.т.п.

Нужно: имея элемент быстро найти все с тем же цветом.  напр элемент красный - пробежаться по всем остальным красным. Исходный контейнер сортировать/изменять нельзя, создавать любые доп данные - можно.

Спасибо

std::multimap
+
pair<const_iterator,const_iterator>
   equal_range ( const key_type& x ) const;

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

Вопрос почти по теме, если контейнер не модифицировать после инициализации и если элементы уникальные - что предпочтительнее: set <pair> или все же map?

уникальные - map.
повторяющиеся - pair или мультимап.

Ну хотя получается, что грубо у всех множест nlogn для поиска, но и все себя перестраивают при добавлении эллемента.
И еще, как я понимаю в зависимости от константы перед nlogn будет сильно зависеть как контейней будет вести себя при разном количестве эллементов. Не смог обнаружить какие-то тесты по сравнению скорости работы алгоритмов и операторов, мб кому-то попадались на глаза?

Написал  

C++ (Qt)
struct CDataLookup {
 QList <CElement> mData;    // исходный контейнер
 QList <CElement *> mLookup; // указатели отсортированы по атрибуту (цвету)
};
 
// использование
void CDataLookup::ScanByColor( CElement & elem )
{
  for (int i = elem.mLookupIndex; i < mLookup.size(); ++i) {
    if (mLookup[i]->mColor != elem.mColor) break;
    DoSomething(mLookup[i]);  // указатель на элемент с тем же цветом что и elem
  }
}
 

Edit: а можно и вообще не хранить сортированный массив

Нет, достаточно один раз отсортировать и вписать в каждый элемент индекс указателя на первый с тем же цветом в сортированном массиве. Хотя есть ходы и получше.

Небольшая разница между "имея элемент" и "имея (значение) цвета" позволяет обойтись без поиска вообще. А от мультимапы я балдею Ну ладно, допустим даже "искать по цвету" - но тогда почему не lower_bound? На худой конец С-шный bsearch. Тот же логарифм но сортированный массив указателей куда дешевле чем любой ассоциативный контейнер.