Forward_list и вставка элемента в конец него

@Leonman · Регистрация: 17.06.2012

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

Всем доброго.

Прошу прощение, если ответ на этот вопрос уже есть на просторах.

И так. Есть у меня forward_list fwlist, я хочу вставить в конец него элемент. Так как forward_list не имеет функции push_back(), а имеет вместо нее функцию insert_after, мне надо получить итератор не на элемент после последнего, а именно на последний элемент fwlist`а. И вот тут-то я застрял.

Я не могу сделать так:

C++
1
auto before_end = --fwlist.end();

потому что нельзя применять декременты на итераторы forward_list`ов.

Я не могу сделать так:

C++
1
auto before_end = fwlist.begin() + (fwlist.size()-1);

потмоу что у forward_list`ов нет метода size()

Конечно, я бы мог просто икрементировать fwlist.begin() до последнего элемента, но как-то это глупо, думаю, что есть способ попроще.

Спасибо.

P.S. Строго не судите, только начал изучать итераторы и forward_list`ы.

@DrOffset · 13.09.2015, 02:06

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

Конечно, я бы мог просто икрементировать fwlist.begin() до последнего элемента, но как-то это глупо, думаю, что есть способ попроще.

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

Добавлено через 3 минуты
Можно в общем-то сохранять итератор после каждой вставки, тогда ты получишь актуальный последний элемент. Как-то так:

C++
1
2
3
4
5
6
7
  std::forward_list<int> mylist;
   
  auto end = mylist.before_begin();  
  
  end = mylist.insert_after(end, 1); 
  end = mylist.insert_after(end, 2);     
  end = mylist.insert_after(end, 3);

@Leonman · 13.09.2015, 02:18 **[ТС]**

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

Если в твоей задаче это глупо, то ты просто неправильно выбрал контейнер.

Задача не моя, а учебника. Там требуется использовать конкретно forward_list. Ну как вариант. Но опять же, как-то не очень.

@DrOffset · 13.09.2015, 02:40

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

Задача не моя, а учебника. Там требуется использовать конкретно forward_list. Ну как вариант. Но опять же, как-то не очень.

Ты должен понимать, что существуют разные инструменты.
Каждый инструмент под свою задачу.
Если ты попытаешься использовать отвертку вместо стамески, у тебя получится, но плохо. Тут тоже самое.

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

Там требуется использовать конкретно forward_list.

Как задача звучит в оригинале?

Добавлено через 12 минут
Для справки, forward_list содержит всего один элемент, это указатель на начало. С помощью такого контейнера очень легко и эффективно реализуется стек (LIFO). Т.к там имеет смысл брать и добавлять элементы только в начало. При этом мы не тратим память ни на хранение размера списка, ни на хранение указателя на конец списка (и в реализации std::forward_list этих данных нет). Любые другие задачи со схожей организацией обращения к элементам контейнера также хорошо решаются с помощью forward_list. Если же у нас задача, которая требует эффективной вставки в конец или получения размера списка за O(1), то, очевидно, forward_list нам не подходит.

@Leonman · 13.09.2015, 02:43 **[ТС]**

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

Как задача звучит в оригинале?

Forward_list и вставка элемента в конец него

@DrOffset · 13.09.2015, 02:56

Leonman, конкретно в этой задаче требуется перебор всех элементов, поэтому у тебя все равно будет итератор на последней элемент после прохода по циклу, в случае, если строку не удалось найти. Дополнительно проходить не потребуется.
Так что тут все нормально

@Leonman · 13.09.2015, 03:02 **[ТС]**

DrOffset, как же? У меня итератор будет на элемент после последнего, потому что условие цыкла

C++
1
while(begin != fwlist.end())

, где begin - итератор на текущую строку в списке.

@DrOffset · 13.09.2015, 03:17

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

как же? У меня итератор будет на элемент после последнего, потому что условие цыкла

Ну примени воображение

Тебя разве заставляют ограничиваться только одним итератором?

Вот как вариант:

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void add(std::forward_list<std::string> & list
             , std::string const & first
             , std::string const & second)
{
    auto last = list.before_begin();
    for(auto it = list.begin(); it != list.end(); ++it)
    {
        last = it;
        if(*last == first)
        {
            break;
        }
    }
    list.insert_after(last, second);
}

@Leonman · 13.09.2015, 03:23 **[ТС]**

