Довольно простая задача — есть список, есть функция которая может добавить в конец этого списка произвольное число элементов (в т.ч. и ни одного).
Я хочу чтобы функция возвращала итератор на первый добавленный элемент, или end() если элементы не были добавлены — с тем, чтобы вызывающий код мог пройтись по этим новым элементам, не затрагивая старые.
Но оказалось, что push_back не возвращает ничего;
Если брать итератор end() вообще перед добавлением, то после добавления элемента он не указывает на первый добавленный элемент (что было бы логично для массивов, но разумеется не работает для списков, к сожалению).
Как красиво и эффективно решить эту задачу?

Здравствуйте, 00011011, Вы писали:

0>Довольно простая задача — есть список, есть функция которая может добавить в конец этого списка произвольное число элементов (в т.ч. и ни одного).
0>Я хочу чтобы функция возвращала итератор на первый добавленный элемент, или end() если элементы не были добавлены — с тем, чтобы вызывающий код мог пройтись по этим новым элементам, не затрагивая старые.
0>Но оказалось, что push_back не возвращает ничего;
0>Если брать итератор end() вообще перед добавлением, то после добавления элемента он не указывает на первый добавленный элемент (что было бы логично для массивов, но разумеется не работает для списков, к сожалению).
0>Как красиво и эффективно решить эту задачу?

1. Использовать `std::list<>::insert` и запомнить результат первой вставки, если таковая была

2. Всегда держать в списке один guard element в самом начале. Тогда перед вставкой можно запомнить `std::prev()` от `end()`, а после вставки (любым способом) сделать `std::next` от запомненного значения.

3. То же самое, что и 2, но не держать в списке guard element, а обрабатывать ситуацию изначально пустого списка, как особую.

4. ...

Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>1. Использовать `std::list<>::insert` и запомнить результат первой вставки, если таковая была

Да, это именно то что нужно. Вставка в позицию итератора end() работает, я как-то не подумал об этой возможности.

И еще вопрос: определено ли стандартом, что итератор end() одинаковый для любого состояния конкретного списка?
т.е.

std::list<int> L = { 10,20,30 };
auto e1 = L.end();
auto n = L.insert(e1, 40);
auto e2 = L.end();
L.push_back(50);
auto e3 = L.end();

будут ли всегда e1==e2 и e2==e3 и т.п.?
Проверил — в VS2017 одинаковые, но может это особенности реализации?

Здравствуйте, 00011011, Вы писали:

у меня предубеждение против list. Всё-таки куча аллокаций на ровном месте. Почему бы просто не запомнить позицию вставленного элемента?

template<typename T>
auto add_n_elems(std::vector<T>& source, const size_t count, const T& value)
{
    const auto pos = source.size();
    source.resize(count + pos, value); // # allocations <= 1
    auto it = source.cbegin();
    std::advance(it, pos); // complexity O(1)
    return std::span{ it, count };
}

Здравствуйте, sergii.p, Вы писали:

SP>Здравствуйте, 00011011, Вы писали:

SP>у меня предубеждение против list. Всё-таки куча аллокаций на ровном месте. Почему бы просто не запомнить позицию вставленного элемента?

SP>

SP>template<typename T>
SP>auto add_n_elems(std::vector<T>& source, const size_t count, const T& value)
SP>{
SP>    const auto pos = source.size();
SP>    source.resize(count + pos, value); // # allocations <= 1
SP>    auto it = source.cbegin();
SP>    std::advance(it, pos); // complexity O(1)
SP>    return std::span{ it, count };
SP>}
SP>

Непонятен смысл использования `std::advance` в таком коде....

1.
ULONG Before = List.size();
Add();
ULONG N = List.size() — Before;

i=end(); repeat(N) i--;

2.
i = end()
if (one added) if (i == end()) i--;

Здравствуйте, 00011011, Вы писали:

0>Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>>1. Использовать `std::list<>::insert` и запомнить результат первой вставки, если таковая была

0>Да, это именно то что нужно. Вставка в позицию итератора end() работает, я как-то не подумал об этой возможности.

