STL list sort() limit
-
Hi, Can anyone tell me if there is a limit of 2^15 (32768) items that can be sorted in a list using the list function sort()? I am trying the following code in Visual C++ 6 on Windows 2000. std::list TestList; for (int i=0; i<40000; i++) TestList.push_back(i); int nSize = TestList.size(); test.sort(); int nSize2 = TestList.size(); nSize is 40000. nSize2 is 7232. The difference between the two values is always 32768. Less than 32768 values sorts fine. NOTE: max_size() returns a value of > 100000000. I could not find any information that mentions this limit but it is clearly there. Can anyone suggest an alternative?
-
Hi, Can anyone tell me if there is a limit of 2^15 (32768) items that can be sorted in a list using the list function sort()? I am trying the following code in Visual C++ 6 on Windows 2000. std::list TestList; for (int i=0; i<40000; i++) TestList.push_back(i); int nSize = TestList.size(); test.sort(); int nSize2 = TestList.size(); nSize is 40000. nSize2 is 7232. The difference between the two values is always 32768. Less than 32768 values sorts fine. NOTE: max_size() returns a value of > 100000000. I could not find any information that mentions this limit but it is clearly there. Can anyone suggest an alternative?
It looks like there is a bug in the list sort routine which ships with VC 6.0. Looking at the source in , it appears that the internal array used to process the merge sorts is not being handled properly when the array is full. You might be able to find a fix for this by getting an upgrade to the STL that you use. This isn't a bad idea, as there are a number of problems with the STL that ships with VC 6.0. For a quick fix, you could patch the header file so that the sort works correctly. Or you could write your own sort routine which fixes the problem. (just glancing at it, it appears that the sort could be fixed by changing the following sequence:
if (_I == _MAXN) _A[_I].merge(_X); else {_A[_I].swap(_X); if (_I == _N) ++N; }}to the following:if (_I == _MAXN) _A[_I].merge(_X); else _A[_I].swap(_X); if (_I == _N) ++N; }Note: I only briefly tested this, but it appears to work. The other choice (if you are going change ) is to increase the const _MAXN to a larger number, so that the temporary array can fit more elements. Each increase of this number doubles the size of the list that can be sorted. By setting this to 32, it should be able to handle any size list that you could create. Best regards, John -
Hi, Can anyone tell me if there is a limit of 2^15 (32768) items that can be sorted in a list using the list function sort()? I am trying the following code in Visual C++ 6 on Windows 2000. std::list TestList; for (int i=0; i<40000; i++) TestList.push_back(i); int nSize = TestList.size(); test.sort(); int nSize2 = TestList.size(); nSize is 40000. nSize2 is 7232. The difference between the two values is always 32768. Less than 32768 values sorts fine. NOTE: max_size() returns a value of > 100000000. I could not find any information that mentions this limit but it is clearly there. Can anyone suggest an alternative?
This is a known bug. See the following page for how to patch your VC6 STL headers for a number of known bugs: http://www.dinkumware.com/vc_fixes.html[^] In particular, see the "Fix to <list>" section. - Mike