libs/intrusive/example/doc_positional_insertion.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2009-2013
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12 //[doc_positional_insertion
  13 #include <boost/intrusive/set.hpp>
  14 #include <vector>
  15 #include <algorithm>
  16 #include <cassert>
  17
  18 using namespace boost::intrusive;
  19
  20 //A simple class with a set hook
  21 class MyClass : public set_base_hook<>
  22 {
  23    public:
  24    int int_;
  25
  26    MyClass(int i) :  int_(i) {}
  27    friend bool operator< (const MyClass &a, const MyClass &b)
  28       {  return a.int_ < b.int_;  }
  29    friend bool operator> (const MyClass &a, const MyClass &b)
  30       {  return a.int_ > b.int_;  }
  31 };
  32
  33 int main()
  34 {
  35    //Create some ORDERED elements
  36    std::vector<MyClass> values;
  37    for(int i = 0; i < 100; ++i)  values.push_back(MyClass(i));
  38
  39    {  //Data is naturally ordered in the vector with the same criteria
  40       //as multiset's comparison predicate, so we can just push back
  41       //all elements, which is more efficient than normal insertion
  42       multiset<MyClass> mset;
  43       for(int i = 0; i < 100; ++i)  mset.push_back(values[i]);
  44
  45       //Now check orderd invariant
  46       multiset<MyClass>::const_iterator next(mset.cbegin()), it(next++);
  47       for(int i = 0; i < 99; ++i, ++it, ++next) assert(*it < *next);
  48    }
  49    {  //Now the correct order for the set is the reverse order
  50       //so let's push front all elements
  51       multiset<MyClass, compare< std::greater<MyClass> > > mset;
  52       for(int i = 0; i < 100; ++i)  mset.push_front(values[i]);
  53
  54       //Now check orderd invariant
  55       multiset<MyClass, compare< std::greater<MyClass> > >::
  56          const_iterator next(mset.cbegin()), it(next++);
  57       for(int i = 0; i < 99; ++i, ++it, ++next) assert(*it > *next);
  58    }
  59    {  //Now push the first and the last and insert the rest
  60       //before the last position using "insert_before"
  61       multiset<MyClass> mset;
  62       mset.insert_before(mset.begin(), values[0]);
  63       multiset<MyClass>::const_iterator pos =
  64          mset.insert_before(mset.end(), values[99]);
  65       for(int i = 1; i < 99; ++i)  mset.insert_before(pos, values[i]);
  66
  67       //Now check orderd invariant
  68       multiset<MyClass>::const_iterator next(mset.cbegin()), it(next++);
  69       for(int i = 0; i < 99; ++i, ++it, ++next) assert(*it < *next);
  70    }
  71
  72    return 0;
  73 }
  74 //]