STLひどい、、、

sample.cpp

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <list>
using namespace std;

int
main (
  int   argc,
  char *argv[ ]
  )
{
  list<size_t> lis;
  size_t i, j;

  for ( i = 1; i < 1000000000; i *= 10 )
  {
    clock_t clk;

    for ( j = 0; j < i; ++j )
      lis.push_back ( j );

    clk = clock ( );
    printf ( "%10zu", lis.size ( ) );
    clk = clock ( ) - clk;
    printf ( " %zu\n", clk );
  }

  return ( EXIT_SUCCESS );
}

/** RESULT:
         1 0
        11 0
       111 0
      1111 0
     11111 0
    111111 10000
   1111111 10000
  11111111 80000
 111111111 750000
*/