9

forward_list is a single linked list (unlike the standard list container). list has functions to insert both in front and back but forward_list hasn't a function to insert an element in the back (something like push_back). Why isn't it possible to insert an element at the back of the list?

Mark B
  • 95,107
  • 10
  • 109
  • 188
Johnny Pauling
  • 12,701
  • 18
  • 65
  • 108
  • 3
    @ALJIMohamed I wish I could downvote comments – David Apr 02 '13 at 13:40
  • 1
    Probably because it would be an O(N) operation. It would have to start at the front and step all the way to the back. – juanchopanza Apr 02 '13 at 13:41
  • 4
    Probably redundant with http://stackoverflow.com/q/8742462/1758762 – Leo Chapiro Apr 02 '13 at 13:42
  • @juanchopanza and why would it be an O(N) operation? It should be sufficient to allocate the element, change its pointer to the ex-first element and point the start of the list to this new element – Johnny Pauling Apr 02 '13 at 13:43
  • 1
    The back of the list is not the beginning. – R. Martinho Fernandes Apr 02 '13 at 13:45
  • 1
    You are asking about inserting an element in the *back* of the list (although the question title suggests otherwise). The back is the end of the list, not the beginning. You only have a handle to the beginning. `std::forward_list` is designed to be very minimal, so it doesn't hold any data that would make an insertion into the back efficient. – juanchopanza Apr 02 '13 at 13:46
  • It could pretty easily hold an iterator to the back to allow for an O(1) `push_back` and `back`. I guess they were more interested in dropping a few bytes. – David Apr 02 '13 at 13:50
  • @JohnnyPauling You're mixing up insertion at beginning (question title, your comment) and insertion at end (question body, `push_back()`). Which of these are you actually asking about? – Angew is no longer proud of SO Apr 02 '13 at 13:50
  • @Dave - that's not true. what if you have an iterator to the last element and you wished to remove it. now it's o(1). but if you need to update the suggested iterator to the end to allow `push_back` it will be O(N) – Roee Gavirel Apr 02 '13 at 13:56
  • 1
    @RoeeGavirel I didn't follow your wording exactly, but: erasing the last element would be O(n), adding an element to the end would be O(1) – David Apr 02 '13 at 13:58

1 Answers1

10

It's a deliberate design decision that forward_list should carry no overhead when compared to a singly-linked list. This is noted in the C++11 standard (23.3.4.1):

Note: It is intended that forward_list have zero space or time overhead relative to a hand-written C-style singly linked list. Features that would conflict with that goal have been omitted.

Maintaining a pointer to the end of the list would add both space overhead (for the pointer itself) and time overhead (updating the pointer when elements are inserted or erased at the end of the list).

Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
  • 4
    This is rather misleading. It is completely fine for a singly-linked list to maintain a pointer to the end of the list or have an extra variable holding amount of items or other stuff. And having them in `forward_list` won't add any overhead compared to a "hand-written C-style singly linked list" with the same features. – user7860670 Feb 03 '19 at 11:43