Welcome to Programming and Data Structures

As with vector, the functions that are provided give a hint as to what is efficient in the container. For example, both kinds of linked lists provide push_front and pop_front functions to add and remove elements at the start of the list. (std::vector does not provide those functions, because they would be inefficient.) The std::list also provides push_back and pop_back functions to add and remove elements at the end of the list efficiently. The std::forward_list does not provide those functions, because adding or removing elements at the end of a singly linked list is not efficient.

The C++ standard containers generally do not specify exactly how the container must be implemented. Instead they make guarantees about the performance of various operations. For example, the documentation for std::list specifies that inserting or removing elements at either the start or end of the list takes constant time, \(O(1)\text{.}\)

Those constraints force some implementation choices. For example, to guarantee that adding an element at the end of the list takes constant time, the std::list implementation must keep a pointer to the tail of the list. Otherwise it would have to walk through the entire list to find the end, which would take linear time, \(O(n)\text{.}\) But, other implementation details are left up to the library implementer. One implementation of std::list might use dummy nodes, while another might not.

The fact that std::forward_list does not provide push_back function indicates that a tail pointer is likely not required. An implementer might choose to add one, but it would not be required to meet the performance guarantees of the container. Similarly, std::forward_list does not provide a size method, indicating that a size member variable is likely not required in implementations.

Here is a simple sample that uses std::list:

If you try changing line 8 to declare a forward_list instead of a list, you will see that some that push_back becomes a compilation error.