Итератор на последний элемент контейнера(до end())

[simulacrus]

Итератор на последний элемент до end()

Таким образом:

1. В forward_list появляется возможность вставить элемент в конец, не итерируясь по всем элементам

Появится новый метод с названием: prev_end() или bend() или before_end()

[pavelkryukov]

А как таковой имплементировать в forward_list без итерации по всем элементам, если у него указатели направлены в одну сторону?

[GeorgiiFirsov]

rbegin же есть для подобного. Да и сделать из него обычный итератор, поколдовав с методом base, проблем не составит

[simulacrus]

А как таковой имплементировать в forward_list без итерации по всем элементам, если у него указатели направлены в одну сторону?

Немногим сложнее чем auto before_end = my_list.insert_after(old_iterator,5);. Только сейчас это приходится делать самому, делая обертку, а можно внедрить на уровне метода

[GeorgiiFirsov]

А как таковой имплементировать в forward_list без итерации по всем элементам, если у него указатели направлены в одну сторону?

Я проглядел часть про forward_list :)

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

[simulacrus]

@GeorgyFirsov имеет смысл, когда не хочется мириться с оверхедом на хранение лишнего указателя. Допустим, когда создается буфер на листе достаточного размера, чтобы сумма всех лишних указателей превышала сотни мегабайт

[pavelkryukov]

только поддержанием актуального итератора/указателя на последнюю ноду внутри контейнера

Глубоко не думал, но боюсь, что где-то вылезет O(N): либо в std::forward_list::splice_after, либо в удалении элемента по итератору...

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

Накладные расходы на разрежение памяти и последовательный доступ в std::list/ std::forward_list будут куда больше.

[pavelkryukov]

поддержанием актуального итератора/указателя на последнюю ноду внутри контейнера

Это, кстати. увеличит размер самого контейнера (sizeof(std::forward_list<T>)), а одно из его основных применений -- экономия места для разреженных матриц, т. е. чего-то такого

std::array<std::forward_list<T>, 100500> matrix; // большинство пустые

[pavelkryukov]

Немногим сложнее чем auto before_end = my_list.insert_after(old_iterator,5);

Это O(N), в данном случае N == 5.

[simulacrus]

Немногим сложнее чем auto before_end = my_list.insert_after(old_iterator,5);

Это O(N), в данном случае N == 5.

Разве?

[pavelkryukov]

Да, см. https://en.cppreference.com/w/cpp/container/forward_list/insert_after:

iterator insert_after( const_iterator pos, size_type count, const T& value );	(3)	(since C++11)

Complexity

1-2) Constant.
3) Linear in count

Нужно будет 5 раз продвинуть итератор, чтобы получить итоговую позицию.

[simulacrus]

Да, см. https://en.cppreference.com/w/cpp/container/forward_list/insert_after:

iterator insert_after( const_iterator pos, size_type count, const T& value ); (3) (since C++11)

Complexity

1-2) Constant. 3) Linear in count

Нужно будет 5 раз продвинуть итератор, чтобы получить итоговую позицию.

0_о
...
Я же привел пример со вставкой одного элемента.

[pavelkryukov]

А, пятёрка смутила, думал вы размер так обозначили. Виноват.
Но тогда вопрос остаётся:

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

как выглядит обёртка над insert_after, которая даёт итератор на последний элемент?

[simulacrus]

А, пятёрка смутила, думал вы размер так обозначили. Виноват. Но тогда вопрос остаётся:

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

как выглядит обёртка над insert_after, которая даёт итератор на последний элемент?

Вы неправильно поняли. Обертка над всем контейнером, которая бы дополнительно хранила указатель(итератор) на последний элемент и который бы обновлялся после вставки/удаления элементов.
Указатель на последний элемент решает 2 проблемы:

1. Дает доступ к последнему элементу сразу (О(1)) для модификации
2. Позволяет вставлять в конец списка через insert_after за О(1)

Просто мне кажется имеется какой-то архитектурный просчет в том, что итератор на первый элемент есть, а на последний -нет. Есть указатель на "после последнего" однако от него нельзя получить доступ к последнему элементу, т.к. не определен operator-(int distance) для итератора в forward_list

[pavelkryukov]