0>И еще вопрос: определено ли стандартом, что итератор end() одинаковый для любого состояния конкретного списка?
0>т.е.

0>std::list<int> L = { 10,20,30 };
0>auto e1 = L.end();
0>auto n = L.insert(e1, 40);
0>auto e2 = L.end();
0>L.push_back(50);
0>auto e3 = L.end();

0>будут ли всегда e1==e2 и e2==e3 и т.п.?
0>Проверил — в VS2017 одинаковые, но может это особенности реализации?

Смотрим документацию:
https://en.cppreference.com/w/cpp/container/list/insert
https://en.cppreference.com/w/cpp/container/list/push_back
No iterators or references are invalidated.

По методам контейнеров обычно указывается в документации какие итераторы инвалидируются.

Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>Непонятен смысл использования `std::advance` в таком коде....

чтобы избавится от привязки к контейнеру. Может вам кажется, что для демонстрации такой простой идеи подойдёт it + pos. Но внутренний перфекционист отговорил меня от этого.

Здравствуйте, sergii.p, Вы писали:

АТ>>Непонятен смысл использования `std::advance` в таком коде....

SP>чтобы избавится от привязки к контейнеру. Может вам кажется, что для демонстрации такой простой идеи подойдёт it + pos. Но внутренний перфекционист отговорил меня от этого.

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

Будет только лучше, если вы воспользуетесь `+` и тем самым запретите использование вашей функции для контейнеров без random access. В противном случае неопытный пользователь может применить вашу функцию к контейнеру без random access и даже и не заметить, что тем самым он внес в код существенную неэффективность.

`std::advance` — это "костыль-заглушка", специально предназначенный для ситуаций, когда вы понимаете, что ваш код будет работать неэффективно без прямого доступа, но пока что не хотите заниматься оптимизацией (у вас нет времени и на текущем этапе вас устроит заглушка). То есть `std::advance` и `std::distance` — это функции-пометки, функции-закладки, функции-памятки, функции-красные флаги, помечающие неэффективные места, которые следует переписать в будущем.

Здравствуйте, sergii.p, Вы писали:

SP>у меня предубеждение против list. Всё-таки куча аллокаций на ровном месте. Почему бы просто не запомнить позицию вставленного элемента?

Можно std::deque использовать.

Здравствуйте, sergii.p, Вы писали:

SP>у меня предубеждение против list. Всё-таки куча аллокаций на ровном месте.

Кастомный аллокатор, который делает pre-alloc достаточного размера и затем просто возвращает адреса?

Здравствуйте, Mr.Delphist, Вы писали:

MD>Кастомный аллокатор, который делает pre-alloc достаточного размера и затем просто возвращает адреса?

этот кастомный аллокатор называется vector

Здравствуйте, sergii.p, Вы писали:

SP>этот кастомный аллокатор называется vector

Да, но нет, хотя и да

Иногда у вектора есть минус — необходимость сдвига контента если средний элемент удаляется. На маленьких размерах это незаметно, т.к. кэш и предиктивное чтение творят чудеса. Но если размер побольше, то ой. В такой ситуации, список может дать меньше тормозов, даже не взирая на indirection и отсутствие упорядоченности внутри блока памяти. Ну и сюда же вопрос сохранности итераторов — тоже может быть полезно. В общем, думаем, взвешаваем, измеряем.

Здравствуйте, 00011011, Вы писали:

0>Довольно простая задача — есть список, есть функция которая может добавить в конец этого списка произвольное число элементов (в т.ч. и ни одного).
0>Я хочу чтобы функция возвращала итератор на первый добавленный элемент, или end() если элементы не были добавлены — с тем, чтобы вызывающий код мог пройтись по этим новым элементам, не затрагивая старые.
0>Но оказалось, что push_back не возвращает ничего;
Возьми после первой вставки rbegin

Здравствуйте, Igore, Вы писали:

I>Возьми после первой вставки rbegin

и после второй вставки итератор может быть не валиден