DrOffset, вот остановился на таком варианте:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void insert_s2_after_s1(forward_list<string> &fwlist, const string s1,
                        const string s2)
{
        auto begin = fwlist.begin(), prev = fwlist.before_begin();
 
        while(begin != fwlist.end())
        {
                if(*begin == s1)
                {
                        prev = begin;
                        break;
                }
 
                ++begin;
                ++prev;
        }
 
        fwlist.insert_after(prev, s2);
}

Однако все равно возникает необходимость во-втором итераторе, думал может как-то без него обойтись.

Или ваш, да.

@DrOffset · 13.09.2015, 03:41

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

думал может как-то без него обойтись.

Можно и без него:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void add(std::forward_list<std::string> & list
             , std::string const & first
             , std::string const & second)
{
    auto last = list.before_begin();
 
    while(std::next(last) != list.end())
    {
        if(*++last == first)
        {
            break;
        }
    }
    list.insert_after(last, second);
}

@Leonman · 13.09.2015, 03:58 **[ТС]**

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

std::next(last)

классная штука. Спасибо.

@DrOffset · 13.09.2015, 04:06

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

классная штука. Спасибо.

Пожалуйста.
И все-таки я очень рекомендую почитать про forward_list например вот в этой книге.
Там подробно рассказано почему у него нет функций size, push_back и т.п., описаны требования контейнера и его ограничения. Этого должно хватить, чтобы понять в каких ситуациях его можно использовать, а в каких нет.
Разные инструменты - разные задачи.

@Leonman · 13.09.2015, 04:11 **[ТС]**

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

Там подробно рассказано почему у него нет функций size, push_back и т.п.,

Вы меня не поняли. Это все описанно и в моей книге. Просто задача требовала именно forward_list. А все то, почему он не имеет size, busk_back, декремент и т.д. - я знаю. Липпман и его primerCpp 5 edition - хорошая вещь.

@DrOffset · 13.09.2015, 04:14

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

Вы меня не поняли. Это все описанно и в моей книге. Я все это знаю. Просто задача требовала именно forward_list.

Я как раз тебя хорошо понял.
Просто твой первый пост был полон удивления, вот я и решил посоветовать где можно почитать подробнее.
А задача эта на forward_list хорошо ложится и без size и декрементов, как ты уже успел увидеть, иначе бы ее в этой теме не давали.

@Leonman · 13.09.2015, 04:20 **[ТС]**

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

Просто твой первый пост был полон удивления

Да вроде небыл. Я как раз-таки написал, какие варианты применил бы, еслиб они были доступны, что и показывало мою осведомленность в данной вопросе.

@DrOffset · 13.09.2015, 04:33

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

Да вроде небыл. Я как раз-таки написал, какие варианты применил бы, еслиб они были доступны, что и показывало мою осведомленность в данной вопросе.

Хм. Мне это видится несколько в ином свете.
Если человек знаком с тем что из себя представляет single-linked list, то ему не придет в голову пытаться вставить что-то в его конец, потому что он знает, что это весьма затратная операция в общем случае. Это, знаешь, как пытаться прикручивать индексацию к списку. Можно, но будет очень дорого. И обычно никаких обходных маневров тут не может быть - скорее всего только смена структуры данных на более подходящую.
Но твоя задача хитрая, она поставлена таким образом, чтобы оверхед на полный перебор не являлся узким местом, потому что в худшем случае его все равно придется делать. Если бы задача звучала как требование безусловно добавить в конец списка какие-то данные, то тут forward_list тут же стал бы очень малоэффективен. Я на этом пытаюсь акцентировать твое внимание, на проблеме выбора инструмента, отсюда все советы данные выше. К примеру, мы можем знать что у std::list нет операции индексации, но этого мало, нужно понимать почему ее нет, и, самое главное, почему ее не может там быть. Если мы знаем это, то у нас не возникнет даже мысли применять std::list там, где нужен быстрый доступ к произвольному элементу контейнера по индексу.
В любом случае, я просто хотел заострить твое внимание на важных вещах, вот и все...

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@DrOffset 19497 / 10102 / 2461 Регистрация: 30.01.2014 Сообщений: 17,808
	13.09.2015, 02:56
	Leonman, конкретно в этой задаче требуется перебор всех элементов, поэтому у тебя все равно будет итератор на последней элемент после прохода по циклу, в случае, если строку не удалось найти. Дополнительно проходить не потребуется. Так что тут все нормально 0