Просто мне кажется имеется какой-то архитектурный просчет в том, что итератор на первый элемент есть, а на последний -нет.

См. мой предыдущий ответ про разреженные матрицы:
#487 (comment)

который бы обновлялся после вставки/удаления элементов

Допустим, вы делаете splice_after с некоторой позиции списка A в список B:

std::forward_list<T> a;
std::forward_list<T> b;
auto it = a.begin();
// ... что-то делаем с it
b.splice_after(b.end(), a, it);

Сейчас эта операция O(1).
Если нам нужно хранить итератор на последний элемент, то:

• у списка B это будет последний элемент списка A, который можно достать только итерированием от it до последнего валидного элемента (линейная сложность)
• у списка A это либо
  • std::prev(it), которого в std::forward_list нет.
  • последний валидный элемент от a.begin() (линейная сложность + вы уже потеряли информацию о a.begin()

[simulacrus]

Просто мне кажется имеется какой-то архитектурный просчет в том, что итератор на первый элемент есть, а на последний -нет.

См. мой предыдущий ответ про разреженные матрицы: #487 (comment)

который бы обновлялся после вставки/удаления элементов

Допустим, вы делаете splice_after с некоторой позиции списка A в список B:

std::forward_list<T> a;
std::forward_list<T> b;
auto it = a.begin();
// ... что-то делаем с it
b.splice_after(b.end(), it);

Сейчас эта операция O(1). Если нам нужно хранить итератор на последний элемент, то:

• у списка B это будет последний элемент списка A, который можно достать только итерированием от it до последнего валидного элемента (линейная сложность)

• у списка A это либо

  • std::prev(it), которого в std::forward_list нет.
  • последний валидный элемент от a.begin() (линейная сложность + вы уже потеряли информацию о a.begin()

1. b.before_end = a.before.end
2. a.before_end = it (Где it это параметр из b.splice_after(b.end(), it);)

[pavelkryukov]

a.before_end = it (Где it это параметр из b.splice_after(b.end(), it);)

Да, согласен -- "первый" итератор остаётся в исходном контейнере.

b.before_end = a.before.end

Но a не является аргументом в std::forward_list::splice_after

Пока соглашусь, что действительно выглядит, как отдельный контейнер/обёртка:

• больший размер самого объекта, равный размеру std::list.
• наличие std::before_end()
• splice_after с дополнительным параметром

[simulacrus]

a.before_end = it (Где it это параметр из b.splice_after(b.end(), it);)

Да, согласен -- "первый" итератор остаётся в исходном контейнере.

b.before_end = a.before.end

Но a не является аргументом в std::forward_list::splice_after

Пока соглашусь, что действительно выглядит, как отдельный контейнер/обёртка:

• больший размер самого объекта, равный размеру std::list.
• наличие std::before_end()
• splice_after с дополнительным параметром

В splice_after есть параметр other - это и есть а

[pavelkryukov]

Да, не выгрузил из головы insert_after; ну, тем лучше.

[simulacrus]

a.before_end = it (Где it это параметр из b.splice_after(b.end(), it);)

Да, согласен -- "первый" итератор остаётся в исходном контейнере.

b.before_end = a.before.end

Но a не является аргументом в std::forward_list::splice_after

Пока соглашусь, что действительно выглядит, как отдельный контейнер/обёртка:

• больший размер самого объекта, равный размеру std::list.
• наличие std::before_end()
• splice_after с дополнительным параметром

@pavelkryukov почему размер равен std::list?

[pavelkryukov]

https://godbolt.org/z/W3fMTG7aP

• std::forward_list – одно слово – самый компактный пустой контейнер.
• У std::list с некоторых пор появился __Size, так что он занимает 3 машинных слова.
• Ваш контейнер будет размером в 2 слова (итератор на начало и на конец), как std::list был в C++98. Можно и размер добавить.

[simulacrus]

https://godbolt.org/z/W3fMTG7aP

• std::forward_list – одно слово – самый компактный пустой контейнер.
• У std::list с некоторых пор появился __Size, так что он занимает 3 машинных слова.
• Ваш контейнер будет размером в 2 слова (итератор на начало и на конец), как std::list был в C++98. Можно и размер добавить.

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

[pavelkryukov]

Я тоже не про ноды говорю, я про корневой элемент. Одно из преимуществ std::forward_list состоит в том, что пустые контейнеры получаются самыми маленькими (см. #487 (comment)).

Где выигрыш в уменьшении размера ноды можно получить, представляю слабо. Если элемент большой, то добавление 1 или 2 указателей несущественно. Если элемент небольшой, куда эффективнее использовать vector/deque.

[simulacrus]

Я тоже не про ноды говорю, я про корневой элемент. Одно из преимуществ std::forward_list состоит в том, что пустые контейнеры получаются самыми маленькими (см. #487 (comment)).

Где выигрыш в уменьшении размера ноды можно получить, представляю слабо. Если элемент большой, то добавление 1 или 2 указателей несущественно. Если элемент небольшой, куда эффективнее использовать vector/deque.

Если хранится 1000000 элементов с размером 40 байт до будет отжираться 5 Гб + 1 Гб на поля, которые мне не нужны. Использование вектора влечет за собой еще больший объем памяти(1.5 - 2 x size для capacity) для push_back

[pavelkryukov]

1. Можно привести источник оценки 1.5x-2x для вектора, в особенности учитывая то, что расти он будет посредством push_back?
2. Миллион элементов – это всё же мегабайты. Я ожидаю, что выигрыш от экономии будет меньше потерь от нелокального размещения данных в связных списках.
3. Присоединяясь к предыдущим ораторам: было бы неплохо понять, какую задачу вы пытаетесь оптимизировать, зачем вам нужен связный список, а не std::deque.

[simulacrus]

1. Можно привести источник оценки 1.5x-2x для вектора, в особенности учитывая то, что расти он будет посредством push_back?
2. Миллион элементов – это всё же мегабайты. Я ожидаю, что выигрыш от экономии будет меньше потерь от нелокального размещения данных в связных списках.
3. Присоединяясь к предыдущим ораторам: было бы неплохо понять, какую задачу вы пытаетесь оптимизировать, зачем вам нужен связный список, а не std::deque.

1. https://github.com/facebook/folly/blob/main/folly/docs/FBVector.md . Вообще зависит от реализации компилятора, но мне кажется это адекватной эмпирической оценкой
2. Да, я ошибся на пару порядков =)
3. Задача - создание эффективного буфера при записи высокочастотных данных. Запись в конец, чтение с начала. deque,vector не эффективны - чтение может быть медленне чем запись(при чтении мы записываем данные на диск) и весь профит от линейного расположения исчезает. Зато не исчезает реалокация элементов в таких контейнерах

[simulacrus]

@pavelkryukov да даже в примере с матрицами - как у них реализована операция конкатенации(A(n x m)+B(n x k)=C(n x (m+k))) тогда?

[pavelkryukov]

как у них реализована операция конкатенации(A(n x m)+B(n x k)=C(n x (m+k))) тогда?

Я эту идею отсюда почерпнул, пока единственный содержательный ответ на вопрос "зачем нужен std::forward_list?
Если большинство списков пустые, то небольших затрат будет пройти каждый от начала к концу. Хотя я думаю, что автору эта операция могла и не требоваться.

Использование вектора влечет за собой еще больший объем памяти(1.5 - 2 x size для capacity) для push_back

Это не значит. что в любой момент времени v.capacity() == v.size() * 2. Удвоение будет происходить только по превышению текущей ёмкости.

[pavelkryukov]

чтение может быть медленне чем запись

Выходит, много звёзд должно сойтись, чтобы этот контейнер оказался предпочтительнее других. Так ли он тогда нужен в стандарте?
В std-proposals обычно советуют в таких случаях этот контейнер имплементировать на должном уровне и попытаться встроить в Boost.

[pavelkryukov]

Вот, что-то получается.

[pavelkryukov]

Похоже, before_end() сможет вернуть только const_iterator.

Дан список: std::forward_list<int> list{1, 2, 3, 4, 5, 8};.
before_end указывает на последний элемент (8).

Задача: удалить последний элемент через iterator erase_after(const_iterator pos).
Для этого сделаем pos, указывающий на предпоследний элемент (5).

Убедимся, что удаляем последний элемент, сравнив результат erase_after с end().
В этом случае нужно присвоить before_end = pos, но последний по сигнатуре STL константый.