C++Guns – RoboBlog


C++ Guns: Solve std::forward_list no size() method problem

Filed under: Allgemein — Tags: — Thomas @ 21:08

Why has forward_list no size() method?

In short: Its about performance. A single linked list size() function has a asymptotic complexity of O(n). We do not usually need something like that. So we don't have something.
The second reason is: For a O(1) size() function, it would increase the size of std::forward_list by 8 byte. We don't pay for what we don't need.

N2543 is the proposal, and it has a detailed discussion about size() [1]

The choice between Option 3 [not providing size()] and Option 2 [providing a O(1) size()] is more a matter of judgment. I have chosen Option 3 for the same reason that I chose insert-after instead of insert-before: Option 3 is more consistent with the goal of zero overhead compared to a hand-written C-style linked list. Maintaining a count doubles the size of a forward_list object (one word for the list head and one for the count), and it slows down every operation that changes the number of nodes. In most cases this isn't a change in asymptotic complexity (the one change in asymptotic complexity is in one of the forms of splice), but it is nonzero overhead. It's a cost that all users would have to pay for, whether they need this feature or not, and, for users who care about maintaining a count, it's just as easy to maintain it outside the list, by incrementing the count with every insert and decrementing it with every erase, as it is to maintain the count within the list.

But there is a very simple solution for this problem: A non-member size() function for std::forward_list as they are introduced in C++17.

namespace std {
    template<typename T>
    size_t size(const std::forward_list<T>& list) {
        size_t i=0;
        for(const auto& x : list) {
        return i;

But there is one problem: The std::size() now take O(1) or O(n) time, depending on the passed container.

[1] https://stackoverflow.com/questions/31822494/c-stl-why-has-forward-list-no-size-method

No Comments

No comments yet.

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress