Why does std::list::pop_front seem slow for large lists?

Question

I'm trying to limit the size of a list by deleting nodes from the front before appending new nodes to the end. I expected the speed to be constant regardless of list size, but I see longer execution times for larger lists. Am I implementing it wrong, or is pop_front actually not constant time?

The following code executes with these results:

$ time ./testlist 2 1000000
MAX is 2
NUM is 1000000
DELETED 999998

real    0m0.835s

$ time ./testlist 10 1000000
MAX is 10
NUM is 1000000
DELETED 999990

real    0m1.070s

$ time ./testlist 100 1000000
MAX is 100
NUM is 1000000
DELETED 999900

real    0m3.612s

$ time ./testlist 1000 1000000
MAX is 1000
NUM is 1000000
DELETED 999000

real    0m28.838s

The source code:

#include <iostream>
#include <stdlib.h>
#include <list>

int deletes=0;
std::list<int> l;
void insert(int x, size_t maxsize) {
    if (l.size() == maxsize)
    {
        l.pop_front();
        deletes++;
    }
    l.push_back(x);
}
int main(int argc, char *argv[])
{
    size_t v = atoi(argv[1]);
    size_t n = atoi(argv[2]);
    std::cout << "MAX is " << v << std::endl;
    std::cout << "NUM is " << n << std::endl;
    for (size_t i=0; i<n; i++)
    {
        insert(i, v);
    }
    std::cout << "DELETED " << deletes << std::endl;

    return 0;
}

Answer 1

std::list::size() takes linear time (GCC 4.9.2), even in optimized builds. Use this instead:

#include <iostream>
#include <stdlib.h>
#include <list>
#include <deque>

int deletes=0;
int size=0;
std::list<int> l;
void insert(int x, size_t maxsize) {
    if (size == maxsize)
    {
        l.pop_front();
        deletes++;
    size--;
    }
    size++;
    l.push_back(x);
}
int main(int argc, char *argv[])
{
    size_t v = atoi(argv[1]);
    size_t n = atoi(argv[2]);
    std::cout << "MAX is " << v << std::endl;
    std::cout << "NUM is " << n << std::endl;
    for (size_t i=0; i<n; i++)
    {
        insert(i, v);
    }
    std::cout << "DELETED " << deletes << std::endl;

    return 0;
}

Notice: deque might be faster (if the implementation uses an array, else they're the same, however, deque provides the same performance as list with this optimization — YMMV)

Addendum: C++11 does not seem to provide leeway for a O(n) size() as it says in 23.2.1 General container requirements:

Expression: a.size()

Complexity: constant

Prior to C++11 it said "constant or linear" in this place, which caused your performance issue in this specific case.

GCC 5.0 will fix this issue: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561