Lookup

[qt_user]

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

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

[twp]

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

The QMap class is a template class that provides a skip-list-based dictionary.

[V1KT0P]

Добрый день

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

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

Спасибо

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

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

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

[qt_user]

The QMap class is a template class that provides a skip-list-based dictionary.

не очень понял что значит "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 - это и есть самобалансируещее красно-черное дерево

[twp]

не очень понял что значит "skip-list-based dictionary", но вот что говорит вики:

На вики есть и про Skip list (Список с пропусками)

[Igors]

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

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

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