simulacrus
simulacrus
> А как таковой имплементировать в `forward_list` без итерации по всем элементам, если у него указатели направлены в одну сторону? Немногим сложнее чем `auto before_end = my_list.insert_after(old_iterator,5);`. Только сейчас это...
@GeorgyFirsov имеет смысл, когда не хочется мириться с оверхедом на хранение лишнего указателя. Допустим, когда создается буфер на листе достаточного размера, чтобы сумма всех лишних указателей превышала сотни мегабайт
> > Немногим сложнее чем `auto before_end = my_list.insert_after(old_iterator,5);` > > Это O(N), в данном случае N == 5. [Разве?](https://ru.stackoverflow.com/questions/334085/%D0%A1%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C-%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BA%D0%B8-%D0%BD%D0%BE%D0%B2%D0%BE%D0%B3%D0%BE-%D1%8D%D0%BB%D0%B5%D0%BC%D0%B5%D0%BD%D1%82%D0%B0-%D0%B2-%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA)
> Да, см. 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** >...
> А, пятёрка смутила, думал вы размер так обозначили. Виноват. Но тогда вопрос остаётся: > > > Только сейчас это приходится делать самому, делая обертку, а можно внедрить на уровне...
> > Просто мне кажется имеется какой-то архитектурный просчет в том, что итератор на первый элемент есть, а на последний -нет. > > См. мой предыдущий ответ про разреженные матрицы:...
> > a.before_end = it (Где it это параметр из b.splice_after(b.end(), it);) > > Да, согласен -- "первый" итератор остаётся в исходном контейнере. > > > b.before_end = a.before.end >...
> > a.before_end = it (Где it это параметр из b.splice_after(b.end(), it);) > > Да, согласен -- "первый" итератор остаётся в исходном контейнере. > > > b.before_end = a.before.end >...
> https://godbolt.org/z/W3fMTG7aP > > * `std::forward_list` – одно слово – самый компактный пустой контейнер. > * У `std::list` с некоторых пор появился `__Size`, так что он занимает 3 машинных слова....
> Я тоже не про ноды говорю, я про корневой элемент. Одно из преимуществ `std::forward_list` состоит в том, что пустые контейнеры получаются самыми маленькими (см. [#487 (comment)](https://github.com/cpp-ru/ideas/issues/487#issuecomment-987070408)). > > Где...