Найти количество повторяющихся элементов в multiset

@dimmarvel · Регистрация: 04.04.2018

Студворк — интернет-сервис помощи студентам

Собственно из названия понятно что я хочу сделать)
Вот код, закомментированый элемент не работает

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<string>
#include<set>
using namespace std;
 
int main() {
    setlocale(LC_ALL, "Rus");
    string str;
    char a;
    getline(cin,str);
        multiset<char> multstr;
        for (int i = 0; i < str.size(); i++)
        {
            multstr.insert(str[i]);
        }
        /*for (auto &item : multstr) {
            cout << "\n\nElement: " << item;
            a = multstr.count(item);
            cout << "\nEgo kolichestvo: " << a;
        }*/
    system("pause");
    return 0;
}

Добавлено через 1 час 54 минуты
Т. е., есть строка которая содержит произвольный текст, мне нужно узнать какая буква и сколько раз она повторяется обязательно использовать set\multiset

Croessmah · 20.10.2019, 18:15

S_el, поменял.

elapsed_mseconds= 131
elapsed_mseconds= 395

@nonedark2008 · 20.10.2019, 18:29

Сообщение от IGPIGP

it=upper_bound(it, chars.end(), *it);

Это "палёный" upper_bound и для данной задачи неэффективен. Нужно использовать chars.upper_bound(...).

Новичок · 20.10.2019, 18:30

А вы в курсе что multiset.count работает не за чистый логарифм ? Логарифм + количество. Помню на codeforces какая-то задача у меня из-за этого по времени не прошла, тогда я узнал и запомнил(на всю жизнь

) что multiset.count работает за O(log N + K), где K = количество найденных элементов. Я правда не знаю как написать тест, на котором это скажется, но я решал бы эту задачу с std::map.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <string>
#include <map>
 
int main() {
    std::string s;
    std::getline(std::cin, s);
    std::map<char, int> count;
    for (char c: s) count[c]++;
    for (const auto &res: count) {
        std::cout << res.first << ' ' << res.second << '\n';
    }
}

@S_el · 20.10.2019, 18:33

Сообщение от Croessmah

S_el, поменял.

Теперь сомнений нет. Замерил и у себя. advance ~ в 3 раза быстрее upper_bound windows gcc без оптимизаций.
Сейчас еще студийным замерю.

update:
на студийном advance все равно быстрее примерно с такой разницей.

IGPIGP · 20.10.2019, 18:44

А я ничего не менял. Однако первый вариант стал значительно медленнее. Что-то в системе перестроилось... Сейчас advance побеждает везде.

Добавлено через 3 минуты

Сообщение от S_el

на студийном advance все равно быстрее примерно с такой разницей

Не могу повторить тот тест. В чём тут дело, не понимаю. Студия кстати ныла что будет апдейтиться. Но не думаю, что всё так хитро получилось. Чудеса.

Добавлено через 2 минуты

Сообщение от Новичок

А вы в курсе что multiset.count работает не за чистый логарифм ?

Новичок, када идёт захват слева и справа (от цепи повторов) там лог. Может не совсем чистый.

Добавлено через 1 минуту

Сообщение от nonedark2008

Это "палёный" upper_bound и для данной задачи неэффективен. Нужно использовать chars.upper_bound(...).

nonedark2008, да вы чо?! Щас попробую))

@S_el · 20.10.2019, 18:44

Сообщение от IGPIGP

Сейчас advance побеждает везде.

Добавьте chars.upper_bound как в моем первом сообщении и которое выбирает nonedark2008, на моих компиляторах этот вариант в ~2 раза быстрее чем advance

Croessmah · 20.10.2019, 18:48

Сообщение от nonedark2008

Это "палёный" upper_bound

Я даже не заметил, что там std::upper_bound

IGPIGP · 20.10.2019, 18:53

Сообщение от IGPIGP

Щас попробую))

А с ним вдвое быстрее чем advance в обоих компиляторах! И это несмотря на то, что он вызывается по ключу только и нельзя задать пару итераторов. То есть, тупо просматривает весь контейнер, но всё равно быстрее. Вот что ~~святой крест~~ бинарный алгоритм делает!
Но ведь глядя на

Сообщение от nonedark2008

"палёный" upper_bound

остаётся признать, что дурют нашего брата. Внутрях у upper_bound - последовательный просмотр... Вот это да... Ч-черт. Полезно однако задавать дурацкие вопросы иной раз. Спасибо nonedark2008!

@nonedark2008 · 20.10.2019, 19:30

Сообщение от IGPIGP

что дурют нашего брата

Не то чтобы дурят. Там под капотом почти всегда обычный бинарный поиск, гарантирующий O(log2(n)) сравнений. Но, думаю, всем понятно, к чему это приведет на итераторах неслучайного доступа.

IGPIGP · 20.10.2019, 19:36

Сообщение от nonedark2008

Но, думаю, всем понятно, к чему это приведет на итераторах неслучайного доступа.

nonedark2008, вы правы. К сожалению не существует способа получить ссылку на контейнер по итератору инициализированному через него. Таким образом внутри upper_bound нельзя выбрать алгоритм для дерева. Я когда-то это видел. Но забыл. Хорошая ступенька чтобы споткнуться. Интересно, а в топике:
Распространенные ошибки
есть упоминание такой? Ошибка чисто логическая. Может успешно "работать" годами и никто не увидит)

Новые блоги и статьи Все статьи Все блоги /
интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .
Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .	Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .	Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .