Why does std::list::reverse have O(n) complexity?

Solution 1:

Hypothetically, reverse could have been O(1). There (again hypothetically) could have been a boolean list member indicating whether the direction of the linked list is currently the same or opposite as the original one where the list was created.

Unfortunately, that would reduce the performance of basically any other operation (albeit without changing the asymptotic runtime). In each operation, a boolean would need to be consulted to consider whether to follow a "next" or "prev" pointer of a link.

Since this was presumably considered a relatively infrequent operation, the standard (which does not dictate implementations, only complexity), specified that the complexity could be linear. This allows "next" pointers to always mean the same direction unambiguously, speeding up common-case operations.

Solution 2:

It could be O(1) if the list would store a flag that allows swapping the meaning of the “prev” and “next” pointers each node has. If reversing the list would be a frequent operation, such an addition might be in fact useful and I don't know of any reason why implementing it would be prohibited by the current standard. However, having such a flag would make ordinary traversal of the list more expensive (if only by a constant factor) because instead of

current = current->next;

in the operator++ of the list iterator, you would get

if (reversed)
  current = current->prev;
else
  current = current->next;

which is not something you'd decide to add easily. Given that lists are usually traversed much more often than they are reversed, it would be very unwise for the standard to mandate this technique. Therefore, the reverse operation is allowed to have linear complexity. Do note, however, that t ∈ O(1) ⇒ t ∈ O(n) so, as mentioned earlier, implementing your “optimization” technically would be permitted.

If you come from a Java or similar background, you might wonder why the iterator has to check the flag each time. Couldn't we instead have two distinct iterator types, both derived from a common base type, and have std::list::begin and std::list::rbegin polymorphically return the appropriate iterator? While possible, this would make the whole thing even worse because advancing the iterator would be an indirect (hard to inline) function call now. In Java, you're paying this price routinely anyway, but then again, this is one of the reasons many people reach for C++ when performance is critical.

As pointed out by Benjamin Lindley in the comments, since reverse is not allowed to invalidate iterators, the only approach permitted by the standard seems to be to store a pointer back to the list inside the iterator which causes a double-indirect memory access.

Solution 3:

Surely since all containers that support bidirectional iterators have the concept of rbegin() and rend(), this question is moot?

It's trivial to build a proxy that reverses the iterators and access the container through that.

This non-operation is indeed O(1).

such as:

#include <iostream>
#include <list>
#include <string>
#include <iterator>

template<class Container>
struct reverse_proxy
{
    reverse_proxy(Container& c)
    : _c(c)
    {}

    auto begin() { return std::make_reverse_iterator(std::end(_c)); }
    auto end() { return std::make_reverse_iterator(std::begin(_c)); }

    auto begin() const { return std::make_reverse_iterator(std::end(_c)); }
    auto end() const { return std::make_reverse_iterator(std::begin(_c)); }

    Container& _c;
};

template<class Container>
auto reversed(Container& c)
{
    return reverse_proxy<Container>(c);
}

int main()
{
    using namespace std;
    list<string> l { "the", "cat", "sat", "on", "the", "mat" };

    auto r = reversed(l);
    copy(begin(r), end(r), ostream_iterator<string>(cout, "\n"));

    return 0;
}

expected output:

mat
the
on
sat
cat
the

Given this, it seems to me that the standards committee have not taken time to mandate O(1) reverse-ordering of the container because it's not necessary, and the standard library is largely built on the principle of mandating only what is strictly necessary while avoiding duplication.

Just my 2c.

Solution 4:

Because it has to traverse every node (n total) and update their data (the update step is indeed O(1)). This makes the whole operation O(n*1) = O(n).