pavelkryukov/forward_list2

C++ std::forward_list with push_back and before_end

forward_list2

Wrapper around C++ std::forward_list which adds an iterator to the last element.

The idea has been proposed and discussed here: cpp-ru/ideas#487.

Extra functions

const_reference back() const;

const_iterator before_end() const noexcept;
const_iterator cbefore_end() const noexcept;

void push_back(const T& value);
void push_back(T&& value);

template<class... Args>
reference emplace_back(Args&&... args);

Price

• Compute time overheads to maintain the iterator to the last element.
• Extra O(N) traversals on copy assignment and sorting.
• Memory size overhead on empty container:

static_assert(sizeof(std::forward_list<int>) == sizeof(void*));
static_assert(sizeof(forward_list2<int>) == 2 * sizeof(void*));

Limitations

• No reference back(); is available since it would require passing non-constant iterator to erase_after.

Impact

• Identified and fixed PR libstdc++/103853.