Lookup

[Igors]

Добрый день

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

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

Спасибо

[kambala]

можно сразу завести словарь, ключами которого будут атрибуты, а значениями - векторы/множества указателей на элементы с данным атрибутом

[qt_user]

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

[Igors]

Рекомендации понятны, спасибо. А нельзя это сделать без всякого STL и/или Qt, просто на массивах/new? Или так будет сложно/громоздко?

[kambala]

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

[Bepec]

Можно конечно создать кучу массивов с названиями атрибутов, и в них запихивать элементы.

Конечно это будет жутким костылём, ибо мультимап уже это реализует и вполне сносно.

PS напиши свой собственный мультимап.

[Disa]

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

[Igors]

Нельзя модифицировать исходный контейнер, но снабдить элемент доп данными - можно

[Bepec]

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

[qt_user]

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

я думаю если ключи допустим строка, оператор сравнения для std::string будет работать намного быстрее,
чем для std::pair<std::string, std::string>

хотя это больше зависит от задачи: если можно выделить один ключ - тогда это std::map,
если два значения равноправны и нельзя сказать что из них является ключом - тогда лучше
std::set<std::pair<...> >

[Disa]

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

[Igors]

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

Это катастрофически зависит от конкретной реализации, часто также от опций компилятора. Напр (не к ночи будь сказано) у MS это может отличаться на порядки debug/release

На мой взгляд лучшее средство - тщательно продумывать организацию данных, а не ляпать контейнерами абы как. О чем, кстати, и данная тема 

[Igors]

Можно конечно создать кучу массивов с названиями атрибутов, и в них запихивать элементы.

Конечно это будет жутким костылём, ибо мультимап уже это реализует и вполне сносно.

PS напиши свой собственный мультимап.

Написал  

Код

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: а можно и вообще не хранить сортированный массив

[qt_user]

Можно конечно создать кучу массивов с названиями атрибутов, и в них запихивать элементы.

Конечно это будет жутким костылём, ибо мультимап уже это реализует и вполне сносно.

PS напиши свой собственный мультимап.

Написал  

Код

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]);
  }
}
 

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

это конечно все хорошо, но зачем нужен подобный велосипед если есть тот же
мультимап?
void CDataLookup::ScanByColor( CElement & elem ) - я так понимаю перед каждым вызовом
этой ф-ции нужно заново сортировать QList <CElement *> mLookup; ?

[Igors]

это конечно все хорошо, но зачем нужен подобный велосипед если есть тот же
мультимап?
void CDataLookup::ScanByColor( CElement & elem ) - я так понимаю перед каждым вызовом
этой ф-ции нужно заново сортировать QList <CElement *> mLookup; ?

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

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