search

cpp-ru / ideas

Идеи по улучшению языка C++ для обсуждения
https://cpp-ru.github.io/proposals
Creative Commons Zero v1.0 Universal
89 stars 0 forks source link

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

Open simulacrus opened 2 years ago

simulacrus commented 2 years ago

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

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

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

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

pavelkryukov commented 2 years ago

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

GeorgyFirsov commented 2 years ago

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

simulacrus commented 2 years ago

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

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

GeorgyFirsov commented 2 years ago

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

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

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

simulacrus commented 2 years ago

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

pavelkryukov commented 2 years ago

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

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

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

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

pavelkryukov commented 2 years ago

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

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

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

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

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

simulacrus commented 2 years ago

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

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

Разве?

pavelkryukov commented 2 years ago

Да, см. 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 commented 2 years ago

Да, см. 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 commented 2 years ago

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

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

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

simulacrus commented 2 years ago

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

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

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

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

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

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

pavelkryukov commented 2 years ago

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

См. мой предыдущий ответ про разреженные матрицы: https://github.com/cpp-ru/ideas/issues/487#issuecomment-987070408

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

Допустим, вы делаете 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). Если нам нужно хранить итератор на последний элемент, то:

simulacrus commented 2 years ago

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

См. мой предыдущий ответ про разреженные матрицы: #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 commented 2 years ago

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

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

b.before_end = a.before.end

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

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

simulacrus commented 2 years ago

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 commented 2 years ago

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

simulacrus commented 2 years ago

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 commented 2 years ago

https://godbolt.org/z/W3fMTG7aP

simulacrus commented 2 years ago

https://godbolt.org/z/W3fMTG7aP

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

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

pavelkryukov commented 2 years ago

Я тоже не про ноды говорю, я про корневой элемент. Одно из преимуществ std::forward_list состоит в том, что пустые контейнеры получаются самыми маленькими (см. https://github.com/cpp-ru/ideas/issues/487#issuecomment-987070408).

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

simulacrus commented 2 years ago

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

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

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

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

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

pavelkryukov commented 2 years ago

как у них реализована операция конкатенации(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 commented 2 years ago

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

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

pavelkryukov commented 2 years ago

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

pavelkryukov commented 2 years ago

Похоже, 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 константый.