Здравствуйте, sergii.p, Вы писали:

SP>Здравствуйте, Igore, Вы писали:

I>>Возьми после первой вставки rbegin

SP>и после второй вставки итератор может быть не валиден

std::list не инвалидирует итераторы и ссылки при добавлении, если верить документации.

Здравствуйте, Sm0ke, Вы писали:

S>Здравствуйте, sergii.p, Вы писали:

SP>>Здравствуйте, Igore, Вы писали:

I>>>Возьми после первой вставки rbegin

SP>>и после второй вставки итератор может быть не валиден

S>std::list не инвалидирует итераторы и ссылки при добавлении, если верить документации.

Совершенно верно, инвалидации итератора не будет.

Однако работать "как надо" это не будет все равно. `rbegin()` вернет reverse iterator, базирующийся на `end()`. И в процессе добавления элементов в список, полученный итератор будет продолжать базироваться на `end()` итераторе (который тоже не инвалидируется и остается неизменным в процессе добавления). То есть такой итератор будет "прилеплен" к концу списка. И после завершения добавления полученный из `rbegin()` reverse iterator будет ссылаться на последний вставленный элемент, а не на первый.

#include <list>
#include <iostream>

int main() 
{
  std::list<int> l = { 1, 2, 3 };
  auto it = l.rbegin();
  std::cout << *it << std::endl;
  l.push_back(4);
  std::cout << *it << std::endl;
  l.push_back(5);
  std::cout << *it << std::endl;
}

Получим

3
4
5

Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>Однако работать "как надо" это не будет все равно. `rbegin()` вернет reverse iterator, базирующийся на `end()`. И в процессе добавления элементов в список, полученный итератор будет продолжать базироваться на `end()` итераторе (который тоже не инвалидируется и остается неизменным в процессе добавления). То есть такой итератор будет "прилеплен" к концу списка. И после завершения добавления полученный из `rbegin()` reverse iterator будет ссылаться на последний вставленный элемент, а не на первый.
Да, точно, значит надо еще раз сдвинуться чтобы вместе с rbegin не уезжать, но порядок будет обратный

#include <list>
#include <iostream>

int main() 
{
  std::list<int> l = { 1, 2, 3 };
  l.push_back(4);
  auto tmp = l.rbegin();
  tmp++;
  l.push_back(5);
  l.push_back(6);
  
  for( auto it = l.rbegin(); it != tmp; ++it )
  {
      std::cout << *it << std::endl;
  }
  // 6 5 4
}

Здравствуйте, 00011011, Вы писали:

0>Довольно простая задача — есть список, есть функция которая может добавить в конец этого списка произвольное число элементов (в т.ч. и ни одного).
0>Я хочу чтобы функция возвращала итератор на первый добавленный элемент, или end() если элементы не были добавлены — с тем, чтобы вызывающий код мог пройтись по этим новым элементам, не затрагивая старые.
0>Но оказалось, что push_back не возвращает ничего;
0>Если брать итератор end() вообще перед добавлением, то после добавления элемента он не указывает на первый добавленный элемент (что было бы логично для массивов, но разумеется не работает для списков, к сожалению).
0>Как красиво и эффективно решить эту задачу?

Если я правильно понимаю задачу, в списке уже есть эта функция: list::insert #4.

Здравствуйте, Mr.Delphist, Вы писали:

MD>Здравствуйте, sergii.p, Вы писали:

SP>>у меня предубеждение против list. Всё-таки куча аллокаций на ровном месте.

MD>Кастомный аллокатор, который делает pre-alloc достаточного размера и затем просто возвращает адреса?

Тут надо замерять по скорости нужен ли такой аллокатор? По сути операционная система сама должна выдавать эти адреса оптимально, будет ли выигрыш?
Потом при освобождении надо в аллокаторе помечать элемент, как освободившийся, чтобы потом снова его выдавать при выделении, но не может его вернуть операционной системе отдельно без всего pre-alloc блока. Стоит ли заморачиваться с такой хитровыфигованной системой, когда проще сделать в лоб?