Итератор на только что добавленный элемент списка - C/C++

Здравствуйте, 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

Здравствуйте, 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.

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

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

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

0>>Как красиво и эффективно решить эту задачу?

D>Некрасиво, но вроде работает

D>

D>template <class T, class SequenceContainer>
D>typename std::list<T>::iterator insertMany(std::list<T>& lst, const SequenceContainer& sequence) {
D>    typename std::list<T>::iterator ret = lst.end();
D>    std::for_each(sequence.begin(), sequence.end(), [&](const T& item) {
D>        auto inserted = lst.insert(lst.end(), item);
D>        if (ret == lst.end()) {
D>            ret = inserted;
D>        }
D>    });
D>    return ret;
D>}
D>

Но у списка же итак есть 4-ая и 5-ая перегрузка функции insert() ...

template <class T, class SequenceContainer>
typename std::list<T>::iterator insertMany(std::list<T>& lst, const SequenceContainer& sequence) {
    return lst.insert(lst.end(), sequence.begin(), sequence.end() );
}

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

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

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

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

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

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

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

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

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

Довольно простая задача — есть список, есть функция которая может добавить в конец этого списка произвольное число элементов (в т.ч. и ни одного).
Я хочу чтобы функция возвращала итератор на первый добавленный элемент, или 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--;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

АТ>Однако работать "как надо" это не будет все равно. `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 блока. Стоит ли заморачиваться с такой хитровыфигованной системой, когда проще сделать в лоб?

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

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

Естественно, что бенчмарки наше всё в такой ситуации, но
1) Ходить к ОС ножками — явно недёшево, можно напороться на syscall. Косвенно на это намекают всякие фреймворки, которые сперва просят большой шмат памяти у системы, а затем обживаю его по надобности.
2) Само собой, ОС не знает, что там у нас с собственными внутренними аллокациями. С её точки зрения нам выдали целый кусок мяса, и вернуть лишь часть от него — никак (разве что попытаться сделать realloc на меньший размер, но тут гарантий опять же нет). Поэтому возвращать всё сразу, по ведомости ОС.

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

0>Как красиво и эффективно решить эту задачу?

Некрасиво, но вроде работает

template <class T, class SequenceContainer>
typename std::list<T>::iterator insertMany(std::list<T>& lst, const SequenceContainer& sequence) {
    typename std::list<T>::iterator ret = lst.end();
    std::for_each(sequence.begin(), sequence.end(), [&](const T& item) {
        auto inserted = lst.insert(lst.end(), item);
        if (ret == lst.end()) {
            ret = inserted;
        }
    });
    return ret;
}

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

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

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

MD>Естественно, что бенчмарки наше всё в такой ситуации, но
MD>1) Ходить к ОС ножками — явно недёшево, можно напороться на syscall. Косвенно на это намекают всякие фреймворки, которые сперва просят большой шмат памяти у системы, а затем обживаю его по надобности.

Так вот куда в приложении память утекла

Это оказывается фреймворки рвут куски от системы

Я конечно шучу тут, но и да, и нет.

MD>2) Само собой, ОС не знает, что там у нас с собственными внутренними аллокациями. С её точки зрения нам выдали целый кусок мяса, и вернуть лишь часть от него — никак (разве что попытаться сделать realloc на меньший размер, но тут гарантий опять же нет). Поэтому возвращать всё сразу, по ведомости ОС.

realloc — не работает
Надо определять rare case когда можно вернуть bucket (содержащий только не выданные итемы), и если он не last. Хотя после list.clear() это может быть и не так уж rare.
Сложность в чём. Вот вернули мы bucket, а он сразу опять понадобился. Значит придётся для Пула писать Trait автовозвращения Бакетов. Автоматом или по требованию.

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

I>Да, точно, значит надо еще раз сдвинуться чтобы вместе с rbegin не уезжать, но порядок будет обратный

Или так, с прямым порядком:

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

	От:	Андрей Тарасевич
	Дата:	26.01.22 17:44
	Оценка:	4 (2)

От:	Sm0ke	ksi
Дата:	23.01.22 04:08
Оценка:	+2

От:	Sm0ke	ksi
Дата:	04.02.22 11:00
Оценка:	6 (1)

	От:	Андрей Тарасевич
	Дата:	23.01.22 20:07
	Оценка:	+1

	От:	Mr.Delphist
	Дата:	24.01.22 10:07
	Оценка:

От:	Don Reba	https://stackoverflow.com/users/49329/don-reba
Дата:	27.01.22 12:57
Оценка:

	От:	00011011
	Дата:	22.01.22 07:58
	Оценка:

	От:	00011011
	Дата:	22.01.22 09:20
	Оценка:

	От:	sergii.p
	Дата:	22.01.22 15:21
	Оценка:

	От:	ομικρον
	Дата:	16.02.22 12:36
	Оценка: