list::sort and slist::sort are not stable

[Andrey Semashev]

The intrusive::list::sort method does not preserve the relative order of equivalent elements. In fact, it makes it the reverse.

The following code snippet shows the problem:

#include <iostream>
#include <boost/checked_delete.hpp>
#include <boost/intrusive/options.hpp>
#include <boost/intrusive/list.hpp>
#include <boost/intrusive/list_hook.hpp>

namespace bi = boost::intrusive;

typedef bi::list_base_hook<
	bi::link_mode< bi::auto_unlink >
> BaseHook_t;

struct MyData :
	public BaseHook_t
{
	struct OrderByKey
	{
		typedef bool result_type;
		result_type operator() (MyData const& left, MyData const& right) const
		{
			return left.m_Key < right.m_Key;
		}
	};

	int m_Key;
	int m_Data;

	explicit MyData(int k, int d) : m_Key(k), m_Data(d) {}
};


int main(int, char*[])
{
	typedef bi::list<
		MyData,
		bi::base_hook< BaseHook_t >,
		bi::constant_time_size< false >
	> List_t;

	List_t l;

	MyData* p = 0;
	p = new MyData(1, 11); l.push_back(*p);
	p = new MyData(1, 12); l.push_back(*p);
	p = new MyData(1, 13); l.push_back(*p);
	p = new MyData(1, 14); l.push_back(*p);

	p = new MyData(3, 31); l.push_back(*p);
	p = new MyData(3, 32); l.push_back(*p);
	p = new MyData(3, 33); l.push_back(*p);
	p = new MyData(3, 34); l.push_back(*p);

	p = new MyData(2, 21); l.push_back(*p);
	p = new MyData(2, 22); l.push_back(*p);
	p = new MyData(2, 23); l.push_back(*p);
	p = new MyData(2, 24); l.push_back(*p);

	l.sort(MyData::OrderByKey());

	for (List_t::const_iterator it = l.begin(); it != l.end(); ++it)
	{
		std::cout << it->m_Data << ", ";
	}

	std::cout << std::endl;

	l.clear_and_dispose(boost::checked_deleter< MyData >());

	return 0;
}

It prints:

14, 13, 12, 11, 24, 23, 22, 21, 34, 33, 32, 31, 

The expected output is:

11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 

[Andrey Semashev]

The patch that fixes the problem (against branches/release)

[Andrey Semashev]

The slist::sort function has precisely the same problem.

[Andrey Semashev]

The patch that fixes the problem (against branches/release)

[Ion Gaztañaga]

Applied a modified patch. Revision 51971.