Sambal

Update: This is a known bug.

In the process of gathering my data for the next post in the stl lower_bound() series, I ran into some weird timings. Basically I was seeing a linear increase until there were 32000 elements in my list, and then at 33000 the timing suddenly dropped by a factor of over 10.

I traced it back to a bug in MSVC 6.0 list::sort. I don’t know what the mechanics of the bug are, and I haven’t confirmed it widely, so I’d appreciate some feedback here. The two machines I’ve tried it on were running MSVC6.0 SP6 and had the Microsoft Platfrom SDK from February 2003 installed as well.

The repro code is below. Create a new Visual C++ Win32 console project, create an empty project, add file main.cpp, and compile. I get an assertion failure on line 34, following the second list.sort(). That is: list.sort() succeeds when there are 32767 elements in the list, but when the 32768th is added, the sort algorithm seems to be deleting 32768 elements.

#include <list>
#include <algorithm>

#include <assert.h>

using namespace std;

struct counter
{
  typedef int result_type;

  counter() : n(0) {}
  result_type operator()() { return n++; }

  result_type n;
};

int main()
{
  list<int> l;

  generate_n( back_inserter( l ), 32767, counter() );

  assert( l.size() == 32767 );
  l.sort();
  assert( l.size() == 32767 );

  l.clear();

  generate_n( back_inserter( l ), 32768, counter() );

  assert( l.size() == 32768 );
  l.sort();
  assert( l.size() == 32768 );

  l.clear();

  return 0;
}

If anyone else can reproduce this with MSVC6.0 SP6, please let me know.