Добрый день.

Задача такая. Построить рейтинг строк, подсчитать, сколько раз встречается каждая строка. Если использовать std::map<std::string, int>, то можно нормально увеличивать счетчик, но тогда сортировка производится по строкам, хотя нужно по значению счетчика. Если использовать std::set<std::pair<std::string, int> >, то можно задать свою функцию сортировки, но тогда для увеличения счетчика придется сначала каким-то образом находить нужную запись. К слову сказать, добавление строк производится гораздо чаще, чем построение самого отчета. Как я понял, для map нельзя написать функцию сравнения для значения (только для ключа). Может можно еще придумать какую-нибудь структуру данных? 

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

делаешь функтор\функцию сравнения для second из pair, потом lower_bound\find для поиска. Только изменяй по следующей схеме, удаляешь элемеент и записываешь уже новый, измененный. Если бы не частое добавление, то можно было бы юзать сортированный вектор

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

O(ln(n))

так искать надо по паре? или только по счетчику?

Ну вот когда добавляем очередную строку: если она есть (вот тут нужно найти пару ("строка", [число])), то её счетчик увеличивается на 1, в противном случае добавляем пару ("строка", 1). 

boost::multi_index_container

ну так в чем прроблема? пишешь две функции сравнения, одна по счетчика(ее передаем в контейнер при создании), вторая по строке(ее передаем в ф-ию поиска) ф-ия поиска возвращает итератор, по которому мы удаляем 'элемент и записываем новый с обновленным счетчиком

Ясно. Спасибо   

А что эффективнее: map с map["строка"] += 1 или set с find_if()? То есть использует ли find_if() информацию о последовательности или же тупо циклом просматривает все элементы?

Это сообщение отредактировал(а) MastEdm - 22.7.2008, 13:26

А вы не могли бы набросать примерчик, а то я в boost не силен и первое знакомство (тут) как-то не пошло

Это сообщение отредактировал(а) MastEdm - 22.7.2008, 15:38

если find_if это алгоритм контейнера, то эффективность равнозначна.

MastEdm, 
тебе нужен контейнер с возможностью независимого поиска как по ключу, так и по значению.
либо сооруди такой сам из двух std::map, либо поищи в сети готовые варианты. В boost тоже есть, и не в одном варианте.

Кажется, скореее boost::bimap — более специализировано для данной задачи.

Интересно, а за какое время производится добавление и поиск в boost::multi_index_container? Ведь где-то мы должны проиграть  

Это сообщение отредактировал(а) MastEdm - 23.7.2008, 09:39

boost::bimap (действительно более подходящий) - http://www.boost.org/doc/libs/1_35_0/libs/...html/index.html
boost::multi_index_container - http://www.boost.org/doc/libs/1_35_0/libs/.../doc/index.html

И все-таки если вернуться к эффективности. Добавление в map происходит за логарифмическое время. То есть при добавлении строки в рейтинг мы можем найти ее за log(n) и прибавить к ее счетчику 1, а если ее нет, то добавить как новую пару <строка, 1> за тоже время. Когда же нам нужно построить сам рейтинг, то есть отсортировать строки по счетчику, то придется перебрать все элементы и добавить, к примеру, в multimap с сортировкой по счетчику. Получаем время n*log(n).  Теперь если нам нужно определить положение конкретной строки в рейтинге, то осуществляем полный перебор сформированного ранее multimap. Подитожу выше сказанное по операциям:

add(string)         C*log(n)
get_rating()        C*n*log(n)
get_pos(string)  C*n*log(n)

Результаты неутешительные (если, конечно, я нигде не наврал).

Не уверен, что предложенные контейнеры из boost работают быстрее. Если я неправ, переубедите меня