AG>Это multimap, а не multiset, причём скорее даже unordered_multimap

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

Здравствуйте, sokel, Вы писали:

S>например, над множеством объектов требуется построить различные индексы по каким любо ключам.
S>как вариант, индексы можно делать в виде set или multiset из указателей с соответсвующими компараторами — multisetset<T*, T_compare>

Допустим имеем такой multiset (пишу прямо сюда, может не скомпилиться, но думаю код понятен):

struct T { int a, b, c, d, e };

strunct T_compare
  : public std::binary_function<T*, T*, bool>
{
  T_compare(void) : f_(boost::bind(T::d, _1) < boost::bind(T::d, _2)) {}
  bool operator()(T* lhs, T*, rhs) { return f_(lhs, rhs); }
private:
  boost::function<bool (T*, T*)> f_;
}

multisetset<T*, T_compare>

Ну вот он упорядочен по d. Дальше что ? Чтобы работать теперь с диапазонами, нужны не ключи, а сами T*. Вряд ли это полезно.

Здравствуйте, igna, Вы писали:

I>Словарь, где словарные статьи отсортированы по алфавиту, а синонимы не объединены в одной статье.

И зачем в словаре сортировать слова по алфавиту, если unordered_multiset вроде как быстрее ?

Здравствуйте, Cyberax, Вы писали:

C>Да запросто. Например, у тебя у человека есть набор отработаных смен, и нужно их распределить по датам. std::map<date, shift> не пойдёт, так как могут быть две (или три) смены в один день. Тут-то std::multimap/multiset и помогает.

multimap — да, насколько я понимаю, именно для этого. но multiset — ?

Здравствуйте, maq, Вы писали:

maq>Ну не обязательно, ведь ID это значение поля класса, который будет лежать в multiset, зачем его еще как ключ выносить в map.

Затем, чтобы значение ID можно было передать в eqaul_range.

Здравствуйте, Alexander G, Вы писали:

AG>Здравствуйте, jazzer, Вы писали:

RK>>>>Возможно, для хранения частично упорядоченного множества. Например:
AG>>>2. Тут лучше подходит unordered_mulitset/hash_multiset, а не multiset.
J>>Интересно, как unordered_mulitset может подойти лучше в задаче, в которой требуется упорядочение.

AG>Интересно как в случае multiset (не multimap) извлечь пользу из упорядочения.

очередь сообщений, упорядоченная по таймстемпу с плохим разрешением

You will always get what you always got
  If you always do  what you always did

Здравствуйте, jazzer, Вы писали:

J>очередь сообщений, упорядоченная по таймстемпу с плохим разрешением

Это priority_queue, нет ?

Здравствуйте, Alexander G, Вы писали:

AG>И зачем в словаре сортировать слова по алфавиту, если unordered_multiset вроде как быстрее ?

Чтобы имитировать привычный пользователю просмотр книжного словаря.

Здравствуйте, Alexander G, Вы писали:

AG>2. Тут лучше подходит unordered_mulitset/hash_multiset, а не multiset.

1) unordered_* и hash_* есть в STL?
2) какая временная сложность у unordered_multiset?
3) как по заданному предикату сравнения (равенства или порядка, неважно) сделать хеш-функцию?

Например, есть функция strcoll, сравнивающая строки в соответствие с текущей (или заданной) локалью.
Я надеюсь, что она корректно обрабатывает лигатуры, умляуты и т.п.
То есть, немецкие слова Roentgen и Röntgen попадут в одну корзину.

Хеш-функция, читающая строку посимвольно, даст разные значения для слитного и раздельного написания умляута. Получится более сильный предикат, чем искомый — а должен быть более слабый.
Значит, нам нужна хеш-функция, читающая строку порциями, да ещё в зависимости от локали.
Давайте попросим разработчиков ОС и компиляторов, чтоб они включили эти хеш-функции в соответствующие системные библиотеки? Дело-то хорошее...

