-
Notifications
You must be signed in to change notification settings - Fork 0
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Итератор на последний элемент контейнера(до end()) #487
Comments
А как таковой имплементировать в |
|
Немногим сложнее чем |
Я проглядел часть про Ну тут как бы для такого контейнера это возможно реализовать только поддержанием актуального итератора/указателя на последнюю ноду внутри контейнера, но есть ли от этого большой смысл? Не то чтобы |
@GeorgyFirsov имеет смысл, когда не хочется мириться с оверхедом на хранение лишнего указателя. Допустим, когда создается буфер на листе достаточного размера, чтобы сумма всех лишних указателей превышала сотни мегабайт |
Глубоко не думал, но боюсь, что где-то вылезет O(N): либо в
Накладные расходы на разрежение памяти и последовательный доступ в |
Это, кстати. увеличит размер самого контейнера ( std::array<std::forward_list<T>, 100500> matrix; // большинство пустые |
Это O(N), в данном случае N == 5. |
|
Да, см. https://en.cppreference.com/w/cpp/container/forward_list/insert_after:
Complexity1-2) Constant. Нужно будет 5 раз продвинуть итератор, чтобы получить итоговую позицию. |
0_о |
А, пятёрка смутила, думал вы размер так обозначили. Виноват.
как выглядит обёртка над |
Вы неправильно поняли. Обертка над всем контейнером, которая бы дополнительно хранила указатель(итератор) на последний элемент и который бы обновлялся после вставки/удаления элементов.
Просто мне кажется имеется какой-то архитектурный просчет в том, что итератор на первый элемент есть, а на последний -нет. Есть указатель на "после последнего" однако от него нельзя получить доступ к последнему элементу, т.к. не определен |
См. мой предыдущий ответ про разреженные матрицы:
Допустим, вы делаете std::forward_list<T> a;
std::forward_list<T> b;
auto it = a.begin();
// ... что-то делаем с it
b.splice_after(b.end(), a, it); Сейчас эта операция O(1).
|
|
Да, согласен -- "первый" итератор остаётся в исходном контейнере.
Пока соглашусь, что действительно выглядит, как отдельный контейнер/обёртка:
|
В splice_after есть параметр other - это и есть а |
Да, не выгрузил из головы |
@pavelkryukov почему размер равен std::list? |
https://godbolt.org/z/W3fMTG7aP
|
Да, базовый класс у forward_list имеет лишь поле next(реализация gcc). Я не предлагаю ввести указатель на конечный элемент для каждой ноды(базового класса). Я предлагаю ввести указатель на уровне уже наследника от базового класса - он будет один на весь контейнер |
Я тоже не про ноды говорю, я про корневой элемент. Одно из преимуществ Где выигрыш в уменьшении размера ноды можно получить, представляю слабо. Если элемент большой, то добавление 1 или 2 указателей несущественно. Если элемент небольшой, куда эффективнее использовать |
Если хранится 1000000 элементов с размером 40 байт до будет отжираться 5 Гб + 1 Гб на поля, которые мне не нужны. Использование вектора влечет за собой еще больший объем памяти(1.5 - 2 x size для capacity) для push_back |
|
|
@pavelkryukov да даже в примере с матрицами - как у них реализована операция конкатенации(A(n x m)+B(n x k)=C(n x (m+k))) тогда? |
Я эту идею отсюда почерпнул, пока единственный содержательный ответ на вопрос "зачем нужен
Это не значит. что в любой момент времени |
Выходит, много звёзд должно сойтись, чтобы этот контейнер оказался предпочтительнее других. Так ли он тогда нужен в стандарте? |
Вот, что-то получается. |
Похоже, Дан список: Задача: удалить последний элемент через iterator erase_after(const_iterator pos). Убедимся, что удаляем последний элемент, сравнив результат |
Итератор на последний элемент до end()
Таким образом:
Появится новый метод с названием: prev_end() или bend() или before_end()
The text was updated successfully, but these errors were encountered: