Переделать код для unordered_set

@Fixer_84 · Регистрация: 30.04.2016

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

Здравствуйте! У меня просьба к более опытным программистам данного форума. Можно ли как-то переделать код ниже для unordered_set? Подойдет ли этот контейнер для решения данной задачи? Если нет, то какой еще можно использовать? Данный код удаляет все повторы из строки сохраняя порядок символов. На входе строка, элементы которой переносятся в unordered_set<char>. Вот мое решение:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
 
using namespace std;
 
int main()
{
    string a;
    getline(cin, a);
    for (int j = 0; j < a.length(); j++)
    {
        for (int i = j + 1; i < a.length(); i++)
        {
            if (a[j] == a[i])
            {
                while (a[j] == a[i])
                {
                    a.erase(i, 1);
                }
            }
        }
    }
    cout << a << endl;
    system("pause"); 
    return 0;   
}

P.S. Сам алгоритм должен повторять исходный.

@palva · 02.03.2018, 22:54

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

@Fixer_84 · 02.03.2018, 23:18 **[ТС]**

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

Множества не хранят порядок элементов.

Здравствуйте! Спасибо за ваш ответ. Мне необходимо сохранить порядок остающихся элементов. Вот пример входных данных:

abc13a1b2z3c

Выходные данные:

abc132z

Данная задача решена (см. код выше), но в последнем тесте по времени не проходит. Есть алгоритм, который работает быстрее, но мне хотелось бы сохранить этот, чтобы посмотреть на скорость выполнения.

P.S. Можно ли как-то ускорить мой алгоритм?

@Renji · 02.03.2018, 23:36

Месье знает толк в извращениях.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
 
int main()
{
    bool table[256]={false};
    while(std::cin.peek()!='\n' && std::cin.peek()!=EOF)
    {
        int value=std::cin.get();
        if(!table[value])
        {
            table[value]=true;
            std::cout.put(value);
        }
    }
    std::cout<<std::endl;
    return 0;
}

Новичок · 03.03.2018, 02:23

Fixer_84, заводим unordered_set, идем по строке, если символа в множестве добавляем и добавляем в строку-результат(которая изначально пустая). Добавление в unordered_set работает за О(1), потому получаем алгоритм за линейное время.

@Renji · 03.03.2018, 02:34

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

Добавление в unordered_set работает за О(1), потому получаем алгоритм за линейное время.

А в худшем случае - добавление работает за линейное время. Плюс дергает аллокатор, для которого гарантий времени работы вообще никто, никому не давал.

Новичок · 03.03.2018, 02:53

Renji, выходит unordered_set вообще нельзя использовать.

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

@palva 4278 / 2970 / 693 Регистрация: 08.06.2007 Сообщений: 9,930 Записей в блоге: 5
	02.03.2018, 22:54
	Множества не хранят порядок элементов. С другой стороны множества и используют как раз для того, чтобы отказаться от этого алгоритма. Достаточно положить элемент в множество, -- и будет обеспечена уникальность. Поэтому непонятно требование сохранить алгоритм. 1

Новичок 1682 / 1098 / 489 Регистрация: 17.07.2012 Сообщений: 5,361
	03.03.2018, 02:23
	Fixer_84, заводим unordered_set, идем по строке, если символа в множестве добавляем и добавляем в строку-результат(которая изначально пустая). Добавление в unordered_set работает за О(1), потому получаем алгоритм за линейное время. 0

Новичок 1682 / 1098 / 489 Регистрация: 17.07.2012 Сообщений: 5,361
	03.03.2018, 02:53
	Renji, выходит unordered_set вообще нельзя использовать. 0

Опции темы