Здравствуйте, Кодт, Вы писали:

К>Значит, нам нужна хеш-функция, читающая строку порциями, да ещё в зависимости от локали.
Обычно это решается нормализацией строк в хэш-функции.

Здравствуйте, Кодт, Вы писали:

К>1) unordered_* и hash_* есть в STL?

hash_ это расширение некоторых STL. unordered_ будут в STL и есть в Boost.

К>2) какая временная сложность у unordered_multiset?

Amortized constant.
На практике multimap ощутимо быстрее map.

К>3) как по заданному предикату сравнения (равенства или порядка, неважно) сделать хеш-функцию?

Никак, но часто проблем с тем чтобы сделать хеш-фукнцию для ключа нет.

К>Например, есть функция strcoll, сравнивающая строки в соответствие с текущей (или заданной) локалью.
К>Я надеюсь, что она корректно обрабатывает лигатуры, умляуты и т.п.
К>То есть, немецкие слова Roentgen и Röntgen попадут в одну корзину.

Нет тут проблемы. Достаточно привести к виду, где Roentgen и Röntgen будут одинаковы.
strxfrm делает это.

К>Хеш-функция, читающая строку посимвольно, даст разные значения для слитного и раздельного написания умляута. Получится более сильный предикат, чем искомый — а должен быть более слабый.
К>Значит, нам нужна хеш-функция, читающая строку порциями, да ещё в зависимости от локали.
К>Давайте попросим разработчиков ОС и компиляторов, чтоб они включили эти хеш-функции в соответствующие системные библиотеки? Дело-то хорошее...

Хеширование результата strxfrm уже долшно работать.

Здравствуйте, igna, Вы писали:

I>Чтобы имитировать привычный пользователю просмотр книжного словаря.

Для пользователя нам надо отображать не всё — всё на экране не поместится.
Значит нужен random access iterator, к которому прибавляется положение скроллбара. Это сортированный vector.

Здравствуйте, Alexander G, Вы писали:

AG>Для пользователя нам надо отображать не всё — всё на экране не поместится.
AG>Значит нужен random access iterator, к которому прибавляется положение скроллбара. Это сортированный vector.

Я видел такой скроллбар для просмотра словаря из более чем ста тысяч слов. Использовать его двигая вверх-вниз мышью было довольно неудобно и бессмысленно, все равно не знаешь куда попадешь (хуже чем в книжном словаре). Реально пользователям это было не нужно, они просто хотели видеть слова предшествующие или последующие найденному поиском слову. Для такой функциональности сортированный вектор не нужен, но сортировка все-таки нужна.

Здравствуйте, igna, Вы писали:

I>Я видел такой скроллбар для просмотра словаря из более чем ста тысяч слов. Использовать его двигая вверх-вниз мышью было довольно неудобно и бессмысленно, все равно не знаешь куда попадешь (хуже чем в книжном словаре). Реально пользователям это было не нужно, они просто хотели видеть слова предшествующие или последующие найденному поиском слову. Для такой функциональности сортированный вектор не нужен, но сортировка все-таки нужна.

Хорошо, без скролбара. Хотя скролбаром нужно просто уметь пользоваться — двигать ползунок, затем кликать мжду ползунком и стрелкой, затем кликать по стрелке — вот в такой последовательности точность будет повышаться. А ещё есть клавиши управления курсором.

Всё равно, если пользователь не добавляет слова то лучше вектор.
А если даже взять словарь, где пользователь добавляет слова, нужен mulitmap, а не multiset, потому что у слов есть значения.

Здравствуйте, Alexander G, Вы писали:

AG>Хорошо, без скролбара. Хотя скролбаром нужно просто уметь пользоваться — двигать ползунок, затем кликать мжду ползунком и стрелкой, затем кликать по стрелке — вот в такой последовательности точность будет повышаться. А ещё есть клавиши управления курсором.

