Modify

Opened 8 years ago

Closed 8 years ago

#2807 closed Patches (fixed)

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

Reported by: Andrey Semashev Owned by: Ion Gaztañaga
Milestone: Boost 1.39.0 Component: intrusive
Version: Boost 1.38.0 Severity: Showstopper
Keywords: list sort stable Cc:

Description

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, 

Attachments (2)

list.hpp.patch (536 bytes) - added by Andrey Semashev 8 years ago.
The patch that fixes the problem (against branches/release)
slist.hpp.patch (515 bytes) - added by Andrey Semashev 8 years ago.
The patch that fixes the problem (against branches/release)

Download all attachments as: .zip

Change History (5)

Changed 8 years ago by Andrey Semashev

Attachment: list.hpp.patch added

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

comment:1 Changed 8 years ago by Andrey Semashev

Type: BugsPatches

comment:2 Changed 8 years ago by Andrey Semashev

Summary: list::sort is not stablelist::sort and slist::sort are not stable

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

Changed 8 years ago by Andrey Semashev

Attachment: slist.hpp.patch added

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

comment:3 Changed 8 years ago by Ion Gaztañaga

Resolution: fixed
Status: newclosed

Applied a modified patch. Revision 51971.

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain Ion Gaztañaga.
The resolution will be deleted.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.