This must be a stupid oversight on my part, but how can I add to the back of a std::forward_list
? I know usually the forward_list
implementation doesn't contain an iterator to the back, but according to cppreference the standard forward_list
is required to have one (constant time), so I thought I might as well use it.
Now, the way this is supposed to work is that emplace_after()
will look at the node before the given one and re-link its next
pointer. This makes it clear that I need to insert after the node before cend()
, so do std::prev()
. But, if there's no element in the list at all, this will result in a node before begin()
, which is still perfectly covered by the implementation. The given example of emplace_after()
does so itself. So, I thought I would be fine, but this segfaults (Demo):
#include <memory_resource>
#include <cstdio>
#include <ranges>
#include <algorithm>
#include <forward_list>
struct entity
{
entity()
: mylist_{ std::pmr::polymorphic_allocator<std::byte>{}}
{}
auto add(int i) {
// printf("start = %p, end = %p", &*mylist_.cbegin(), &*mylist_.cend());
auto it = mylist_.emplace_after(std::prev(mylist_.cend()));
*it = i;
}
auto print() {
std::ranges::for_each(mylist_, [](int i){ printf("%d\n", i); });
}
std::pmr::forward_list<int> mylist_;
};
int main()
{
entity e;
e.add(4);
e.print();
}
I checked start
and end
iterators with the commented-out print
statement, and they point to the same address.
What am I missing?
std::forward_list
only provides forward iterators which means you can't use std::prev
.
libstdc++ doesn't implement type requirements for iterators by default when calling std::prev
. The implementation of std::prev(it)
is to just call std::advance(it, -1)
. For forward iterators std::advance
has a debug asssertion to check that the distance is positive (but debug assertions won't normally be enabled), the implementation then does:
while (distance--)
{
iterator++;
}
As distance
is negative this will iterate quite a few times but actually crashes on the first increment as mylist_.cend()++
is undefined.
MSVC does better here and rejects your code: https://godbolt.org/z/e4G3M9n44.
You could solve this by having entity
store a reference to the last element but you'd be better off just using a container that better meets your requirements like std::list
or even std::vector
(due to lack of memory locality linked lists often have poor performance on modern CPUs).