id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
2807,list::sort and slist::sort are not stable,Andrey Semashev,Ion Gaztañaga,"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, 
}}}

",Patches,closed,Boost 1.39.0,intrusive,Boost 1.38.0,Showstopper,fixed,list sort stable,