c++listcontainersemplaceforward-list

Emplacing to the back of a forward_list segfaults


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?


Solution

  • 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).