Вот если убрать практически бесполезную в данном случае операцию "двигать ползунок" и заменить скроллбар четырьмя кнопками: "кликать между ползунком и стрелкой вверх", "кликать между ползунком и стрелкой вниз", "кликать по стрелке вверх" и "кликать по стрелке вниз", то вектор просто будет не нужен.

AG>Всё равно, если пользователь не добавляет слова то лучше вектор.

Почему?

Здравствуйте, igna, Вы писали:

AG>>Всё равно, если пользователь не добавляет слова то лучше вектор.

I>Почему?

А чем multiset::equal_range лучше std::equal_range ?
std::vector — дефолтный контейнер, это использование других вместо него нужно обосновывать.

Здравствуйте, Alexander G, Вы писали:

AG>Здравствуйте, jazzer, Вы писали:

J>>очередь сообщений, упорядоченная по таймстемпу с плохим разрешением

AG>Это priority_queue, нет ?

Если я не ошибаюсь, priority_queue постоянно двигает объекты (естественно, как же иначе их в массиве располагать), в отличие от дерева.
А сложность и там и там — логарифм (правда, в дереве еще есть такая хорошая вещь как hinted insertion)

You will always get what you always got
  If you always do  what you always did

Здравствуйте, Alexander G, Вы писали:

AG>А чем multiset::equal_range лучше std::equal_range ?
Теоритически может быть быстрее, если реализована не дословно как 'make_pair(a.lower_bound(k), a.upper_bound(k))', а с использованием некоторых деталей реализации.

AG>std::vector — дефолтный контейнер, это использование других вместо него нужно обосновывать.
+1

Здравствуйте, Alexander G, Вы писали:

AG>Ну вот он упорядочен по d. Дальше что ? Чтобы работать теперь с диапазонами, нужны не ключи, а сами T*. Вряд ли это полезно.

И всё-таки, может быть полезно. Если, например, в сравнении участвует множество полей структуры. Плюс в разных индексах сравниваемые наборы полей могут пересекаться. И в отдельную структуры-ключи выносить не хочется. Для поиска создаем объект на стеке, в нем заполняем нужные для компаратора поля и вперед — получать диапазоны.

P.S. эти проблемы решаются с помощью multiindex вроде, но для себя все вопросы с ассоциативными контейнерами давно решил велосипедом. самодельное дерево + стратегия доступа к линкам в объектах (объекты сами по себе являются нодами). а для порядка — отдельная стратегия (нужна в insert-erase). деревья с фиксированными стратегиями порядка — аналоги stl деревьев. ну и по сути все деревья тогда представляются как своеобразный set или multiset. разница только в стратегиях порядка, определяющих варианты сравнения объектов с ключами (и/или с самим собой) и возможность множественной вставки. это могут быть стратегии упорядовачивания по member-ключу, типа member_order (кстати, можно даже мутить стратегии, которые будут принимать на вход тип ключа, вообще не имеющий отношения к объектам, например поиск по паре типа std::pair а порядок при вставке просто по паре членов структуры, просто чуть сложней стратегия (реализовать сравнение во всех вариантах типа объекта и типа ключа, соответственно стратегии вроде pair-triple-quad-member_order). различные варианты self_order стратегий (как для set). довольно часто попадаются стратегии навроде cast_member_order — по члену предка или потомка при возможности static_cast.

Здравствуйте, igna, Вы писали:

I>Я видел такой скроллбар для просмотра словаря из более чем ста тысяч слов. Использовать его двигая вверх-вниз мышью было довольно неудобно и бессмысленно, все равно не знаешь куда попадешь (хуже чем в книжном словаре). Реально пользователям это было не нужно, они просто хотели видеть слова предшествующие или последующие найденному поиском слову. Для такой функциональности сортированный вектор не нужен, но сортировка все-таки нужна.

1) Советую посмотреть, например, как работает скроллер в лингво.
2) Жизнь такова, что обычно словарей много, а пользователю надо показывать их слияние...