c++c++11stdforward-list

std::forward_list and std::forward_list::push_back

I'd like to use std::forward_list

Because:

Forward list is a container which supports fast insertion and removal of elements from anywhere from the container

But there's no *std::forward_list::push_back* implementation.

Is there a high-performance way to add support for the one or no reason to do it?

Solution

  • std::forward_list supports fast insertion and removal, but not traversal to the end. To implement .push_back, you'll first need to get to the end of the list, which is O(N) and not fast at all, which is probably why it's not implemented.

     

    You could find the iterator to the last element by incrementing .before_begin N times

    auto before_end = slist.before_begin();
for (auto& _ : slist)
  ++ before_end;

    and then use .insert_after or .emplace_after to insert the element:

    slist.insert_after(before_end, 1234);