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?

回答1:

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);

回答2:

I recommend against std::forward_list just like I recommend against std::list in almost all situations. Personally, I've never found a situation in my code where a linked list was the best data structure.

In C++, your default go-to data collection should be std::vector. It gives you efficient push_back, if that is what you really need. It technically does not give you efficient deletion and insertion from the middle if you only look at abstract big-O complexity measurements of that one operation. In the real world, however, std::vector still wins even for inserting and deleting in the middle.

As an example, Bjarne Stroustrup created a test of a 100,000 element std::list vs. std::vector. He would search each for an element and delete it. Then he would find an insertion point and insert into the middle. He could have use a binary search on the std::vector, but did not to make the comparison 'more fair'.

The results show a strong win for std::vector, even in this situation where std::list is supposed to be strong. Simply traversing the std::list takes so much longer because of how far apart in memory all of the objects are. std::list is not cache-friendly, which is possibly the most important thing for modern processors.

The complete talk by Bjarne Stroustrup

Thorough explanation of the effects, with benchmarks at multiple sizes

Note that this second link here gives some situations of where you may possibly want to use a std::list, such as when the size of the elements is large. However, I've been in a situation where I have many elements in a particular order and needed to delete some.

These elements were larger than any built-in type, but not huge, perhaps 20-30 bytes each on a 32-bit computer). The number of elements was large enough so that my entire data structure was a few hundred MiB. The data collection was a set of values that could theoretically be a valid based on currently known information. The algorithm iterated over all elements and removed elements that could no longer be valid based on new information, with each pass probably deleting somewhere around 80% of the remaining elements.

My first implementation was a straightforward std::vector approach where I deleted invalid elements as I traversed. This worked for small test data sets, but when I tried to do the real thing, it was too slow to be useful. I switched to a std::list as the container, but used the same algorithm, and I saw significant performance improvements. However, it was still too slow to be useful. The winning change was to switch back to a std::vector, but instead of deleting elements in place that were bad, I created a new std::vector, and any elements I found that were good were put into that std::vector, and then at the end of the function I would simply discard the old std::vector and use the new one, and this gave me about as much of a speed up over the std::list as the std::list gave me over my original std::vector implementation, and this was just fast enough to be useful.

回答3:

There is no push_back because the list doesn't keep track of the back of the list, only the front.

You could write a wrapper around the list that maintains an iterator to the last element, and implements push_back using either insert_after or push_front depending on whether the list is empty. This will get rather complicated if you want to support the more complex operations (e.g. sort and splice_after).

Alternatively, if you don't need push_back to be fast, it's straightforward to do it in linear time.

Unless memory is extremely tight, the best solution is to use list. This has the same performance characteristics as forward_list, and is bidirectional, supporting push_back as well as push_front; the cost is an extra pointer per element.

回答4:

The point of std::forward_list is to be an ultra-stripped-down version of std::list, so it doesn't store an iterator to the last element. If you need one, you'll have to maintain it yourself, like so:

forward_list<int> a;

auto it = a.before_begin();

for(int i = 0; i < 10; ++i)
    it = a.insert_after(it, i);

回答5:

Unfortunatelly I can't add a comment (low reputation) but I just wanted to mention that one of the forward_list & list advantages is that insert-delete operations do not invalidate iterators. I had an application where collection of elements was growing while iterating and processing individual elements. Absence of iterator invalidation allowed me to implement segment scan (begin of the list as start of the segment and begin of the last segment as end).