[Boost-bugs] [Boost C++ Libraries] #2807: list::sort is not stable

Subject: [Boost-bugs] [Boost C++ Libraries] #2807: list::sort is not stable
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2009-02-27 14:44:12

#2807: list::sort is not stable
------------------------------+---------------------------------------------
 Reporter:  andysem           |       Owner:  igaztanaga 
     Type:  Bugs              |      Status:  new        
Milestone:  Boost 1.39.0      |   Component:  intrusive  
  Version:  Boost 1.38.0      |    Severity:  Showstopper
 Keywords:  list sort stable  |  
------------------------------+---------------------------------------------
 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,
 }}}

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/2807>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.