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.
I found this same problem while debugging my application. I did a quick google search to see if it was documented and if there was a work around other than not using list::sort for big lists.
Still haven’t found a work around, but at least I know that someone else gets a problem with it too.
Al,
There is a fix at this MSDN page, provided you are able to change your STL headers and recompile:
http://support.microsoft.com/kb/240014/en-us
I’m happy to see that I’m not the last person still using VS6.0!