Russian Qt Forum

Добрый день

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

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

Спасибо

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Написал  :)

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

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

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

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

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

Ну у меня в голове родился такой интересный костыль. Если тебе надо быстро пройтись по всем элементам но не критична скорость добавления/удаления новых элементов и не жалко продублировать данные то вот как можно замутить через-жопу:
QList<Элемент> - Список элементов.
QMap<Атрибут,*QList<Элемент> > - Вот здесь будем хранить дублированные данные.

Вот у нас есть элемент и нам надо пройтись по всем таким же элементам с таким же атрибутом. Типа псевдокод:
QList<Элемент> *список = QMap.value(Элемент.Атрибут);
Ну и дальше foreach список с проверкой на то что элемент не равняется первоначальному.

Ну и при вставке и удалении надо будет синхронизовать с QMap<Атрибут,*QList<Элемент> > но если этот контейнер и дополнительный вынести в отдельный класс то можно там все так красиво в обертку завернуть =).

не очень понял что значит "skip-list-based dictionary", но вот что говорит вики:
Associative containers are designed to be especially efficient in accessing its elements by their key, as opposed to sequence containers which are more efficient in accessing elements by their position.[1] Associative containers are guaranteed to perform operations of insertion, deletion, and testing whether an element is in it, in logarithmic time - O(log n). As such, they are typically implemented using self-balancing binary search trees and support bidirectional iteration. Iterators and references are not invalidated by insert and erase operations, except for iterators and references to erased elements.
http://en.wikipedia.org/wiki/Associative_containers_(C%2B%2B)

self-balancing binary search tree - это и есть самобалансируещее красно-черное дерево

На вики есть и про Skip list (Список с пропусками) (http://ru.wikipedia.org/wiki/Список_с_пропусками)

Желание вооружиться знаниями вполне нормально, но Вы можете думать сами?  :)

Для задачи изложенной в теме - вообще не нужны никакие мапы и/или др ассоциативные контейнеры, проход вообще выполняется без поиска, за счет того что нужные данные просчитываются один раз и сохраняются в элементы. Это можно с тем же успехом делать и С массивами.

Если же рассматривать др, более общую задачу - уметь находить все "по цвету" при условии что в исходный контейнер добавляются/удаляются элементы - то и здесь можно найти ходы намного лучше шаблонов STL, как по скорости, так и по расходу памяти. Правда они не будут такими общими/универсальными/очевидными.