Modify

Ticket #2807 (closed Patches: fixed)

Opened 5 years ago

Last modified 5 years ago

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

Reported by: andysem Owned by: igaztanaga
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

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

Change History

Changed 5 years ago by andysem

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

comment:1 Changed 5 years ago by andysem

  • Type changed from Bugs to Patches

comment:2 Changed 5 years ago by andysem

  • Summary changed from list::sort is not stable to list::sort and slist::sort are not stable

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

Changed 5 years ago by andysem

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

comment:3 Changed 5 years ago by igaztanaga

  • Status changed from new to closed
  • Resolution set to fixed

Applied a modified patch. Revision 51971.

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
The resolution will be deleted. Next status will be 'reopened'
Author


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

 
Note: See TracTickets for help on using tickets.