← Back to branch summary

~ubuntu-branches/ubuntu/saucy/deal.ii/saucy

« back to all changes in this revision

Viewing changes to contrib/boost-1.46.1/include/boost/intrusive/sg_set.hpp

  • Committer: Package Import Robot
  • Author(s): "Adam C. Powell, IV", Adam C. Powell, IV, Christophe Trophime
  • Date: 2012-02-21 06:57:30 UTC
  • mfrom: (3.1.7 sid)
  • Revision ID: package-import@ubuntu.com-20120221065730-r2iz70lg557wcd2e
Tags: 7.1.0-1
http://bugs.debian.org/652057
http://bugs.debian.org/652058
http://bugs.debian.org/637655
http://bugs.debian.org/659245
[ Adam C. Powell, IV ]
* New upstream (closes: #652057).
* Updated to use PETSc and SLEPc 3.2, and forward-ported all patches.
* Removed NetCDF Build-Depends because it uses serial HDF5.
* Made Sacado cmath patch work with new configure.
* Moved -dev package symlink lines in rules to arch all section.

[ Christophe Trophime ]
* debian/rules:
   - add dh_strip --dbg-package to generate dbg package (closes: #652058)
   - add .install files to simplify rules
* Add support for mumps, arpack (closes: #637655)
* Add patch for slepc 3.2 (closes: #659245)

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/boost-1.46.1/include/boost/intrusive/sg_set.hpp
 
1
/////////////////////////////////////////////////////////////////////////////
 
2
//
 
3
// (C) Copyright Ion Gaztanaga 2007-2009
 
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
#ifndef BOOST_INTRUSIVE_SG_SET_HPP
 
13
#define BOOST_INTRUSIVE_SG_SET_HPP
 
14
 
 
15
#include <boost/intrusive/detail/config_begin.hpp>
 
16
#include <boost/intrusive/intrusive_fwd.hpp>
 
17
#include <boost/intrusive/sgtree.hpp>
 
18
#include <boost/intrusive/detail/mpl.hpp>
 
19
#include <iterator>
 
20
 
 
21
namespace boost {
 
22
namespace intrusive {
 
23
 
 
24
//! The class template sg_set is an intrusive container, that mimics most of 
 
25
//! the interface of std::set as described in the C++ standard.
 
26
//! 
 
27
//! The template parameter \c T is the type to be managed by the container.
 
28
//! The user can specify additional options and if no options are provided
 
29
//! default options are used.
 
30
//!
 
31
//! The container supports the following options:
 
32
//! \c base_hook<>/member_hook<>/value_traits<>,
 
33
//! \c constant_time_size<>, \c size_type<> and
 
34
//! \c compare<>.
 
35
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
36
template<class T, class ...Options>
 
37
#else
 
38
template<class Config>
 
39
#endif
 
40
class sg_set_impl
 
41
{
 
42
   /// @cond
 
43
   typedef sgtree_impl<Config> tree_type;
 
44
   //! This class is
 
45
   //! non-copyable
 
46
   sg_set_impl (const sg_set_impl&);
 
47
 
 
48
   //! This class is
 
49
   //! non-assignable
 
50
   sg_set_impl &operator =(const sg_set_impl&);
 
51
 
 
52
   typedef tree_type implementation_defined;
 
53
   /// @endcond
 
54
 
 
55
   public:
 
56
   typedef typename implementation_defined::value_type               value_type;
 
57
   typedef typename implementation_defined::value_traits             value_traits;
 
58
   typedef typename implementation_defined::pointer                  pointer;
 
59
   typedef typename implementation_defined::const_pointer            const_pointer;
 
60
   typedef typename implementation_defined::reference                reference;
 
61
   typedef typename implementation_defined::const_reference          const_reference;
 
62
   typedef typename implementation_defined::difference_type          difference_type;
 
63
   typedef typename implementation_defined::size_type                size_type;
 
64
   typedef typename implementation_defined::value_compare            value_compare;
 
65
   typedef typename implementation_defined::key_compare              key_compare;
 
66
   typedef typename implementation_defined::iterator                 iterator;
 
67
   typedef typename implementation_defined::const_iterator           const_iterator;
 
68
   typedef typename implementation_defined::reverse_iterator         reverse_iterator;
 
69
   typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
 
70
   typedef typename implementation_defined::insert_commit_data       insert_commit_data;
 
71
   typedef typename implementation_defined::node_traits              node_traits;
 
72
   typedef typename implementation_defined::node                     node;
 
73
   typedef typename implementation_defined::node_ptr                 node_ptr;
 
74
   typedef typename implementation_defined::const_node_ptr           const_node_ptr;
 
75
   typedef typename implementation_defined::node_algorithms          node_algorithms;
 
76
 
 
77
   /// @cond
 
78
   private:
 
79
   tree_type tree_;
 
80
   /// @endcond
 
81
 
 
82
   public:
 
83
   //! <b>Effects</b>: Constructs an empty sg_set. 
 
84
   //!   
 
85
   //! <b>Complexity</b>: Constant. 
 
86
   //! 
 
87
   //! <b>Throws</b>: If value_traits::node_traits::node
 
88
   //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks)
 
89
   //!   or the copy constructor of the value_compare object throws. 
 
90
   sg_set_impl( const value_compare &cmp = value_compare()
 
91
           , const value_traits &v_traits = value_traits()) 
 
92
      :  tree_(cmp, v_traits)
 
93
   {}
 
94
 
 
95
   //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type. 
 
96
   //!   cmp must be a comparison function that induces a strict weak ordering.
 
97
   //! 
 
98
   //! <b>Effects</b>: Constructs an empty sg_set and inserts elements from 
 
99
   //!   [b, e).
 
100
   //! 
 
101
   //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using 
 
102
   //!   comp and otherwise N * log N, where N is std::distance(last, first).
 
103
   //! 
 
104
   //! <b>Throws</b>: If value_traits::node_traits::node
 
105
   //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks)
 
106
   //!   or the copy constructor/operator() of the value_compare object throws. 
 
107
   template<class Iterator>
 
108
   sg_set_impl( Iterator b, Iterator e
 
109
           , const value_compare &cmp = value_compare()
 
110
           , const value_traits &v_traits = value_traits())
 
111
      : tree_(true, b, e, cmp, v_traits)
 
112
   {}
 
113
 
 
114
   //! <b>Effects</b>: Detaches all elements from this. The objects in the sg_set 
 
115
   //!   are not deleted (i.e. no destructors are called).
 
116
   //! 
 
117
   //! <b>Complexity</b>: Linear to the number of elements on the container.
 
118
   //!   if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
 
119
   //! 
 
120
   //! <b>Throws</b>: Nothing.
 
121
   ~sg_set_impl() 
 
122
   {}
 
123
 
 
124
   //! <b>Effects</b>: Returns an iterator pointing to the beginning of the sg_set.
 
125
   //! 
 
126
   //! <b>Complexity</b>: Constant.
 
127
   //! 
 
128
   //! <b>Throws</b>: Nothing.
 
129
   iterator begin()
 
130
   { return tree_.begin();  }
 
131
 
 
132
   //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the sg_set.
 
133
   //! 
 
134
   //! <b>Complexity</b>: Constant.
 
135
   //! 
 
136
   //! <b>Throws</b>: Nothing.
 
137
   const_iterator begin() const
 
138
   { return tree_.begin();  }
 
139
 
 
140
   //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the sg_set.
 
141
   //! 
 
142
   //! <b>Complexity</b>: Constant.
 
143
   //! 
 
144
   //! <b>Throws</b>: Nothing.
 
145
   const_iterator cbegin() const
 
146
   { return tree_.cbegin();  }
 
147
 
 
148
   //! <b>Effects</b>: Returns an iterator pointing to the end of the sg_set.
 
149
   //! 
 
150
   //! <b>Complexity</b>: Constant.
 
151
   //! 
 
152
   //! <b>Throws</b>: Nothing.
 
153
   iterator end()
 
154
   { return tree_.end();  }
 
155
 
 
156
   //! <b>Effects</b>: Returns a const_iterator pointing to the end of the sg_set.
 
157
   //! 
 
158
   //! <b>Complexity</b>: Constant.
 
159
   //! 
 
160
   //! <b>Throws</b>: Nothing.
 
161
   const_iterator end() const
 
162
   { return tree_.end();  }
 
163
 
 
164
   //! <b>Effects</b>: Returns a const_iterator pointing to the end of the sg_set.
 
165
   //! 
 
166
   //! <b>Complexity</b>: Constant.
 
167
   //! 
 
168
   //! <b>Throws</b>: Nothing.
 
169
   const_iterator cend() const
 
170
   { return tree_.cend();  }
 
171
 
 
172
   //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning of the
 
173
   //!    reversed sg_set.
 
174
   //! 
 
175
   //! <b>Complexity</b>: Constant.
 
176
   //! 
 
177
   //! <b>Throws</b>: Nothing.
 
178
   reverse_iterator rbegin()
 
179
   { return tree_.rbegin();  }
 
180
 
 
181
   //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
 
182
   //!    of the reversed sg_set.
 
183
   //! 
 
184
   //! <b>Complexity</b>: Constant.
 
185
   //! 
 
186
   //! <b>Throws</b>: Nothing.
 
187
   const_reverse_iterator rbegin() const
 
188
   { return tree_.rbegin();  }
 
189
 
 
190
   //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
 
191
   //!    of the reversed sg_set.
 
192
   //! 
 
193
   //! <b>Complexity</b>: Constant.
 
194
   //! 
 
195
   //! <b>Throws</b>: Nothing.
 
196
   const_reverse_iterator crbegin() const
 
197
   { return tree_.crbegin();  }
 
198
 
 
199
   //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
 
200
   //!    of the reversed sg_set.
 
201
   //! 
 
202
   //! <b>Complexity</b>: Constant.
 
203
   //! 
 
204
   //! <b>Throws</b>: Nothing.
 
205
   reverse_iterator rend()
 
206
   { return tree_.rend();  }
 
207
 
 
208
   //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
 
209
   //!    of the reversed sg_set.
 
210
   //! 
 
211
   //! <b>Complexity</b>: Constant.
 
212
   //! 
 
213
   //! <b>Throws</b>: Nothing.
 
214
   const_reverse_iterator rend() const
 
215
   { return tree_.rend();  }
 
216
 
 
217
   //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
 
218
   //!    of the reversed sg_set.
 
219
   //! 
 
220
   //! <b>Complexity</b>: Constant.
 
221
   //! 
 
222
   //! <b>Throws</b>: Nothing.
 
223
   const_reverse_iterator crend() const
 
224
   { return tree_.crend();  }
 
225
 
 
226
   //! <b>Precondition</b>: end_iterator must be a valid end iterator
 
227
   //!   of sg_set.
 
228
   //! 
 
229
   //! <b>Effects</b>: Returns a const reference to the sg_set associated to the end iterator
 
230
   //! 
 
231
   //! <b>Throws</b>: Nothing.
 
232
   //! 
 
233
   //! <b>Complexity</b>: Constant.
 
234
   static sg_set_impl &container_from_end_iterator(iterator end_iterator)
 
235
   {
 
236
      return *detail::parent_from_member<sg_set_impl, tree_type>
 
237
         ( &tree_type::container_from_end_iterator(end_iterator)
 
238
         , &sg_set_impl::tree_);
 
239
   }
 
240
 
 
241
   //! <b>Precondition</b>: end_iterator must be a valid end const_iterator
 
242
   //!   of sg_set.
 
243
   //! 
 
244
   //! <b>Effects</b>: Returns a const reference to the sg_set associated to the end iterator
 
245
   //! 
 
246
   //! <b>Throws</b>: Nothing.
 
247
   //! 
 
248
   //! <b>Complexity</b>: Constant.
 
249
   static const sg_set_impl &container_from_end_iterator(const_iterator end_iterator)
 
250
   {
 
251
      return *detail::parent_from_member<sg_set_impl, tree_type>
 
252
         ( &tree_type::container_from_end_iterator(end_iterator)
 
253
         , &sg_set_impl::tree_);
 
254
   }
 
255
 
 
256
   //! <b>Precondition</b>: it must be a valid iterator of set.
 
257
   //! 
 
258
   //! <b>Effects</b>: Returns a reference to the set associated to the iterator
 
259
   //! 
 
260
   //! <b>Throws</b>: Nothing.
 
261
   //! 
 
262
   //! <b>Complexity</b>: Logarithmic.
 
263
   static sg_set_impl &container_from_iterator(iterator it)
 
264
   {
 
265
      return *detail::parent_from_member<sg_set_impl, tree_type>
 
266
         ( &tree_type::container_from_iterator(it)
 
267
         , &sg_set_impl::tree_);
 
268
   }
 
269
 
 
270
   //! <b>Precondition</b>: it must be a valid const_iterator of set.
 
271
   //! 
 
272
   //! <b>Effects</b>: Returns a const reference to the set associated to the iterator
 
273
   //! 
 
274
   //! <b>Throws</b>: Nothing.
 
275
   //! 
 
276
   //! <b>Complexity</b>: Logarithmic.
 
277
   static const sg_set_impl &container_from_iterator(const_iterator it)
 
278
   {
 
279
      return *detail::parent_from_member<sg_set_impl, tree_type>
 
280
         ( &tree_type::container_from_iterator(it)
 
281
         , &sg_set_impl::tree_);
 
282
   }
 
283
 
 
284
   //! <b>Effects</b>: Returns the key_compare object used by the sg_set.
 
285
   //! 
 
286
   //! <b>Complexity</b>: Constant.
 
287
   //! 
 
288
   //! <b>Throws</b>: If key_compare copy-constructor throws.
 
289
   key_compare key_comp() const
 
290
   { return tree_.value_comp(); }
 
291
 
 
292
   //! <b>Effects</b>: Returns the value_compare object used by the sg_set.
 
293
   //! 
 
294
   //! <b>Complexity</b>: Constant.
 
295
   //! 
 
296
   //! <b>Throws</b>: If value_compare copy-constructor throws.
 
297
   value_compare value_comp() const
 
298
   { return tree_.value_comp(); }
 
299
 
 
300
   //! <b>Effects</b>: Returns true if the container is empty.
 
301
   //! 
 
302
   //! <b>Complexity</b>: Constant.
 
303
   //! 
 
304
   //! <b>Throws</b>: Nothing.
 
305
   bool empty() const
 
306
   { return tree_.empty(); }
 
307
 
 
308
   //! <b>Effects</b>: Returns the number of elements stored in the sg_set.
 
309
   //! 
 
310
   //! <b>Complexity</b>: Linear to elements contained in *this if,
 
311
   //!   constant-time size option is enabled. Constant-time otherwise.
 
312
   //! 
 
313
   //! <b>Throws</b>: Nothing.
 
314
   size_type size() const
 
315
   { return tree_.size(); }
 
316
 
 
317
   //! <b>Effects</b>: Swaps the contents of two sets.
 
318
   //! 
 
319
   //! <b>Complexity</b>: Constant.
 
320
   //! 
 
321
   //! <b>Throws</b>: If the swap() call for the comparison functor
 
322
   //!   found using ADL throws. Strong guarantee.
 
323
   void swap(sg_set_impl& other)
 
324
   { tree_.swap(other.tree_); }
 
325
 
 
326
   //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
 
327
   //!   Cloner should yield to nodes equivalent to the original nodes.
 
328
   //!
 
329
   //! <b>Effects</b>: Erases all the elements from *this
 
330
   //!   calling Disposer::operator()(pointer), clones all the 
 
331
   //!   elements from src calling Cloner::operator()(const_reference )
 
332
   //!   and inserts them on *this. Copies the predicate from the source container.
 
333
   //!
 
334
   //!   If cloner throws, all cloned elements are unlinked and disposed
 
335
   //!   calling Disposer::operator()(pointer).
 
336
   //!   
 
337
   //! <b>Complexity</b>: Linear to erased plus inserted elements.
 
338
   //! 
 
339
   //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee.
 
340
   template <class Cloner, class Disposer>
 
341
   void clone_from(const sg_set_impl &src, Cloner cloner, Disposer disposer)
 
342
   {  tree_.clone_from(src.tree_, cloner, disposer);  }
 
343
 
 
344
   //! <b>Requires</b>: value must be an lvalue
 
345
   //! 
 
346
   //! <b>Effects</b>: Tries to inserts value into the sg_set.
 
347
   //!
 
348
   //! <b>Returns</b>: If the value
 
349
   //!   is not already present inserts it and returns a pair containing the
 
350
   //!   iterator to the new value and true. If there is an equivalent value
 
351
   //!   returns a pair containing an iterator to the already present value
 
352
   //!   and false.
 
353
   //! 
 
354
   //! <b>Complexity</b>: Average complexity for insert element is at
 
355
   //!   most logarithmic.
 
356
   //! 
 
357
   //! <b>Throws</b>: If the internal value_compare ordering function throws. Strong guarantee.
 
358
   //! 
 
359
   //! <b>Note</b>: Does not affect the validity of iterators and references.
 
360
   //!   No copy-constructors are called.
 
361
   std::pair<iterator, bool> insert(reference value)
 
362
   {  return tree_.insert_unique(value);  }
 
363
 
 
364
   //! <b>Requires</b>: value must be an lvalue
 
365
   //! 
 
366
   //! <b>Effects</b>: Tries to to insert x into the sg_set, using "hint" 
 
367
   //!   as a hint to where it will be inserted.
 
368
   //!
 
369
   //! <b>Returns</b>: An iterator that points to the position where the 
 
370
   //!   new element was inserted into the sg_set.
 
371
   //! 
 
372
   //! <b>Complexity</b>: Logarithmic in general, but it's amortized
 
373
   //!   constant time if t is inserted immediately before hint.
 
374
   //! 
 
375
   //! <b>Throws</b>: If the internal value_compare ordering function throws. Strong guarantee.
 
376
   //! 
 
377
   //! <b>Note</b>: Does not affect the validity of iterators and references.
 
378
   //!   No copy-constructors are called.
 
379
   iterator insert(const_iterator hint, reference value)
 
380
   {  return tree_.insert_unique(hint, value);  }
 
381
 
 
382
   //! <b>Requires</b>: key_value_comp must be a comparison function that induces 
 
383
   //!   the same strict weak ordering as value_compare. The difference is that
 
384
   //!   key_value_comp compares an arbitrary key with the contained values.
 
385
   //! 
 
386
   //! <b>Effects</b>: Checks if a value can be inserted in the sg_set, using
 
387
   //!   a user provided key instead of the value itself.
 
388
   //!
 
389
   //! <b>Returns</b>: If there is an equivalent value
 
390
   //!   returns a pair containing an iterator to the already present value
 
391
   //!   and false. If the value can be inserted returns true in the returned
 
392
   //!   pair boolean and fills "commit_data" that is meant to be used with
 
393
   //!   the "insert_commit" function.
 
394
   //! 
 
395
   //! <b>Complexity</b>: Average complexity is at most logarithmic.
 
396
   //!
 
397
   //! <b>Throws</b>: If the key_value_comp ordering function throws. Strong guarantee.
 
398
   //! 
 
399
   //! <b>Notes</b>: This function is used to improve performance when constructing
 
400
   //!   a value_type is expensive: if there is an equivalent value
 
401
   //!   the constructed object must be discarded. Many times, the part of the
 
402
   //!   node that is used to impose the order is much cheaper to construct
 
403
   //!   than the value_type and this function offers the possibility to use that 
 
404
   //!   part to check if the insertion will be successful.
 
405
   //!
 
406
   //!   If the check is successful, the user can construct the value_type and use
 
407
   //!   "insert_commit" to insert the object in constant-time. This gives a total
 
408
   //!   logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
 
409
   //!
 
410
   //!   "commit_data" remains valid for a subsequent "insert_commit" only if no more
 
411
   //!   objects are inserted or erased from the sg_set.
 
412
   template<class KeyType, class KeyValueCompare>
 
413
   std::pair<iterator, bool> insert_check
 
414
      (const KeyType &key, KeyValueCompare key_value_comp, insert_commit_data &commit_data)
 
415
   {  return tree_.insert_unique_check(key, key_value_comp, commit_data); }
 
416
 
 
417
   //! <b>Requires</b>: key_value_comp must be a comparison function that induces 
 
418
   //!   the same strict weak ordering as value_compare. The difference is that
 
419
   //!   key_value_comp compares an arbitrary key with the contained values.
 
420
   //! 
 
421
   //! <b>Effects</b>: Checks if a value can be inserted in the sg_set, using
 
422
   //!   a user provided key instead of the value itself, using "hint" 
 
423
   //!   as a hint to where it will be inserted.
 
424
   //!
 
425
   //! <b>Returns</b>: If there is an equivalent value
 
426
   //!   returns a pair containing an iterator to the already present value
 
427
   //!   and false. If the value can be inserted returns true in the returned
 
428
   //!   pair boolean and fills "commit_data" that is meant to be used with
 
429
   //!   the "insert_commit" function.
 
430
   //! 
 
431
   //! <b>Complexity</b>: Logarithmic in general, but it's amortized
 
432
   //!   constant time if t is inserted immediately before hint.
 
433
   //!
 
434
   //! <b>Throws</b>: If the key_value_comp ordering function throws. Strong guarantee.
 
435
   //! 
 
436
   //! <b>Notes</b>: This function is used to improve performance when constructing
 
437
   //!   a value_type is expensive: if there is an equivalent value
 
438
   //!   the constructed object must be discarded. Many times, the part of the
 
439
   //!   constructing that is used to impose the order is much cheaper to construct
 
440
   //!   than the value_type and this function offers the possibility to use that key 
 
441
   //!   to check if the insertion will be successful.
 
442
   //!
 
443
   //!   If the check is successful, the user can construct the value_type and use
 
444
   //!   "insert_commit" to insert the object in constant-time. This can give a total
 
445
   //!   constant-time complexity to the insertion: check(O(1)) + commit(O(1)).
 
446
   //!   
 
447
   //!   "commit_data" remains valid for a subsequent "insert_commit" only if no more
 
448
   //!   objects are inserted or erased from the sg_set.
 
449
   template<class KeyType, class KeyValueCompare>
 
450
   std::pair<iterator, bool> insert_check
 
451
      (const_iterator hint, const KeyType &key
 
452
      ,KeyValueCompare key_value_comp, insert_commit_data &commit_data)
 
453
   {  return tree_.insert_unique_check(hint, key, key_value_comp, commit_data); }
 
454
 
 
455
   //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data
 
456
   //!   must have been obtained from a previous call to "insert_check".
 
457
   //!   No objects should have been inserted or erased from the sg_set between
 
458
   //!   the "insert_check" that filled "commit_data" and the call to "insert_commit".
 
459
   //! 
 
460
   //! <b>Effects</b>: Inserts the value in the sg_set using the information obtained
 
461
   //!   from the "commit_data" that a previous "insert_check" filled.
 
462
   //!
 
463
   //! <b>Returns</b>: An iterator to the newly inserted object.
 
464
   //! 
 
465
   //! <b>Complexity</b>: Constant time.
 
466
   //!
 
467
   //! <b>Throws</b>: Nothing.
 
468
   //! 
 
469
   //! <b>Notes</b>: This function has only sense if a "insert_check" has been
 
470
   //!   previously executed to fill "commit_data". No value should be inserted or
 
471
   //!   erased between the "insert_check" and "insert_commit" calls.
 
472
   iterator insert_commit(reference value, const insert_commit_data &commit_data)
 
473
   {  return tree_.insert_unique_commit(value, commit_data); }
 
474
 
 
475
   //! <b>Requires</b>: Dereferencing iterator must yield an lvalue 
 
476
   //!   of type value_type.
 
477
   //! 
 
478
   //! <b>Effects</b>: Inserts a range into the sg_set.
 
479
   //! 
 
480
   //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the
 
481
   //!   size of the range. However, it is linear in N if the range is already sorted
 
482
   //!   by value_comp().
 
483
   //! 
 
484
   //! <b>Throws</b>: If the internal value_compare ordering function throws. Basic guarantee.
 
485
   //! 
 
486
   //! <b>Note</b>: Does not affect the validity of iterators and references.
 
487
   //!   No copy-constructors are called.
 
488
   template<class Iterator>
 
489
   void insert(Iterator b, Iterator e)
 
490
   {  tree_.insert_unique(b, e);  }
 
491
 
 
492
   //! <b>Requires</b>: value must be an lvalue, "pos" must be
 
493
   //!   a valid iterator (or end) and must be the succesor of value
 
494
   //!   once inserted according to the predicate. "value" must not be equal to any
 
495
   //!   inserted key according to the predicate.
 
496
   //!
 
497
   //! <b>Effects</b>: Inserts x into the tree before "pos".
 
498
   //! 
 
499
   //! <b>Complexity</b>: Constant time.
 
500
   //! 
 
501
   //! <b>Throws</b>: Nothing.
 
502
   //! 
 
503
   //! <b>Note</b>: This function does not check preconditions so if "pos" is not
 
504
   //! the successor of "value" or "value" is not unique tree ordering and uniqueness
 
505
   //! invariants will be broken respectively.
 
506
   //! This is a low-level function to be used only for performance reasons
 
507
   //! by advanced users.
 
508
   iterator insert_before(const_iterator pos, reference value)
 
509
   {  return tree_.insert_before(pos, value);  }
 
510
 
 
511
   //! <b>Requires</b>: value must be an lvalue, and it must be greater than
 
512
   //!   any inserted key according to the predicate.
 
513
   //!
 
514
   //! <b>Effects</b>: Inserts x into the tree in the last position.
 
515
   //! 
 
516
   //! <b>Complexity</b>: Constant time.
 
517
   //! 
 
518
   //! <b>Throws</b>: Nothing.
 
519
   //! 
 
520
   //! <b>Note</b>: This function does not check preconditions so if value is
 
521
   //!   less than or equal to the greatest inserted key tree ordering invariant will be broken.
 
522
   //!   This function is slightly more efficient than using "insert_before".
 
523
   //!   This is a low-level function to be used only for performance reasons
 
524
   //!   by advanced users.
 
525
   void push_back(reference value)
 
526
   {  tree_.push_back(value);  }
 
527
 
 
528
   //! <b>Requires</b>: value must be an lvalue, and it must be less
 
529
   //!   than any inserted key according to the predicate.
 
530
   //!
 
531
   //! <b>Effects</b>: Inserts x into the tree in the first position.
 
532
   //! 
 
533
   //! <b>Complexity</b>: Constant time.
 
534
   //! 
 
535
   //! <b>Throws</b>: Nothing.
 
536
   //! 
 
537
   //! <b>Note</b>: This function does not check preconditions so if value is
 
538
   //!   greater than or equal to the the mimum inserted key tree ordering or uniqueness
 
539
   //!   invariants will be broken.
 
540
   //!   This function is slightly more efficient than using "insert_before".
 
541
   //!   This is a low-level function to be used only for performance reasons
 
542
   //!   by advanced users.
 
543
   void push_front(reference value)
 
544
   {  tree_.push_front(value);  }
 
545
 
 
546
   //! <b>Effects</b>: Erases the element pointed to by pos. 
 
547
   //! 
 
548
   //! <b>Complexity</b>: Average complexity is constant time.
 
549
   //! 
 
550
   //! <b>Returns</b>: An iterator to the element after the erased element.
 
551
   //!
 
552
   //! <b>Throws</b>: Nothing.
 
553
   //! 
 
554
   //! <b>Note</b>: Invalidates the iterators (but not the references)
 
555
   //!    to the erased elements. No destructors are called.
 
556
   iterator erase(const_iterator i)
 
557
   {  return tree_.erase(i);  }
 
558
 
 
559
   //! <b>Effects</b>: Erases the range pointed to by b end e. 
 
560
   //! 
 
561
   //! <b>Complexity</b>: Average complexity for erase range is at most 
 
562
   //!   O(log(size() + N)), where N is the number of elements in the range.
 
563
   //! 
 
564
   //! <b>Returns</b>: An iterator to the element after the erased elements.
 
565
   //! 
 
566
   //! <b>Throws</b>: Nothing.
 
567
   //! 
 
568
   //! <b>Note</b>: Invalidates the iterators (but not the references)
 
569
   //!    to the erased elements. No destructors are called.
 
570
   iterator erase(const_iterator b, const_iterator e)
 
571
   {  return tree_.erase(b, e);  }
 
572
 
 
573
   //! <b>Effects</b>: Erases all the elements with the given value.
 
574
   //! 
 
575
   //! <b>Returns</b>: The number of erased elements.
 
576
   //! 
 
577
   //! <b>Complexity</b>: O(log(size()) + this->count(value)).
 
578
   //! 
 
579
   //! <b>Throws</b>: If the internal value_compare ordering function throws. Basic guarantee.
 
580
   //! 
 
581
   //! <b>Note</b>: Invalidates the iterators (but not the references)
 
582
   //!    to the erased elements. No destructors are called.
 
583
   size_type erase(const_reference value)
 
584
   {  return tree_.erase(value);  }
 
585
 
 
586
   //! <b>Effects</b>: Erases all the elements that compare equal with
 
587
   //!   the given key and the given comparison functor.
 
588
   //! 
 
589
   //! <b>Returns</b>: The number of erased elements.
 
590
   //! 
 
591
   //! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
 
592
   //! 
 
593
   //! <b>Throws</b>: If the comp ordering function throws. Basic guarantee.
 
594
   //! 
 
595
   //! <b>Note</b>: Invalidates the iterators (but not the references)
 
596
   //!    to the erased elements. No destructors are called.
 
597
   template<class KeyType, class KeyValueCompare>
 
598
   size_type erase(const KeyType& key, KeyValueCompare comp
 
599
                  /// @cond
 
600
                  , typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
 
601
                  /// @endcond
 
602
                  )
 
603
   {  return tree_.erase(key, comp);  }
 
604
 
 
605
   //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
 
606
   //!
 
607
   //! <b>Effects</b>: Erases the element pointed to by pos. 
 
608
   //!   Disposer::operator()(pointer) is called for the removed element.
 
609
   //! 
 
610
   //! <b>Complexity</b>: Average complexity for erase element is constant time. 
 
611
   //! 
 
612
   //! <b>Returns</b>: An iterator to the element after the erased element.
 
613
   //! 
 
614
   //! <b>Throws</b>: Nothing.
 
615
   //! 
 
616
   //! <b>Note</b>: Invalidates the iterators 
 
617
   //!    to the erased elements.
 
618
   template<class Disposer>
 
619
   iterator erase_and_dispose(const_iterator i, Disposer disposer)
 
620
   {  return tree_.erase_and_dispose(i, disposer);  }
 
621
 
 
622
   #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
623
   template<class Disposer>
 
624
   iterator erase_and_dispose(iterator i, Disposer disposer)
 
625
   {  return this->erase_and_dispose(const_iterator(i), disposer);   }
 
626
   #endif
 
627
 
 
628
   //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
 
629
   //!
 
630
   //! <b>Effects</b>: Erases the range pointed to by b end e.
 
631
   //!   Disposer::operator()(pointer) is called for the removed elements.
 
632
   //! 
 
633
   //! <b>Complexity</b>: Average complexity for erase range is at most 
 
634
   //!   O(log(size() + N)), where N is the number of elements in the range.
 
635
   //! 
 
636
   //! <b>Returns</b>: An iterator to the element after the erased elements.
 
637
   //! 
 
638
   //! <b>Throws</b>: Nothing.
 
639
   //! 
 
640
   //! <b>Note</b>: Invalidates the iterators
 
641
   //!    to the erased elements.
 
642
   template<class Disposer>
 
643
   iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
 
644
   {  return tree_.erase_and_dispose(b, e, disposer);  }
 
645
 
 
646
   //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
 
647
   //!
 
648
   //! <b>Effects</b>: Erases all the elements with the given value.
 
649
   //!   Disposer::operator()(pointer) is called for the removed elements.
 
650
   //! 
 
651
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
652
   //! 
 
653
   //! <b>Complexity</b>: O(log(size() + this->count(value)). Basic guarantee.
 
654
   //! 
 
655
   //! <b>Throws</b>: Nothing.
 
656
   //! 
 
657
   //! <b>Note</b>: Invalidates the iterators (but not the references)
 
658
   //!    to the erased elements. No destructors are called.
 
659
   template<class Disposer>
 
660
   size_type erase_and_dispose(const_reference value, Disposer disposer)
 
661
   {  return tree_.erase_and_dispose(value, disposer);  }
 
662
 
 
663
   //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
 
664
   //!
 
665
   //! <b>Effects</b>: Erases all the elements with the given key.
 
666
   //!   according to the comparison functor "comp".
 
667
   //!   Disposer::operator()(pointer) is called for the removed elements.
 
668
   //!
 
669
   //! <b>Returns</b>: The number of erased elements.
 
670
   //! 
 
671
   //! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
 
672
   //! 
 
673
   //! <b>Throws</b>: If comp ordering function throws. Basic guarantee.
 
674
   //! 
 
675
   //! <b>Note</b>: Invalidates the iterators
 
676
   //!    to the erased elements.
 
677
   template<class KeyType, class KeyValueCompare, class Disposer>
 
678
   size_type erase_and_dispose(const KeyType& key, KeyValueCompare comp, Disposer disposer
 
679
                  /// @cond
 
680
                  , typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
 
681
                  /// @endcond
 
682
                  )
 
683
   {  return tree_.erase_and_dispose(key, comp, disposer);  }
 
684
 
 
685
   //! <b>Effects</b>: Erases all the elements of the container.
 
686
   //! 
 
687
   //! <b>Complexity</b>: Linear to the number of elements on the container.
 
688
   //!   if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
 
689
   //! 
 
690
   //! <b>Throws</b>: Nothing.
 
691
   //! 
 
692
   //! <b>Note</b>: Invalidates the iterators (but not the references)
 
693
   //!    to the erased elements. No destructors are called.
 
694
   void clear()
 
695
   {  return tree_.clear();  }
 
696
 
 
697
   //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
 
698
   //! 
 
699
   //! <b>Effects</b>: Erases all the elements of the container.
 
700
   //! 
 
701
   //! <b>Complexity</b>: Linear to the number of elements on the container.
 
702
   //!   Disposer::operator()(pointer) is called for the removed elements.
 
703
   //! 
 
704
   //! <b>Throws</b>: Nothing.
 
705
   //! 
 
706
   //! <b>Note</b>: Invalidates the iterators (but not the references)
 
707
   //!    to the erased elements. No destructors are called.
 
708
   template<class Disposer>
 
709
   void clear_and_dispose(Disposer disposer)
 
710
   {  return tree_.clear_and_dispose(disposer);  }
 
711
 
 
712
   //! <b>Effects</b>: Returns the number of contained elements with the given key
 
713
   //! 
 
714
   //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
 
715
   //!   to number of objects with the given key.
 
716
   //! 
 
717
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
718
   size_type count(const_reference value) const
 
719
   {  return tree_.find(value) != end();  }
 
720
 
 
721
   //! <b>Effects</b>: Returns the number of contained elements with the same key
 
722
   //!   compared with the given comparison functor.
 
723
   //! 
 
724
   //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
 
725
   //!   to number of objects with the given key.
 
726
   //! 
 
727
   //! <b>Throws</b>: If comp ordering function throws.
 
728
   template<class KeyType, class KeyValueCompare>
 
729
   size_type count(const KeyType& key, KeyValueCompare comp) const
 
730
   {  return tree_.find(key, comp) != end();  }
 
731
 
 
732
   //! <b>Effects</b>: Returns an iterator to the first element whose
 
733
   //!   key is not less than k or end() if that element does not exist.
 
734
   //! 
 
735
   //! <b>Complexity</b>: Logarithmic.
 
736
   //! 
 
737
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
738
   iterator lower_bound(const_reference value)
 
739
   {  return tree_.lower_bound(value);  }
 
740
 
 
741
   //! <b>Requires</b>: comp must imply the same element order as
 
742
   //!   value_compare. Usually key is the part of the value_type
 
743
   //!   that is used in the ordering functor.
 
744
   //!
 
745
   //! <b>Effects</b>: Returns an iterator to the first element whose
 
746
   //!   key according to the comparison functor is not less than k or 
 
747
   //!   end() if that element does not exist.
 
748
   //! 
 
749
   //! <b>Complexity</b>: Logarithmic.
 
750
   //! 
 
751
   //! <b>Throws</b>: If comp ordering function throws.
 
752
   //! 
 
753
   //! <b>Note</b>: This function is used when constructing a value_type
 
754
   //!   is expensive and the value_type can be compared with a cheaper
 
755
   //!   key type. Usually this key is part of the value_type.
 
756
   template<class KeyType, class KeyValueCompare>
 
757
   iterator lower_bound(const KeyType& key, KeyValueCompare comp)
 
758
   {  return tree_.lower_bound(key, comp);  }
 
759
 
 
760
   //! <b>Effects</b>: Returns a const iterator to the first element whose
 
761
   //!   key is not less than k or end() if that element does not exist.
 
762
   //! 
 
763
   //! <b>Complexity</b>: Logarithmic.
 
764
   //! 
 
765
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
766
   const_iterator lower_bound(const_reference value) const
 
767
   {  return tree_.lower_bound(value);  }
 
768
 
 
769
   //! <b>Requires</b>: comp must imply the same element order as
 
770
   //!   value_compare. Usually key is the part of the value_type
 
771
   //!   that is used in the ordering functor.
 
772
   //!
 
773
   //! <b>Effects</b>: Returns a const_iterator to the first element whose
 
774
   //!   key according to the comparison functor is not less than k or 
 
775
   //!   end() if that element does not exist.
 
776
   //! 
 
777
   //! <b>Complexity</b>: Logarithmic.
 
778
   //! 
 
779
   //! <b>Throws</b>: If comp ordering function throws.
 
780
   //! 
 
781
   //! <b>Note</b>: This function is used when constructing a value_type
 
782
   //!   is expensive and the value_type can be compared with a cheaper
 
783
   //!   key type. Usually this key is part of the value_type.
 
784
   template<class KeyType, class KeyValueCompare>
 
785
   const_iterator lower_bound(const KeyType& key, KeyValueCompare comp) const
 
786
   {  return tree_.lower_bound(key, comp);  }
 
787
 
 
788
   //! <b>Effects</b>: Returns an iterator to the first element whose
 
789
   //!   key is greater than k or end() if that element does not exist.
 
790
   //! 
 
791
   //! <b>Complexity</b>: Logarithmic.
 
792
   //! 
 
793
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
794
   iterator upper_bound(const_reference value)
 
795
   {  return tree_.upper_bound(value);  }
 
796
 
 
797
   //! <b>Requires</b>: comp must imply the same element order as
 
798
   //!   value_compare. Usually key is the part of the value_type
 
799
   //!   that is used in the ordering functor.
 
800
   //!
 
801
   //! <b>Effects</b>: Returns an iterator to the first element whose
 
802
   //!   key according to the comparison functor is greater than key or 
 
803
   //!   end() if that element does not exist.
 
804
   //! 
 
805
   //! <b>Complexity</b>: Logarithmic.
 
806
   //! 
 
807
   //! <b>Throws</b>: If comp ordering function throws.
 
808
   //!
 
809
   //! <b>Note</b>: This function is used when constructing a value_type
 
810
   //!   is expensive and the value_type can be compared with a cheaper
 
811
   //!   key type. Usually this key is part of the value_type.
 
812
   template<class KeyType, class KeyValueCompare>
 
813
   iterator upper_bound(const KeyType& key, KeyValueCompare comp)
 
814
   {  return tree_.upper_bound(key, comp);  }
 
815
 
 
816
   //! <b>Effects</b>: Returns an iterator to the first element whose
 
817
   //!   key is greater than k or end() if that element does not exist.
 
818
   //! 
 
819
   //! <b>Complexity</b>: Logarithmic.
 
820
   //! 
 
821
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
822
   const_iterator upper_bound(const_reference value) const
 
823
   {  return tree_.upper_bound(value);  }
 
824
 
 
825
   //! <b>Requires</b>: comp must imply the same element order as
 
826
   //!   value_compare. Usually key is the part of the value_type
 
827
   //!   that is used in the ordering functor.
 
828
   //!
 
829
   //! <b>Effects</b>: Returns a const_iterator to the first element whose
 
830
   //!   key according to the comparison functor is greater than key or 
 
831
   //!   end() if that element does not exist.
 
832
   //! 
 
833
   //! <b>Complexity</b>: Logarithmic.
 
834
   //! 
 
835
   //! <b>Throws</b>: If comp ordering function throws.
 
836
   //!
 
837
   //! <b>Note</b>: This function is used when constructing a value_type
 
838
   //!   is expensive and the value_type can be compared with a cheaper
 
839
   //!   key type. Usually this key is part of the value_type.
 
840
   template<class KeyType, class KeyValueCompare>
 
841
   const_iterator upper_bound(const KeyType& key, KeyValueCompare comp) const
 
842
   {  return tree_.upper_bound(key, comp);  }
 
843
 
 
844
   //! <b>Effects</b>: Finds an iterator to the first element whose value is 
 
845
   //!   "value" or end() if that element does not exist.
 
846
   //!
 
847
   //! <b>Complexity</b>: Logarithmic.
 
848
   //! 
 
849
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
850
   iterator find(const_reference value)
 
851
   {  return tree_.find(value);  }
 
852
 
 
853
   //! <b>Requires</b>: comp must imply the same element order as
 
854
   //!   value_compare. Usually key is the part of the value_type
 
855
   //!   that is used in the ordering functor.
 
856
   //!
 
857
   //! <b>Effects</b>: Finds an iterator to the first element whose key is 
 
858
   //!   "key" according to the comparison functor or end() if that element 
 
859
   //!   does not exist.
 
860
   //!
 
861
   //! <b>Complexity</b>: Logarithmic.
 
862
   //! 
 
863
   //! <b>Throws</b>: If comp ordering function throws.
 
864
   //!
 
865
   //! <b>Note</b>: This function is used when constructing a value_type
 
866
   //!   is expensive and the value_type can be compared with a cheaper
 
867
   //!   key type. Usually this key is part of the value_type.
 
868
   template<class KeyType, class KeyValueCompare>
 
869
   iterator find(const KeyType& key, KeyValueCompare comp)
 
870
   {  return tree_.find(key, comp);  }
 
871
 
 
872
   //! <b>Effects</b>: Finds a const_iterator to the first element whose value is 
 
873
   //!   "value" or end() if that element does not exist.
 
874
   //! 
 
875
   //! <b>Complexity</b>: Logarithmic.
 
876
   //! 
 
877
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
878
   const_iterator find(const_reference value) const
 
879
   {  return tree_.find(value);  }
 
880
 
 
881
   //! <b>Requires</b>: comp must imply the same element order as
 
882
   //!   value_compare. Usually key is the part of the value_type
 
883
   //!   that is used in the ordering functor.
 
884
   //!
 
885
   //! <b>Effects</b>: Finds a const_iterator to the first element whose key is 
 
886
   //!   "key" according to the comparison functor or end() if that element 
 
887
   //!   does not exist.
 
888
   //! 
 
889
   //! <b>Complexity</b>: Logarithmic.
 
890
   //! 
 
891
   //! <b>Throws</b>: If comp ordering function throws.
 
892
   //!
 
893
   //! <b>Note</b>: This function is used when constructing a value_type
 
894
   //!   is expensive and the value_type can be compared with a cheaper
 
895
   //!   key type. Usually this key is part of the value_type.
 
896
   template<class KeyType, class KeyValueCompare>
 
897
   const_iterator find(const KeyType& key, KeyValueCompare comp) const
 
898
   {  return tree_.find(key, comp);  }
 
899
 
 
900
   //! <b>Effects</b>: Finds a range containing all elements whose key is k or
 
901
   //!   an empty range that indicates the position where those elements would be
 
902
   //!   if they there is no elements with key k.
 
903
   //! 
 
904
   //! <b>Complexity</b>: Logarithmic.
 
905
   //! 
 
906
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
907
   std::pair<iterator,iterator> equal_range(const_reference value)
 
908
   {  return tree_.equal_range(value);  }
 
909
 
 
910
   //! <b>Requires</b>: comp must imply the same element order as
 
911
   //!   value_compare. Usually key is the part of the value_type
 
912
   //!   that is used in the ordering functor.
 
913
   //!
 
914
   //! <b>Effects</b>: Finds a range containing all elements whose key is k 
 
915
   //!   according to the comparison functor or an empty range 
 
916
   //!   that indicates the position where those elements would be
 
917
   //!   if they there is no elements with key k.
 
918
   //! 
 
919
   //! <b>Complexity</b>: Logarithmic.
 
920
   //! 
 
921
   //! <b>Throws</b>: If comp ordering function throws.
 
922
   //!
 
923
   //! <b>Note</b>: This function is used when constructing a value_type
 
924
   //!   is expensive and the value_type can be compared with a cheaper
 
925
   //!   key type. Usually this key is part of the value_type.
 
926
   template<class KeyType, class KeyValueCompare>
 
927
   std::pair<iterator,iterator> equal_range(const KeyType& key, KeyValueCompare comp)
 
928
   {  return tree_.equal_range(key, comp);  }
 
929
 
 
930
   //! <b>Effects</b>: Finds a range containing all elements whose key is k or
 
931
   //!   an empty range that indicates the position where those elements would be
 
932
   //!   if they there is no elements with key k.
 
933
   //! 
 
934
   //! <b>Complexity</b>: Logarithmic.
 
935
   //! 
 
936
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
937
   std::pair<const_iterator, const_iterator>
 
938
      equal_range(const_reference value) const
 
939
   {  return tree_.equal_range(value);  }
 
940
 
 
941
   //! <b>Requires</b>: comp must imply the same element order as
 
942
   //!   value_compare. Usually key is the part of the value_type
 
943
   //!   that is used in the ordering functor.
 
944
   //!
 
945
   //! <b>Effects</b>: Finds a range containing all elements whose key is k 
 
946
   //!   according to the comparison functor or an empty range 
 
947
   //!   that indicates the position where those elements would be
 
948
   //!   if they there is no elements with key k.
 
949
   //! 
 
950
   //! <b>Complexity</b>: Logarithmic.
 
951
   //! 
 
952
   //! <b>Throws</b>: If comp ordering function throws.
 
953
   //!
 
954
   //! <b>Note</b>: This function is used when constructing a value_type
 
955
   //!   is expensive and the value_type can be compared with a cheaper
 
956
   //!   key type. Usually this key is part of the value_type.
 
957
   template<class KeyType, class KeyValueCompare>
 
958
   std::pair<const_iterator, const_iterator>
 
959
      equal_range(const KeyType& key, KeyValueCompare comp) const
 
960
   {  return tree_.equal_range(key, comp);  }
 
961
 
 
962
   //! <b>Requires</b>: value must be an lvalue and shall be in a sg_set of
 
963
   //!   appropriate type. Otherwise the behavior is undefined.
 
964
   //! 
 
965
   //! <b>Effects</b>: Returns: a valid iterator i belonging to the sg_set
 
966
   //!   that points to the value
 
967
   //! 
 
968
   //! <b>Complexity</b>: Constant.
 
969
   //! 
 
970
   //! <b>Throws</b>: Nothing.
 
971
   //! 
 
972
   //! <b>Note</b>: This static function is available only if the <i>value traits</i>
 
973
   //!   is stateless.
 
974
   static iterator s_iterator_to(reference value)
 
975
   {  return tree_type::s_iterator_to(value);  }
 
976
 
 
977
   //! <b>Requires</b>: value must be an lvalue and shall be in a sg_set of
 
978
   //!   appropriate type. Otherwise the behavior is undefined.
 
979
   //! 
 
980
   //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
 
981
   //!   sg_set that points to the value
 
982
   //! 
 
983
   //! <b>Complexity</b>: Constant.
 
984
   //! 
 
985
   //! <b>Throws</b>: Nothing.
 
986
   //! 
 
987
   //! <b>Note</b>: This static function is available only if the <i>value traits</i>
 
988
   //!   is stateless.
 
989
   static const_iterator s_iterator_to(const_reference value)
 
990
   {  return tree_type::s_iterator_to(value);  }
 
991
 
 
992
   //! <b>Requires</b>: value must be an lvalue and shall be in a sg_set of
 
993
   //!   appropriate type. Otherwise the behavior is undefined.
 
994
   //! 
 
995
   //! <b>Effects</b>: Returns: a valid iterator i belonging to the sg_set
 
996
   //!   that points to the value
 
997
   //! 
 
998
   //! <b>Complexity</b>: Constant.
 
999
   //! 
 
1000
   //! <b>Throws</b>: Nothing.
 
1001
   iterator iterator_to(reference value)
 
1002
   {  return tree_.iterator_to(value);  }
 
1003
 
 
1004
   //! <b>Requires</b>: value must be an lvalue and shall be in a sg_set of
 
1005
   //!   appropriate type. Otherwise the behavior is undefined.
 
1006
   //! 
 
1007
   //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
 
1008
   //!   sg_set that points to the value
 
1009
   //! 
 
1010
   //! <b>Complexity</b>: Constant.
 
1011
   //! 
 
1012
   //! <b>Throws</b>: Nothing.
 
1013
   const_iterator iterator_to(const_reference value) const
 
1014
   {  return tree_.iterator_to(value);  }
 
1015
 
 
1016
   //! <b>Requires</b>: value shall not be in a sg_set/sg_multiset.
 
1017
   //! 
 
1018
   //! <b>Effects</b>: init_node puts the hook of a value in a well-known default
 
1019
   //!   state.
 
1020
   //! 
 
1021
   //! <b>Throws</b>: Nothing.
 
1022
   //! 
 
1023
   //! <b>Complexity</b>: Constant time.
 
1024
   //! 
 
1025
   //! <b>Note</b>: This function puts the hook in the well-known default state
 
1026
   //!   used by auto_unlink and safe hooks.
 
1027
   static void init_node(reference value)
 
1028
   { tree_type::init_node(value);   }
 
1029
 
 
1030
   //! <b>Effects</b>: Unlinks the leftmost node from the tree.
 
1031
   //! 
 
1032
   //! <b>Complexity</b>: Average complexity is constant time.
 
1033
   //! 
 
1034
   //! <b>Throws</b>: Nothing.
 
1035
   //! 
 
1036
   //! <b>Notes</b>: This function breaks the tree and the tree can
 
1037
   //!   only be used for more unlink_leftmost_without_rebalance calls.
 
1038
   //!   This function is normally used to achieve a step by step
 
1039
   //!   controlled destruction of the tree.
 
1040
   pointer unlink_leftmost_without_rebalance()
 
1041
   {  return tree_.unlink_leftmost_without_rebalance();  }
 
1042
 
 
1043
   //! <b>Requires</b>: replace_this must be a valid iterator of *this
 
1044
   //!   and with_this must not be inserted in any tree.
 
1045
   //! 
 
1046
   //! <b>Effects</b>: Replaces replace_this in its position in the
 
1047
   //!   tree with with_this. The tree does not need to be rebalanced.
 
1048
   //! 
 
1049
   //! <b>Complexity</b>: Constant. 
 
1050
   //! 
 
1051
   //! <b>Throws</b>: Nothing.
 
1052
   //! 
 
1053
   //! <b>Note</b>: This function will break container ordering invariants if
 
1054
   //!   with_this is not equivalent to *replace_this according to the
 
1055
   //!   ordering rules. This function is faster than erasing and inserting
 
1056
   //!   the node, since no rebalancing or comparison is needed.
 
1057
   void replace_node(iterator replace_this, reference with_this)
 
1058
   {  tree_.replace_node(replace_this, with_this);   }
 
1059
 
 
1060
   //! <b>Effects</b>: Rebalances the tree.
 
1061
   //! 
 
1062
   //! <b>Throws</b>: Nothing.
 
1063
   //! 
 
1064
   //! <b>Complexity</b>: Linear.
 
1065
   void rebalance()
 
1066
   {  tree_.rebalance(); }
 
1067
 
 
1068
   //! <b>Requires</b>: old_root is a node of a tree.
 
1069
   //! 
 
1070
   //! <b>Effects</b>: Rebalances the subtree rooted at old_root.
 
1071
   //!
 
1072
   //! <b>Returns</b>: The new root of the subtree.
 
1073
   //!
 
1074
   //! <b>Throws</b>: Nothing.
 
1075
   //! 
 
1076
   //! <b>Complexity</b>: Linear to the elements in the subtree.
 
1077
   iterator rebalance_subtree(iterator root)
 
1078
   {  return tree_.rebalance_subtree(root); }
 
1079
 
 
1080
   //! <b>Returns</b>: The balance factor (alpha) used in this tree
 
1081
   //!
 
1082
   //! <b>Throws</b>: Nothing.
 
1083
   //! 
 
1084
   //! <b>Complexity</b>: Constant.
 
1085
   float balance_factor() const
 
1086
   {  return tree_.balance_factor(); }
 
1087
 
 
1088
   //! <b>Requires</b>: new_alpha must be a value between 0.5 and 1.0
 
1089
   //! 
 
1090
   //! <b>Effects</b>: Establishes a new balance factor (alpha) and rebalances
 
1091
   //!   the tree if the new balance factor is stricter (less) than the old factor.
 
1092
   //!
 
1093
   //! <b>Throws</b>: Nothing.
 
1094
   //! 
 
1095
   //! <b>Complexity</b>: Linear to the elements in the subtree.
 
1096
   void balance_factor(float new_alpha)
 
1097
   {  tree_.balance_factor(new_alpha); }
 
1098
 
 
1099
   /// @cond
 
1100
   friend bool operator==(const sg_set_impl &x, const sg_set_impl &y)
 
1101
   {  return x.tree_ == y.tree_;  }
 
1102
 
 
1103
   friend bool operator<(const sg_set_impl &x, const sg_set_impl &y)
 
1104
   {  return x.tree_ < y.tree_;  }
 
1105
   /// @endcond
 
1106
};
 
1107
 
 
1108
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
1109
template<class T, class ...Options>
 
1110
#else
 
1111
template<class Config>
 
1112
#endif
 
1113
inline bool operator!=
 
1114
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
1115
(const sg_set_impl<T, Options...> &x, const sg_set_impl<T, Options...> &y)
 
1116
#else
 
1117
(const sg_set_impl<Config> &x, const sg_set_impl<Config> &y)
 
1118
#endif
 
1119
{  return !(x == y); }
 
1120
 
 
1121
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
1122
template<class T, class ...Options>
 
1123
#else
 
1124
template<class Config>
 
1125
#endif
 
1126
inline bool operator>
 
1127
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
1128
(const sg_set_impl<T, Options...> &x, const sg_set_impl<T, Options...> &y)
 
1129
#else
 
1130
(const sg_set_impl<Config> &x, const sg_set_impl<Config> &y)
 
1131
#endif
 
1132
{  return y < x;  }
 
1133
 
 
1134
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
1135
template<class T, class ...Options>
 
1136
#else
 
1137
template<class Config>
 
1138
#endif
 
1139
inline bool operator<=
 
1140
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
1141
(const sg_set_impl<T, Options...> &x, const sg_set_impl<T, Options...> &y)
 
1142
#else
 
1143
(const sg_set_impl<Config> &x, const sg_set_impl<Config> &y)
 
1144
#endif
 
1145
{  return !(y < x);  }
 
1146
 
 
1147
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
1148
template<class T, class ...Options>
 
1149
#else
 
1150
template<class Config>
 
1151
#endif
 
1152
inline bool operator>=
 
1153
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
1154
(const sg_set_impl<T, Options...> &x, const sg_set_impl<T, Options...> &y)
 
1155
#else
 
1156
(const sg_set_impl<Config> &x, const sg_set_impl<Config> &y)
 
1157
#endif
 
1158
{  return !(x < y);  }
 
1159
 
 
1160
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
1161
template<class T, class ...Options>
 
1162
#else
 
1163
template<class Config>
 
1164
#endif
 
1165
inline void swap
 
1166
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
1167
(sg_set_impl<T, Options...> &x, sg_set_impl<T, Options...> &y)
 
1168
#else
 
1169
(sg_set_impl<Config> &x, sg_set_impl<Config> &y)
 
1170
#endif
 
1171
{  x.swap(y);  }
 
1172
 
 
1173
//! Helper metafunction to define a \c sg_set that yields to the same type when the
 
1174
//! same options (either explicitly or implicitly) are used.
 
1175
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 
1176
template<class T, class ...Options>
 
1177
#else
 
1178
template<class T, class O1 = none, class O2 = none
 
1179
                , class O3 = none, class O4 = none>
 
1180
#endif
 
1181
struct make_sg_set
 
1182
{
 
1183
   /// @cond
 
1184
   typedef sg_set_impl
 
1185
      < typename make_sgtree_opt<T, 
 
1186
      #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 
1187
      O1, O2, O3, O4
 
1188
      #else
 
1189
      Options...
 
1190
      #endif
 
1191
      >::type
 
1192
      > implementation_defined;
 
1193
   /// @endcond
 
1194
   typedef implementation_defined type;
 
1195
};
 
1196
 
 
1197
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 
1198
 
 
1199
#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 
1200
template<class T, class O1, class O2, class O3, class O4>
 
1201
#else
 
1202
template<class T, class ...Options>
 
1203
#endif
 
1204
class sg_set
 
1205
   :  public make_sg_set<T, 
 
1206
      #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 
1207
      O1, O2, O3, O4
 
1208
      #else
 
1209
      Options...
 
1210
      #endif
 
1211
      >::type
 
1212
{
 
1213
   typedef typename make_sg_set
 
1214
      <T, 
 
1215
      #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 
1216
      O1, O2, O3, O4
 
1217
      #else
 
1218
      Options...
 
1219
      #endif
 
1220
      >::type   Base;
 
1221
 
 
1222
   public:
 
1223
   typedef typename Base::value_compare      value_compare;
 
1224
   typedef typename Base::value_traits       value_traits;
 
1225
   typedef typename Base::iterator           iterator;
 
1226
   typedef typename Base::const_iterator     const_iterator;
 
1227
 
 
1228
   //Assert if passed value traits are compatible with the type
 
1229
   BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
 
1230
 
 
1231
   sg_set( const value_compare &cmp = value_compare()
 
1232
         , const value_traits &v_traits = value_traits())
 
1233
      :  Base(cmp, v_traits)
 
1234
   {}
 
1235
 
 
1236
   template<class Iterator>
 
1237
   sg_set( Iterator b, Iterator e
 
1238
      , const value_compare &cmp = value_compare()
 
1239
      , const value_traits &v_traits = value_traits())
 
1240
      :  Base(b, e, cmp, v_traits)
 
1241
   {}
 
1242
 
 
1243
   static sg_set &container_from_end_iterator(iterator end_iterator)
 
1244
   {  return static_cast<sg_set &>(Base::container_from_end_iterator(end_iterator));   }
 
1245
 
 
1246
   static const sg_set &container_from_end_iterator(const_iterator end_iterator)
 
1247
   {  return static_cast<const sg_set &>(Base::container_from_end_iterator(end_iterator));   }
 
1248
 
 
1249
   static sg_set &container_from_iterator(iterator it)
 
1250
   {  return static_cast<sg_set &>(Base::container_from_iterator(it));   }
 
1251
 
 
1252
   static const sg_set &container_from_iterator(const_iterator it)
 
1253
   {  return static_cast<const sg_set &>(Base::container_from_iterator(it));   }
 
1254
};
 
1255
 
 
1256
#endif
 
1257
 
 
1258
//! The class template sg_multiset is an intrusive container, that mimics most of 
 
1259
//! the interface of std::sg_multiset as described in the C++ standard.
 
1260
//! 
 
1261
//! The template parameter \c T is the type to be managed by the container.
 
1262
//! The user can specify additional options and if no options are provided
 
1263
//! default options are used.
 
1264
//!
 
1265
//! The container supports the following options:
 
1266
//! \c base_hook<>/member_hook<>/value_traits<>,
 
1267
//! \c constant_time_size<>, \c size_type<> and
 
1268
//! \c compare<>.
 
1269
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
1270
template<class T, class ...Options>
 
1271
#else
 
1272
template<class Config>
 
1273
#endif
 
1274
class sg_multiset_impl
 
1275
{
 
1276
   /// @cond
 
1277
   typedef sgtree_impl<Config> tree_type;
 
1278
 
 
1279
   //Non-copyable and non-assignable
 
1280
   sg_multiset_impl (const sg_multiset_impl&);
 
1281
   sg_multiset_impl &operator =(const sg_multiset_impl&);
 
1282
   typedef tree_type implementation_defined;
 
1283
   /// @endcond
 
1284
 
 
1285
   public:
 
1286
   typedef typename implementation_defined::value_type               value_type;
 
1287
   typedef typename implementation_defined::value_traits             value_traits;
 
1288
   typedef typename implementation_defined::pointer                  pointer;
 
1289
   typedef typename implementation_defined::const_pointer            const_pointer;
 
1290
   typedef typename implementation_defined::reference                reference;
 
1291
   typedef typename implementation_defined::const_reference          const_reference;
 
1292
   typedef typename implementation_defined::difference_type          difference_type;
 
1293
   typedef typename implementation_defined::size_type                size_type;
 
1294
   typedef typename implementation_defined::value_compare            value_compare;
 
1295
   typedef typename implementation_defined::key_compare              key_compare;
 
1296
   typedef typename implementation_defined::iterator                 iterator;
 
1297
   typedef typename implementation_defined::const_iterator           const_iterator;
 
1298
   typedef typename implementation_defined::reverse_iterator         reverse_iterator;
 
1299
   typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
 
1300
   typedef typename implementation_defined::insert_commit_data       insert_commit_data;
 
1301
   typedef typename implementation_defined::node_traits              node_traits;
 
1302
   typedef typename implementation_defined::node                     node;
 
1303
   typedef typename implementation_defined::node_ptr                 node_ptr;
 
1304
   typedef typename implementation_defined::const_node_ptr           const_node_ptr;
 
1305
   typedef typename implementation_defined::node_algorithms          node_algorithms;
 
1306
 
 
1307
   /// @cond
 
1308
   private:
 
1309
   tree_type tree_;
 
1310
   /// @endcond
 
1311
 
 
1312
   public:
 
1313
   //! <b>Effects</b>: Constructs an empty sg_multiset. 
 
1314
   //!   
 
1315
   //! <b>Complexity</b>: Constant. 
 
1316
   //! 
 
1317
   //! <b>Throws</b>: If value_traits::node_traits::node
 
1318
   //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks)
 
1319
   //!   or the copy constructor/operator() of the value_compare object throws. 
 
1320
   sg_multiset_impl( const value_compare &cmp = value_compare()
 
1321
                , const value_traits &v_traits = value_traits()) 
 
1322
      :  tree_(cmp, v_traits)
 
1323
   {}
 
1324
 
 
1325
   //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type. 
 
1326
   //!   cmp must be a comparison function that induces a strict weak ordering.
 
1327
   //! 
 
1328
   //! <b>Effects</b>: Constructs an empty sg_multiset and inserts elements from 
 
1329
   //!   [b, e).
 
1330
   //! 
 
1331
   //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using
 
1332
   //!   comp and otherwise N * log N, where N is the distance between first and last
 
1333
   //! 
 
1334
   //! <b>Throws</b>: If value_traits::node_traits::node
 
1335
   //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks)
 
1336
   //!   or the copy constructor/operator() of the value_compare object throws. 
 
1337
   template<class Iterator>
 
1338
   sg_multiset_impl( Iterator b, Iterator e
 
1339
                , const value_compare &cmp = value_compare()
 
1340
                , const value_traits &v_traits = value_traits())
 
1341
      : tree_(false, b, e, cmp, v_traits)
 
1342
   {}
 
1343
 
 
1344
   //! <b>Effects</b>: Detaches all elements from this. The objects in the sg_multiset 
 
1345
   //!   are not deleted (i.e. no destructors are called).
 
1346
   //! 
 
1347
   //! <b>Complexity</b>: Linear to the number of elements on the container.
 
1348
   //!   if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
 
1349
   //! 
 
1350
   //! <b>Throws</b>: Nothing.
 
1351
   ~sg_multiset_impl() 
 
1352
   {}
 
1353
 
 
1354
   //! <b>Effects</b>: Returns an iterator pointing to the beginning of the sg_multiset.
 
1355
   //! 
 
1356
   //! <b>Complexity</b>: Constant.
 
1357
   //! 
 
1358
   //! <b>Throws</b>: Nothing.
 
1359
   iterator begin()
 
1360
   { return tree_.begin();  }
 
1361
 
 
1362
   //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the sg_multiset.
 
1363
   //! 
 
1364
   //! <b>Complexity</b>: Constant.
 
1365
   //! 
 
1366
   //! <b>Throws</b>: Nothing.
 
1367
   const_iterator begin() const
 
1368
   { return tree_.begin();  }
 
1369
 
 
1370
   //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the sg_multiset.
 
1371
   //! 
 
1372
   //! <b>Complexity</b>: Constant.
 
1373
   //! 
 
1374
   //! <b>Throws</b>: Nothing.
 
1375
   const_iterator cbegin() const
 
1376
   { return tree_.cbegin();  }
 
1377
 
 
1378
   //! <b>Effects</b>: Returns an iterator pointing to the end of the sg_multiset.
 
1379
   //! 
 
1380
   //! <b>Complexity</b>: Constant.
 
1381
   //! 
 
1382
   //! <b>Throws</b>: Nothing.
 
1383
   iterator end()
 
1384
   { return tree_.end();  }
 
1385
 
 
1386
   //! <b>Effects</b>: Returns a const_iterator pointing to the end of the sg_multiset.
 
1387
   //! 
 
1388
   //! <b>Complexity</b>: Constant.
 
1389
   //! 
 
1390
   //! <b>Throws</b>: Nothing.
 
1391
   const_iterator end() const
 
1392
   { return tree_.end();  }
 
1393
 
 
1394
   //! <b>Effects</b>: Returns a const_iterator pointing to the end of the sg_multiset.
 
1395
   //! 
 
1396
   //! <b>Complexity</b>: Constant.
 
1397
   //! 
 
1398
   //! <b>Throws</b>: Nothing.
 
1399
   const_iterator cend() const
 
1400
   { return tree_.cend();  }
 
1401
 
 
1402
   //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning of the
 
1403
   //!    reversed sg_multiset.
 
1404
   //! 
 
1405
   //! <b>Complexity</b>: Constant.
 
1406
   //! 
 
1407
   //! <b>Throws</b>: Nothing.
 
1408
   reverse_iterator rbegin()
 
1409
   { return tree_.rbegin();  }
 
1410
 
 
1411
   //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
 
1412
   //!    of the reversed sg_multiset.
 
1413
   //! 
 
1414
   //! <b>Complexity</b>: Constant.
 
1415
   //! 
 
1416
   //! <b>Throws</b>: Nothing.
 
1417
   const_reverse_iterator rbegin() const
 
1418
   { return tree_.rbegin();  }
 
1419
 
 
1420
   //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
 
1421
   //!    of the reversed sg_multiset.
 
1422
   //! 
 
1423
   //! <b>Complexity</b>: Constant.
 
1424
   //! 
 
1425
   //! <b>Throws</b>: Nothing.
 
1426
   const_reverse_iterator crbegin() const
 
1427
   { return tree_.crbegin();  }
 
1428
 
 
1429
   //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
 
1430
   //!    of the reversed sg_multiset.
 
1431
   //! 
 
1432
   //! <b>Complexity</b>: Constant.
 
1433
   //! 
 
1434
   //! <b>Throws</b>: Nothing.
 
1435
   reverse_iterator rend()
 
1436
   { return tree_.rend();  }
 
1437
 
 
1438
   //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
 
1439
   //!    of the reversed sg_multiset.
 
1440
   //! 
 
1441
   //! <b>Complexity</b>: Constant.
 
1442
   //! 
 
1443
   //! <b>Throws</b>: Nothing.
 
1444
   const_reverse_iterator rend() const
 
1445
   { return tree_.rend();  }
 
1446
 
 
1447
   //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
 
1448
   //!    of the reversed sg_multiset.
 
1449
   //! 
 
1450
   //! <b>Complexity</b>: Constant.
 
1451
   //! 
 
1452
   //! <b>Throws</b>: Nothing.
 
1453
   const_reverse_iterator crend() const
 
1454
   { return tree_.crend();  }
 
1455
 
 
1456
   //! <b>Precondition</b>: end_iterator must be a valid end iterator
 
1457
   //!   of sg_multiset.
 
1458
   //! 
 
1459
   //! <b>Effects</b>: Returns a const reference to the sg_multiset associated to the end iterator
 
1460
   //! 
 
1461
   //! <b>Throws</b>: Nothing.
 
1462
   //! 
 
1463
   //! <b>Complexity</b>: Constant.
 
1464
   static sg_multiset_impl &container_from_end_iterator(iterator end_iterator)
 
1465
   {
 
1466
      return *detail::parent_from_member<sg_multiset_impl, tree_type>
 
1467
         ( &tree_type::container_from_end_iterator(end_iterator)
 
1468
         , &sg_multiset_impl::tree_);
 
1469
   }
 
1470
 
 
1471
   //! <b>Precondition</b>: end_iterator must be a valid end const_iterator
 
1472
   //!   of sg_multiset.
 
1473
   //! 
 
1474
   //! <b>Effects</b>: Returns a const reference to the sg_multiset associated to the end iterator
 
1475
   //! 
 
1476
   //! <b>Throws</b>: Nothing.
 
1477
   //! 
 
1478
   //! <b>Complexity</b>: Constant.
 
1479
   static const sg_multiset_impl &container_from_end_iterator(const_iterator end_iterator)
 
1480
   {
 
1481
      return *detail::parent_from_member<sg_multiset_impl, tree_type>
 
1482
         ( &tree_type::container_from_end_iterator(end_iterator)
 
1483
         , &sg_multiset_impl::tree_);
 
1484
   }
 
1485
 
 
1486
   //! <b>Precondition</b>: it must be a valid iterator of multiset.
 
1487
   //! 
 
1488
   //! <b>Effects</b>: Returns a const reference to the multiset associated to the iterator
 
1489
   //! 
 
1490
   //! <b>Throws</b>: Nothing.
 
1491
   //! 
 
1492
   //! <b>Complexity</b>: Constant.
 
1493
   static sg_multiset_impl &container_from_iterator(iterator it)
 
1494
   {
 
1495
      return *detail::parent_from_member<sg_multiset_impl, tree_type>
 
1496
         ( &tree_type::container_from_iterator(it)
 
1497
         , &sg_multiset_impl::tree_);
 
1498
   }
 
1499
 
 
1500
   //! <b>Precondition</b>: it must be a valid const_iterator of multiset.
 
1501
   //! 
 
1502
   //! <b>Effects</b>: Returns a const reference to the multiset associated to the iterator
 
1503
   //! 
 
1504
   //! <b>Throws</b>: Nothing.
 
1505
   //! 
 
1506
   //! <b>Complexity</b>: Constant.
 
1507
   static const sg_multiset_impl &container_from_iterator(const_iterator it)
 
1508
   {
 
1509
      return *detail::parent_from_member<sg_multiset_impl, tree_type>
 
1510
         ( &tree_type::container_from_iterator(it)
 
1511
         , &sg_multiset_impl::tree_);
 
1512
   }
 
1513
 
 
1514
   //! <b>Effects</b>: Returns the key_compare object used by the sg_multiset.
 
1515
   //! 
 
1516
   //! <b>Complexity</b>: Constant.
 
1517
   //! 
 
1518
   //! <b>Throws</b>: If key_compare copy-constructor throws.
 
1519
   key_compare key_comp() const
 
1520
   { return tree_.value_comp(); }
 
1521
 
 
1522
   //! <b>Effects</b>: Returns the value_compare object used by the sg_multiset.
 
1523
   //! 
 
1524
   //! <b>Complexity</b>: Constant.
 
1525
   //! 
 
1526
   //! <b>Throws</b>: If value_compare copy-constructor throws.
 
1527
   value_compare value_comp() const
 
1528
   { return tree_.value_comp(); }
 
1529
 
 
1530
   //! <b>Effects</b>: Returns true if the container is empty.
 
1531
   //! 
 
1532
   //! <b>Complexity</b>: Constant.
 
1533
   //! 
 
1534
   //! <b>Throws</b>: Nothing.
 
1535
   bool empty() const
 
1536
   { return tree_.empty(); }
 
1537
 
 
1538
   //! <b>Effects</b>: Returns the number of elements stored in the sg_multiset.
 
1539
   //! 
 
1540
   //! <b>Complexity</b>: Linear to elements contained in *this if,
 
1541
   //!   constant-time size option is enabled. Constant-time otherwise.
 
1542
   //! 
 
1543
   //! <b>Throws</b>: Nothing.
 
1544
   size_type size() const
 
1545
   { return tree_.size(); }
 
1546
 
 
1547
   //! <b>Effects</b>: Swaps the contents of two sg_multisets.
 
1548
   //! 
 
1549
   //! <b>Complexity</b>: Constant.
 
1550
   //! 
 
1551
   //! <b>Throws</b>: If the swap() call for the comparison functor
 
1552
   //!   found using ADL throws. Strong guarantee.
 
1553
   void swap(sg_multiset_impl& other)
 
1554
   { tree_.swap(other.tree_); }
 
1555
 
 
1556
   //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
 
1557
   //!   Cloner should yield to nodes equivalent to the original nodes.
 
1558
   //!
 
1559
   //! <b>Effects</b>: Erases all the elements from *this
 
1560
   //!   calling Disposer::operator()(pointer), clones all the 
 
1561
   //!   elements from src calling Cloner::operator()(const_reference )
 
1562
   //!   and inserts them on *this. Copies the predicate from the source container.
 
1563
   //!
 
1564
   //!   If cloner throws, all cloned elements are unlinked and disposed
 
1565
   //!   calling Disposer::operator()(pointer).
 
1566
   //!   
 
1567
   //! <b>Complexity</b>: Linear to erased plus inserted elements.
 
1568
   //! 
 
1569
   //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee.
 
1570
   template <class Cloner, class Disposer>
 
1571
   void clone_from(const sg_multiset_impl &src, Cloner cloner, Disposer disposer)
 
1572
   {  tree_.clone_from(src.tree_, cloner, disposer);  }
 
1573
 
 
1574
   //! <b>Requires</b>: value must be an lvalue
 
1575
   //! 
 
1576
   //! <b>Effects</b>: Inserts value into the sg_multiset.
 
1577
   //! 
 
1578
   //! <b>Returns</b>: An iterator that points to the position where the new
 
1579
   //!   element was inserted.
 
1580
   //! 
 
1581
   //! <b>Complexity</b>: Average complexity for insert element is at
 
1582
   //!   most logarithmic.
 
1583
   //! 
 
1584
   //! <b>Throws</b>: If the internal value_compare ordering function throws. Strong guarantee.
 
1585
   //! 
 
1586
   //! <b>Note</b>: Does not affect the validity of iterators and references.
 
1587
   //!   No copy-constructors are called.
 
1588
   iterator insert(reference value)
 
1589
   {  return tree_.insert_equal(value);  }
 
1590
 
 
1591
   //! <b>Requires</b>: value must be an lvalue
 
1592
   //! 
 
1593
   //! <b>Effects</b>: Inserts x into the sg_multiset, using pos as a hint to
 
1594
   //!   where it will be inserted.
 
1595
   //! 
 
1596
   //! <b>Returns</b>: An iterator that points to the position where the new
 
1597
   //!   element was inserted.
 
1598
   //! 
 
1599
   //! <b>Complexity</b>: Logarithmic in general, but it is amortized
 
1600
   //!   constant time if t is inserted immediately before hint.
 
1601
   //! 
 
1602
   //! <b>Throws</b>: If the internal value_compare ordering function throws. Strong guarantee.
 
1603
   //! 
 
1604
   //! <b>Note</b>: Does not affect the validity of iterators and references.
 
1605
   //!   No copy-constructors are called.
 
1606
   iterator insert(const_iterator hint, reference value)
 
1607
   {  return tree_.insert_equal(hint, value);  }
 
1608
 
 
1609
   //! <b>Requires</b>: Dereferencing iterator must yield an lvalue 
 
1610
   //!   of type value_type.
 
1611
   //! 
 
1612
   //! <b>Effects</b>: Inserts a range into the sg_multiset.
 
1613
   //! 
 
1614
   //! <b>Returns</b>: An iterator that points to the position where the new
 
1615
   //!   element was inserted.
 
1616
   //! 
 
1617
   //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the
 
1618
   //!   size of the range. However, it is linear in N if the range is already sorted
 
1619
   //!   by value_comp().
 
1620
   //! 
 
1621
   //! <b>Throws</b>: If the internal value_compare ordering function throws. Basic guarantee.
 
1622
   //! 
 
1623
   //! <b>Note</b>: Does not affect the validity of iterators and references.
 
1624
   //!   No copy-constructors are called.
 
1625
   template<class Iterator>
 
1626
   void insert(Iterator b, Iterator e)
 
1627
   {  tree_.insert_equal(b, e);  }
 
1628
 
 
1629
   //! <b>Requires</b>: value must be an lvalue, "pos" must be
 
1630
   //!   a valid iterator (or end) and must be the succesor of value
 
1631
   //!   once inserted according to the predicate
 
1632
   //!
 
1633
   //! <b>Effects</b>: Inserts x into the tree before "pos".
 
1634
   //! 
 
1635
   //! <b>Complexity</b>: Constant time.
 
1636
   //! 
 
1637
   //! <b>Throws</b>: Nothing.
 
1638
   //! 
 
1639
   //! <b>Note</b>: This function does not check preconditions so if "pos" is not
 
1640
   //! the successor of "value" tree ordering invariant will be broken.
 
1641
   //! This is a low-level function to be used only for performance reasons
 
1642
   //! by advanced users.
 
1643
   iterator insert_before(const_iterator pos, reference value)
 
1644
   {  return tree_.insert_before(pos, value);  }
 
1645
 
 
1646
   //! <b>Requires</b>: value must be an lvalue, and it must be no less
 
1647
   //!   than the greatest inserted key
 
1648
   //!
 
1649
   //! <b>Effects</b>: Inserts x into the tree in the last position.
 
1650
   //! 
 
1651
   //! <b>Complexity</b>: Constant time.
 
1652
   //! 
 
1653
   //! <b>Throws</b>: Nothing.
 
1654
   //! 
 
1655
   //! <b>Note</b>: This function does not check preconditions so if value is
 
1656
   //!   less than the greatest inserted key tree ordering invariant will be broken.
 
1657
   //!   This function is slightly more efficient than using "insert_before".
 
1658
   //!   This is a low-level function to be used only for performance reasons
 
1659
   //!   by advanced users.
 
1660
   void push_back(reference value)
 
1661
   {  tree_.push_back(value);  }
 
1662
 
 
1663
   //! <b>Requires</b>: value must be an lvalue, and it must be no greater
 
1664
   //!   than the minimum inserted key
 
1665
   //!
 
1666
   //! <b>Effects</b>: Inserts x into the tree in the first position.
 
1667
   //! 
 
1668
   //! <b>Complexity</b>: Constant time.
 
1669
   //! 
 
1670
   //! <b>Throws</b>: Nothing.
 
1671
   //! 
 
1672
   //! <b>Note</b>: This function does not check preconditions so if value is
 
1673
   //!   greater than the minimum inserted key tree ordering invariant will be broken.
 
1674
   //!   This function is slightly more efficient than using "insert_before".
 
1675
   //!   This is a low-level function to be used only for performance reasons
 
1676
   //!   by advanced users.
 
1677
   void push_front(reference value)
 
1678
   {  tree_.push_front(value);  }
 
1679
 
 
1680
   //! <b>Effects</b>: Erases the element pointed to by pos. 
 
1681
   //! 
 
1682
   //! <b>Complexity</b>: Average complexity is constant time. 
 
1683
   //! 
 
1684
   //! <b>Returns</b>: An iterator to the element after the erased element.
 
1685
   //!
 
1686
   //! <b>Throws</b>: Nothing.
 
1687
   //! 
 
1688
   //! <b>Note</b>: Invalidates the iterators (but not the references)
 
1689
   //!    to the erased elements. No destructors are called.
 
1690
   iterator erase(const_iterator i)
 
1691
   {  return tree_.erase(i);  }
 
1692
 
 
1693
   //! <b>Effects</b>: Erases the range pointed to by b end e. 
 
1694
   //!
 
1695
   //! <b>Returns</b>: An iterator to the element after the erased elements.
 
1696
   //! 
 
1697
   //! <b>Complexity</b>: Average complexity for erase range is at most 
 
1698
   //!   O(log(size() + N)), where N is the number of elements in the range.
 
1699
   //! 
 
1700
   //! <b>Throws</b>: Nothing.
 
1701
   //! 
 
1702
   //! <b>Note</b>: Invalidates the iterators (but not the references)
 
1703
   //!    to the erased elements. No destructors are called.
 
1704
   iterator erase(const_iterator b, const_iterator e)
 
1705
   {  return tree_.erase(b, e);  }
 
1706
 
 
1707
   //! <b>Effects</b>: Erases all the elements with the given value.
 
1708
   //! 
 
1709
   //! <b>Returns</b>: The number of erased elements.
 
1710
   //! 
 
1711
   //! <b>Complexity</b>: O(log(size() + this->count(value)).
 
1712
   //! 
 
1713
   //! <b>Throws</b>: If the internal value_compare ordering function throws. Basic guarantee.
 
1714
   //! 
 
1715
   //! <b>Note</b>: Invalidates the iterators (but not the references)
 
1716
   //!    to the erased elements. No destructors are called.
 
1717
   size_type erase(const_reference value)
 
1718
   {  return tree_.erase(value);  }
 
1719
 
 
1720
   //! <b>Effects</b>: Erases all the elements that compare equal with
 
1721
   //!   the given key and the given comparison functor.
 
1722
   //! 
 
1723
   //! <b>Returns</b>: The number of erased elements.
 
1724
   //! 
 
1725
   //! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
 
1726
   //! 
 
1727
   //! <b>Throws</b>: If comp ordering function throws. Basic guarantee.
 
1728
   //! 
 
1729
   //! <b>Note</b>: Invalidates the iterators (but not the references)
 
1730
   //!    to the erased elements. No destructors are called.
 
1731
   template<class KeyType, class KeyValueCompare>
 
1732
   size_type erase(const KeyType& key, KeyValueCompare comp
 
1733
                  /// @cond
 
1734
                  , typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
 
1735
                  /// @endcond
 
1736
                  )
 
1737
   {  return tree_.erase(key, comp);  }
 
1738
 
 
1739
   //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
 
1740
   //!
 
1741
   //! <b>Returns</b>: An iterator to the element after the erased element.
 
1742
   //!
 
1743
   //! <b>Effects</b>: Erases the element pointed to by pos. 
 
1744
   //!   Disposer::operator()(pointer) is called for the removed element.
 
1745
   //! 
 
1746
   //! <b>Complexity</b>: Average complexity for erase element is constant time. 
 
1747
   //! 
 
1748
   //! <b>Throws</b>: Nothing.
 
1749
   //! 
 
1750
   //! <b>Note</b>: Invalidates the iterators 
 
1751
   //!    to the erased elements.
 
1752
   template<class Disposer>
 
1753
   iterator erase_and_dispose(const_iterator i, Disposer disposer)
 
1754
   {  return tree_.erase_and_dispose(i, disposer);  }
 
1755
 
 
1756
   #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
1757
   template<class Disposer>
 
1758
   iterator erase_and_dispose(iterator i, Disposer disposer)
 
1759
   {  return this->erase_and_dispose(const_iterator(i), disposer);   }
 
1760
   #endif
 
1761
 
 
1762
   //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
 
1763
   //!
 
1764
   //! <b>Returns</b>: An iterator to the element after the erased elements.
 
1765
   //!
 
1766
   //! <b>Effects</b>: Erases the range pointed to by b end e.
 
1767
   //!   Disposer::operator()(pointer) is called for the removed elements.
 
1768
   //! 
 
1769
   //! <b>Complexity</b>: Average complexity for erase range is at most 
 
1770
   //!   O(log(size() + N)), where N is the number of elements in the range.
 
1771
   //! 
 
1772
   //! <b>Throws</b>: Nothing.
 
1773
   //! 
 
1774
   //! <b>Note</b>: Invalidates the iterators
 
1775
   //!    to the erased elements.
 
1776
   template<class Disposer>
 
1777
   iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
 
1778
   {  return tree_.erase_and_dispose(b, e, disposer);  }
 
1779
 
 
1780
   //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
 
1781
   //!
 
1782
   //! <b>Effects</b>: Erases all the elements with the given value.
 
1783
   //!   Disposer::operator()(pointer) is called for the removed elements.
 
1784
   //! 
 
1785
   //! <b>Returns</b>: The number of erased elements.
 
1786
   //! 
 
1787
   //! <b>Complexity</b>: O(log(size() + this->count(value)).
 
1788
   //! 
 
1789
   //! <b>Throws</b>: If the internal value_compare ordering function throws. Basic guarantee.
 
1790
   //! 
 
1791
   //! <b>Note</b>: Invalidates the iterators (but not the references)
 
1792
   //!    to the erased elements. No destructors are called.
 
1793
   template<class Disposer>
 
1794
   size_type erase_and_dispose(const_reference value, Disposer disposer)
 
1795
   {  return tree_.erase_and_dispose(value, disposer);  }
 
1796
 
 
1797
   //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
 
1798
   //!
 
1799
   //! <b>Effects</b>: Erases all the elements with the given key.
 
1800
   //!   according to the comparison functor "comp".
 
1801
   //!   Disposer::operator()(pointer) is called for the removed elements.
 
1802
   //!
 
1803
   //! <b>Returns</b>: The number of erased elements.
 
1804
   //! 
 
1805
   //! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
 
1806
   //! 
 
1807
   //! <b>Throws</b>: If comp ordering function throws. Basic guarantee.
 
1808
   //! 
 
1809
   //! <b>Note</b>: Invalidates the iterators
 
1810
   //!    to the erased elements.
 
1811
   template<class KeyType, class KeyValueCompare, class Disposer>
 
1812
   size_type erase_and_dispose(const KeyType& key, KeyValueCompare comp, Disposer disposer
 
1813
                  /// @cond
 
1814
                  , typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
 
1815
                  /// @endcond
 
1816
                  )
 
1817
   {  return tree_.erase_and_dispose(key, comp, disposer);  }
 
1818
 
 
1819
   //! <b>Effects</b>: Erases all the elements of the container.
 
1820
   //! 
 
1821
   //! <b>Complexity</b>: Linear to the number of elements on the container.
 
1822
   //!   if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
 
1823
   //! 
 
1824
   //! <b>Throws</b>: Nothing.
 
1825
   //! 
 
1826
   //! <b>Note</b>: Invalidates the iterators (but not the references)
 
1827
   //!    to the erased elements. No destructors are called.
 
1828
   void clear()
 
1829
   {  return tree_.clear();  }
 
1830
 
 
1831
   //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
 
1832
   //! 
 
1833
   //! <b>Effects</b>: Erases all the elements of the container.
 
1834
   //! 
 
1835
   //! <b>Complexity</b>: Linear to the number of elements on the container.
 
1836
   //!   Disposer::operator()(pointer) is called for the removed elements.
 
1837
   //! 
 
1838
   //! <b>Throws</b>: Nothing.
 
1839
   //! 
 
1840
   //! <b>Note</b>: Invalidates the iterators (but not the references)
 
1841
   //!    to the erased elements. No destructors are called.
 
1842
   template<class Disposer>
 
1843
   void clear_and_dispose(Disposer disposer)
 
1844
   {  return tree_.clear_and_dispose(disposer);  }
 
1845
 
 
1846
   //! <b>Effects</b>: Returns the number of contained elements with the given key
 
1847
   //! 
 
1848
   //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
 
1849
   //!   to number of objects with the given key.
 
1850
   //! 
 
1851
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
1852
   size_type count(const_reference value) const
 
1853
   {  return tree_.count(value);  }
 
1854
 
 
1855
   //! <b>Effects</b>: Returns the number of contained elements with the same key
 
1856
   //!   compared with the given comparison functor.
 
1857
   //! 
 
1858
   //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
 
1859
   //!   to number of objects with the given key.
 
1860
   //! 
 
1861
   //! <b>Throws</b>: If comp ordering function throws.
 
1862
   template<class KeyType, class KeyValueCompare>
 
1863
   size_type count(const KeyType& key, KeyValueCompare comp) const
 
1864
   {  return tree_.count(key, comp);  }
 
1865
 
 
1866
   //! <b>Effects</b>: Returns an iterator to the first element whose
 
1867
   //!   key is not less than k or end() if that element does not exist.
 
1868
   //! 
 
1869
   //! <b>Complexity</b>: Logarithmic.
 
1870
   //! 
 
1871
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
1872
   iterator lower_bound(const_reference value)
 
1873
   {  return tree_.lower_bound(value);  }
 
1874
 
 
1875
   //! <b>Requires</b>: comp must imply the same element order as
 
1876
   //!   value_compare. Usually key is the part of the value_type
 
1877
   //!   that is used in the ordering functor.
 
1878
   //!
 
1879
   //! <b>Effects</b>: Returns an iterator to the first element whose
 
1880
   //!   key according to the comparison functor is not less than k or 
 
1881
   //!   end() if that element does not exist.
 
1882
   //! 
 
1883
   //! <b>Complexity</b>: Logarithmic.
 
1884
   //! 
 
1885
   //! <b>Throws</b>: If comp ordering function throws.
 
1886
   //! 
 
1887
   //! <b>Note</b>: This function is used when constructing a value_type
 
1888
   //!   is expensive and the value_type can be compared with a cheaper
 
1889
   //!   key type. Usually this key is part of the value_type.
 
1890
   template<class KeyType, class KeyValueCompare>
 
1891
   iterator lower_bound(const KeyType& key, KeyValueCompare comp)
 
1892
   {  return tree_.lower_bound(key, comp);  }
 
1893
 
 
1894
   //! <b>Effects</b>: Returns a const iterator to the first element whose
 
1895
   //!   key is not less than k or end() if that element does not exist.
 
1896
   //! 
 
1897
   //! <b>Complexity</b>: Logarithmic.
 
1898
   //! 
 
1899
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
1900
   const_iterator lower_bound(const_reference value) const
 
1901
   {  return tree_.lower_bound(value);  }
 
1902
 
 
1903
   //! <b>Requires</b>: comp must imply the same element order as
 
1904
   //!   value_compare. Usually key is the part of the value_type
 
1905
   //!   that is used in the ordering functor.
 
1906
   //!
 
1907
   //! <b>Effects</b>: Returns a const_iterator to the first element whose
 
1908
   //!   key according to the comparison functor is not less than k or 
 
1909
   //!   end() if that element does not exist.
 
1910
   //! 
 
1911
   //! <b>Complexity</b>: Logarithmic.
 
1912
   //! 
 
1913
   //! <b>Throws</b>: If comp ordering function throws.
 
1914
   //! 
 
1915
   //! <b>Note</b>: This function is used when constructing a value_type
 
1916
   //!   is expensive and the value_type can be compared with a cheaper
 
1917
   //!   key type. Usually this key is part of the value_type.
 
1918
   template<class KeyType, class KeyValueCompare>
 
1919
   const_iterator lower_bound(const KeyType& key, KeyValueCompare comp) const
 
1920
   {  return tree_.lower_bound(key, comp);  }
 
1921
 
 
1922
   //! <b>Effects</b>: Returns an iterator to the first element whose
 
1923
   //!   key is greater than k or end() if that element does not exist.
 
1924
   //! 
 
1925
   //! <b>Complexity</b>: Logarithmic.
 
1926
   //! 
 
1927
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
1928
   iterator upper_bound(const_reference value)
 
1929
   {  return tree_.upper_bound(value);  }
 
1930
 
 
1931
   //! <b>Requires</b>: comp must imply the same element order as
 
1932
   //!   value_compare. Usually key is the part of the value_type
 
1933
   //!   that is used in the ordering functor.
 
1934
   //!
 
1935
   //! <b>Effects</b>: Returns an iterator to the first element whose
 
1936
   //!   key according to the comparison functor is greater than key or 
 
1937
   //!   end() if that element does not exist.
 
1938
   //! 
 
1939
   //! <b>Complexity</b>: Logarithmic.
 
1940
   //! 
 
1941
   //! <b>Throws</b>: If comp ordering function throws.
 
1942
   //!
 
1943
   //! <b>Note</b>: This function is used when constructing a value_type
 
1944
   //!   is expensive and the value_type can be compared with a cheaper
 
1945
   //!   key type. Usually this key is part of the value_type.
 
1946
   template<class KeyType, class KeyValueCompare>
 
1947
   iterator upper_bound(const KeyType& key, KeyValueCompare comp)
 
1948
   {  return tree_.upper_bound(key, comp);  }
 
1949
 
 
1950
   //! <b>Effects</b>: Returns an iterator to the first element whose
 
1951
   //!   key is greater than k or end() if that element does not exist.
 
1952
   //! 
 
1953
   //! <b>Complexity</b>: Logarithmic.
 
1954
   //! 
 
1955
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
1956
   const_iterator upper_bound(const_reference value) const
 
1957
   {  return tree_.upper_bound(value);  }
 
1958
 
 
1959
   //! <b>Requires</b>: comp must imply the same element order as
 
1960
   //!   value_compare. Usually key is the part of the value_type
 
1961
   //!   that is used in the ordering functor.
 
1962
   //!
 
1963
   //! <b>Effects</b>: Returns a const_iterator to the first element whose
 
1964
   //!   key according to the comparison functor is greater than key or 
 
1965
   //!   end() if that element does not exist.
 
1966
   //! 
 
1967
   //! <b>Complexity</b>: Logarithmic.
 
1968
   //! 
 
1969
   //! <b>Throws</b>: If comp ordering function throws.
 
1970
   //!
 
1971
   //! <b>Note</b>: This function is used when constructing a value_type
 
1972
   //!   is expensive and the value_type can be compared with a cheaper
 
1973
   //!   key type. Usually this key is part of the value_type.
 
1974
   template<class KeyType, class KeyValueCompare>
 
1975
   const_iterator upper_bound(const KeyType& key, KeyValueCompare comp) const
 
1976
   {  return tree_.upper_bound(key, comp);  }
 
1977
 
 
1978
   //! <b>Effects</b>: Finds an iterator to the first element whose value is 
 
1979
   //!   "value" or end() if that element does not exist.
 
1980
   //!
 
1981
   //! <b>Complexity</b>: Logarithmic.
 
1982
   //! 
 
1983
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
1984
   iterator find(const_reference value)
 
1985
   {  return tree_.find(value);  }
 
1986
 
 
1987
   //! <b>Requires</b>: comp must imply the same element order as
 
1988
   //!   value_compare. Usually key is the part of the value_type
 
1989
   //!   that is used in the ordering functor.
 
1990
   //!
 
1991
   //! <b>Effects</b>: Finds an iterator to the first element whose key is 
 
1992
   //!   "key" according to the comparison functor or end() if that element 
 
1993
   //!   does not exist.
 
1994
   //!
 
1995
   //! <b>Complexity</b>: Logarithmic.
 
1996
   //! 
 
1997
   //! <b>Throws</b>: If comp ordering function throws.
 
1998
   //!
 
1999
   //! <b>Note</b>: This function is used when constructing a value_type
 
2000
   //!   is expensive and the value_type can be compared with a cheaper
 
2001
   //!   key type. Usually this key is part of the value_type.
 
2002
   template<class KeyType, class KeyValueCompare>
 
2003
   iterator find(const KeyType& key, KeyValueCompare comp)
 
2004
   {  return tree_.find(key, comp);  }
 
2005
 
 
2006
   //! <b>Effects</b>: Finds a const_iterator to the first element whose value is 
 
2007
   //!   "value" or end() if that element does not exist.
 
2008
   //! 
 
2009
   //! <b>Complexity</b>: Logarithmic.
 
2010
   //! 
 
2011
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
2012
   const_iterator find(const_reference value) const
 
2013
   {  return tree_.find(value);  }
 
2014
 
 
2015
   //! <b>Requires</b>: comp must imply the same element order as
 
2016
   //!   value_compare. Usually key is the part of the value_type
 
2017
   //!   that is used in the ordering functor.
 
2018
   //!
 
2019
   //! <b>Effects</b>: Finds a const_iterator to the first element whose key is 
 
2020
   //!   "key" according to the comparison functor or end() if that element 
 
2021
   //!   does not exist.
 
2022
   //! 
 
2023
   //! <b>Complexity</b>: Logarithmic.
 
2024
   //! 
 
2025
   //! <b>Throws</b>: If comp ordering function throws.
 
2026
   //!
 
2027
   //! <b>Note</b>: This function is used when constructing a value_type
 
2028
   //!   is expensive and the value_type can be compared with a cheaper
 
2029
   //!   key type. Usually this key is part of the value_type.
 
2030
   template<class KeyType, class KeyValueCompare>
 
2031
   const_iterator find(const KeyType& key, KeyValueCompare comp) const
 
2032
   {  return tree_.find(key, comp);  }
 
2033
 
 
2034
   //! <b>Effects</b>: Finds a range containing all elements whose key is k or
 
2035
   //!   an empty range that indicates the position where those elements would be
 
2036
   //!   if they there is no elements with key k.
 
2037
   //! 
 
2038
   //! <b>Complexity</b>: Logarithmic.
 
2039
   //! 
 
2040
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
2041
   std::pair<iterator,iterator> equal_range(const_reference value)
 
2042
   {  return tree_.equal_range(value);  }
 
2043
 
 
2044
   //! <b>Requires</b>: comp must imply the same element order as
 
2045
   //!   value_compare. Usually key is the part of the value_type
 
2046
   //!   that is used in the ordering functor.
 
2047
   //!
 
2048
   //! <b>Effects</b>: Finds a range containing all elements whose key is k 
 
2049
   //!   according to the comparison functor or an empty range 
 
2050
   //!   that indicates the position where those elements would be
 
2051
   //!   if they there is no elements with key k.
 
2052
   //! 
 
2053
   //! <b>Complexity</b>: Logarithmic.
 
2054
   //! 
 
2055
   //! <b>Throws</b>: If comp ordering function throws.
 
2056
   //!
 
2057
   //! <b>Note</b>: This function is used when constructing a value_type
 
2058
   //!   is expensive and the value_type can be compared with a cheaper
 
2059
   //!   key type. Usually this key is part of the value_type.
 
2060
   template<class KeyType, class KeyValueCompare>
 
2061
   std::pair<iterator,iterator> equal_range(const KeyType& key, KeyValueCompare comp)
 
2062
   {  return tree_.equal_range(key, comp);  }
 
2063
 
 
2064
   //! <b>Effects</b>: Finds a range containing all elements whose key is k or
 
2065
   //!   an empty range that indicates the position where those elements would be
 
2066
   //!   if they there is no elements with key k.
 
2067
   //! 
 
2068
   //! <b>Complexity</b>: Logarithmic.
 
2069
   //! 
 
2070
   //! <b>Throws</b>: If the internal value_compare ordering function throws.
 
2071
   std::pair<const_iterator, const_iterator>
 
2072
      equal_range(const_reference value) const
 
2073
   {  return tree_.equal_range(value);  }
 
2074
 
 
2075
   //! <b>Requires</b>: comp must imply the same element order as
 
2076
   //!   value_compare. Usually key is the part of the value_type
 
2077
   //!   that is used in the ordering functor.
 
2078
   //!
 
2079
   //! <b>Effects</b>: Finds a range containing all elements whose key is k 
 
2080
   //!   according to the comparison functor or an empty range 
 
2081
   //!   that indicates the position where those elements would be
 
2082
   //!   if they there is no elements with key k.
 
2083
   //! 
 
2084
   //! <b>Complexity</b>: Logarithmic.
 
2085
   //! 
 
2086
   //! <b>Throws</b>: If comp ordering function throws.
 
2087
   //!
 
2088
   //! <b>Note</b>: This function is used when constructing a value_type
 
2089
   //!   is expensive and the value_type can be compared with a cheaper
 
2090
   //!   key type. Usually this key is part of the value_type.
 
2091
   template<class KeyType, class KeyValueCompare>
 
2092
   std::pair<const_iterator, const_iterator>
 
2093
      equal_range(const KeyType& key, KeyValueCompare comp) const
 
2094
   {  return tree_.equal_range(key, comp);  }
 
2095
 
 
2096
   //! <b>Requires</b>: value must be an lvalue and shall be in a sg_multiset of
 
2097
   //!   appropriate type. Otherwise the behavior is undefined.
 
2098
   //! 
 
2099
   //! <b>Effects</b>: Returns: a valid iterator i belonging to the sg_multiset
 
2100
   //!   that points to the value
 
2101
   //! 
 
2102
   //! <b>Complexity</b>: Constant.
 
2103
   //! 
 
2104
   //! <b>Throws</b>: Nothing.
 
2105
   //! 
 
2106
   //! <b>Note</b>: This static function is available only if the <i>value traits</i>
 
2107
   //!   is stateless.
 
2108
   static iterator s_iterator_to(reference value)
 
2109
   {  return tree_type::s_iterator_to(value);  }
 
2110
 
 
2111
   //! <b>Requires</b>: value must be an lvalue and shall be in a sg_multiset of
 
2112
   //!   appropriate type. Otherwise the behavior is undefined.
 
2113
   //! 
 
2114
   //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
 
2115
   //!   sg_multiset that points to the value
 
2116
   //! 
 
2117
   //! <b>Complexity</b>: Constant.
 
2118
   //! 
 
2119
   //! <b>Throws</b>: Nothing.
 
2120
   //! 
 
2121
   //! <b>Note</b>: This static function is available only if the <i>value traits</i>
 
2122
   //!   is stateless.
 
2123
   static const_iterator s_iterator_to(const_reference value)
 
2124
   {  return tree_type::s_iterator_to(value);  }
 
2125
 
 
2126
   //! <b>Requires</b>: value must be an lvalue and shall be in a sg_multiset of
 
2127
   //!   appropriate type. Otherwise the behavior is undefined.
 
2128
   //! 
 
2129
   //! <b>Effects</b>: Returns: a valid iterator i belonging to the sg_multiset
 
2130
   //!   that points to the value
 
2131
   //! 
 
2132
   //! <b>Complexity</b>: Constant.
 
2133
   //! 
 
2134
   //! <b>Throws</b>: Nothing.
 
2135
   iterator iterator_to(reference value)
 
2136
   {  return tree_.iterator_to(value);  }
 
2137
 
 
2138
   //! <b>Requires</b>: value must be an lvalue and shall be in a sg_multiset of
 
2139
   //!   appropriate type. Otherwise the behavior is undefined.
 
2140
   //! 
 
2141
   //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
 
2142
   //!   sg_multiset that points to the value
 
2143
   //! 
 
2144
   //! <b>Complexity</b>: Constant.
 
2145
   //! 
 
2146
   //! <b>Throws</b>: Nothing.
 
2147
   const_iterator iterator_to(const_reference value) const
 
2148
   {  return tree_.iterator_to(value);  }
 
2149
 
 
2150
   //! <b>Requires</b>: value shall not be in a sg_multiset/sg_multiset.
 
2151
   //! 
 
2152
   //! <b>Effects</b>: init_node puts the hook of a value in a well-known default
 
2153
   //!   state.
 
2154
   //! 
 
2155
   //! <b>Throws</b>: Nothing.
 
2156
   //! 
 
2157
   //! <b>Complexity</b>: Constant time.
 
2158
   //! 
 
2159
   //! <b>Note</b>: This function puts the hook in the well-known default state
 
2160
   //!   used by auto_unlink and safe hooks.
 
2161
   static void init_node(reference value)
 
2162
   { tree_type::init_node(value);   }
 
2163
 
 
2164
   //! <b>Effects</b>: Unlinks the leftmost node from the tree.
 
2165
   //! 
 
2166
   //! <b>Complexity</b>: Average complexity is constant time.
 
2167
   //! 
 
2168
   //! <b>Throws</b>: Nothing.
 
2169
   //! 
 
2170
   //! <b>Notes</b>: This function breaks the tree and the tree can
 
2171
   //!   only be used for more unlink_leftmost_without_rebalance calls.
 
2172
   //!   This function is normally used to achieve a step by step
 
2173
   //!   controlled destruction of the tree.
 
2174
   pointer unlink_leftmost_without_rebalance()
 
2175
   {  return tree_.unlink_leftmost_without_rebalance();  }
 
2176
 
 
2177
   //! <b>Requires</b>: replace_this must be a valid iterator of *this
 
2178
   //!   and with_this must not be inserted in any tree.
 
2179
   //! 
 
2180
   //! <b>Effects</b>: Replaces replace_this in its position in the
 
2181
   //!   tree with with_this. The tree does not need to be rebalanced.
 
2182
   //! 
 
2183
   //! <b>Complexity</b>: Constant. 
 
2184
   //! 
 
2185
   //! <b>Throws</b>: Nothing.
 
2186
   //! 
 
2187
   //! <b>Note</b>: This function will break container ordering invariants if
 
2188
   //!   with_this is not equivalent to *replace_this according to the
 
2189
   //!   ordering rules. This function is faster than erasing and inserting
 
2190
   //!   the node, since no rebalancing or comparison is needed.
 
2191
   void replace_node(iterator replace_this, reference with_this)
 
2192
   {  tree_.replace_node(replace_this, with_this);   }
 
2193
 
 
2194
   //! <b>Effects</b>: Rebalances the tree.
 
2195
   //! 
 
2196
   //! <b>Throws</b>: Nothing.
 
2197
   //! 
 
2198
   //! <b>Complexity</b>: Linear.
 
2199
   void rebalance()
 
2200
   {  tree_.rebalance(); }
 
2201
 
 
2202
   //! <b>Requires</b>: old_root is a node of a tree.
 
2203
   //! 
 
2204
   //! <b>Effects</b>: Rebalances the subtree rooted at old_root.
 
2205
   //!
 
2206
   //! <b>Returns</b>: The new root of the subtree.
 
2207
   //!
 
2208
   //! <b>Throws</b>: Nothing.
 
2209
   //! 
 
2210
   //! <b>Complexity</b>: Linear to the elements in the subtree.
 
2211
   iterator rebalance_subtree(iterator root)
 
2212
   {  return tree_.rebalance_subtree(root); }
 
2213
 
 
2214
   //! <b>Returns</b>: The balance factor (alpha) used in this tree
 
2215
   //!
 
2216
   //! <b>Throws</b>: Nothing.
 
2217
   //! 
 
2218
   //! <b>Complexity</b>: Constant.
 
2219
   float balance_factor() const
 
2220
   {  return tree_.balance_factor(); }
 
2221
 
 
2222
   //! <b>Requires</b>: new_alpha must be a value between 0.5 and 1.0
 
2223
   //! 
 
2224
   //! <b>Effects</b>: Establishes a new balance factor (alpha) and rebalances
 
2225
   //!   the tree if the new balance factor is stricter (less) than the old factor.
 
2226
   //!
 
2227
   //! <b>Throws</b>: Nothing.
 
2228
   //! 
 
2229
   //! <b>Complexity</b>: Linear to the elements in the subtree.
 
2230
   void balance_factor(float new_alpha)
 
2231
   {  tree_.balance_factor(new_alpha); }
 
2232
 
 
2233
   /// @cond
 
2234
   friend bool operator==(const sg_multiset_impl &x, const sg_multiset_impl &y)
 
2235
   {  return x.tree_ == y.tree_;  }
 
2236
 
 
2237
   friend bool operator<(const sg_multiset_impl &x, const sg_multiset_impl &y)
 
2238
   {  return x.tree_ < y.tree_;  }
 
2239
   /// @endcond
 
2240
};
 
2241
 
 
2242
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
2243
template<class T, class ...Options>
 
2244
#else
 
2245
template<class Config>
 
2246
#endif
 
2247
inline bool operator!=
 
2248
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
2249
(const sg_multiset_impl<T, Options...> &x, const sg_multiset_impl<T, Options...> &y)
 
2250
#else
 
2251
(const sg_multiset_impl<Config> &x, const sg_multiset_impl<Config> &y)
 
2252
#endif
 
2253
{  return !(x == y); }
 
2254
 
 
2255
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
2256
template<class T, class ...Options>
 
2257
#else
 
2258
template<class Config>
 
2259
#endif
 
2260
inline bool operator>
 
2261
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
2262
(const sg_multiset_impl<T, Options...> &x, const sg_multiset_impl<T, Options...> &y)
 
2263
#else
 
2264
(const sg_multiset_impl<Config> &x, const sg_multiset_impl<Config> &y)
 
2265
#endif
 
2266
{  return y < x;  }
 
2267
 
 
2268
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
2269
template<class T, class ...Options>
 
2270
#else
 
2271
template<class Config>
 
2272
#endif
 
2273
inline bool operator<=
 
2274
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
2275
(const sg_multiset_impl<T, Options...> &x, const sg_multiset_impl<T, Options...> &y)
 
2276
#else
 
2277
(const sg_multiset_impl<Config> &x, const sg_multiset_impl<Config> &y)
 
2278
#endif
 
2279
{  return !(y < x);  }
 
2280
 
 
2281
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
2282
template<class T, class ...Options>
 
2283
#else
 
2284
template<class Config>
 
2285
#endif
 
2286
inline bool operator>=
 
2287
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
2288
(const sg_multiset_impl<T, Options...> &x, const sg_multiset_impl<T, Options...> &y)
 
2289
#else
 
2290
(const sg_multiset_impl<Config> &x, const sg_multiset_impl<Config> &y)
 
2291
#endif
 
2292
{  return !(x < y);  }
 
2293
 
 
2294
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
2295
template<class T, class ...Options>
 
2296
#else
 
2297
template<class Config>
 
2298
#endif
 
2299
inline void swap
 
2300
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 
2301
(sg_multiset_impl<T, Options...> &x, sg_multiset_impl<T, Options...> &y)
 
2302
#else
 
2303
(sg_multiset_impl<Config> &x, sg_multiset_impl<Config> &y)
 
2304
#endif
 
2305
{  x.swap(y);  }
 
2306
 
 
2307
//! Helper metafunction to define a \c sg_multiset that yields to the same type when the
 
2308
//! same options (either explicitly or implicitly) are used.
 
2309
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 
2310
template<class T, class ...Options>
 
2311
#else
 
2312
template<class T, class O1 = none, class O2 = none
 
2313
                , class O3 = none, class O4 = none>
 
2314
#endif
 
2315
struct make_sg_multiset
 
2316
{
 
2317
   /// @cond
 
2318
   typedef sg_multiset_impl
 
2319
      < typename make_sgtree_opt<T, 
 
2320
         #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 
2321
         O1, O2, O3, O4
 
2322
         #else
 
2323
         Options...
 
2324
         #endif
 
2325
         >::type
 
2326
      > implementation_defined;
 
2327
   /// @endcond
 
2328
   typedef implementation_defined type;
 
2329
};
 
2330
 
 
2331
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 
2332
 
 
2333
#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 
2334
template<class T, class O1, class O2, class O3, class O4>
 
2335
#else
 
2336
template<class T, class ...Options>
 
2337
#endif
 
2338
class sg_multiset
 
2339
   :  public make_sg_multiset<T, 
 
2340
      #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 
2341
      O1, O2, O3, O4
 
2342
      #else
 
2343
      Options...
 
2344
      #endif
 
2345
      >::type
 
2346
{
 
2347
   typedef typename make_sg_multiset
 
2348
      <T, 
 
2349
      #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 
2350
      O1, O2, O3, O4
 
2351
      #else
 
2352
      Options...
 
2353
      #endif
 
2354
      >::type   Base;
 
2355
 
 
2356
   public:
 
2357
   typedef typename Base::value_compare      value_compare;
 
2358
   typedef typename Base::value_traits       value_traits;
 
2359
   typedef typename Base::iterator           iterator;
 
2360
   typedef typename Base::const_iterator     const_iterator;
 
2361
 
 
2362
   //Assert if passed value traits are compatible with the type
 
2363
   BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
 
2364
 
 
2365
   sg_multiset( const value_compare &cmp = value_compare()
 
2366
           , const value_traits &v_traits = value_traits())
 
2367
      :  Base(cmp, v_traits)
 
2368
   {}
 
2369
 
 
2370
   template<class Iterator>
 
2371
   sg_multiset( Iterator b, Iterator e
 
2372
           , const value_compare &cmp = value_compare()
 
2373
           , const value_traits &v_traits = value_traits())
 
2374
      :  Base(b, e, cmp, v_traits)
 
2375
   {}
 
2376
 
 
2377
   static sg_multiset &container_from_end_iterator(iterator end_iterator)
 
2378
   {  return static_cast<sg_multiset &>(Base::container_from_end_iterator(end_iterator));   }
 
2379
 
 
2380
   static const sg_multiset &container_from_end_iterator(const_iterator end_iterator)
 
2381
   {  return static_cast<const sg_multiset &>(Base::container_from_end_iterator(end_iterator));   }
 
2382
 
 
2383
   static sg_multiset &container_from_iterator(iterator it)
 
2384
   {  return static_cast<sg_multiset &>(Base::container_from_iterator(it));   }
 
2385
 
 
2386
   static const sg_multiset &container_from_iterator(const_iterator it)
 
2387
   {  return static_cast<const sg_multiset &>(Base::container_from_iterator(it));   }
 
2388
};
 
2389
 
 
2390
#endif
 
2391
 
 
2392
} //namespace intrusive 
 
2393
} //namespace boost 
 
2394
 
 
2395
#include <boost/intrusive/detail/config_end.hpp>
 
2396
 
 
2397
#endif //BOOST_INTRUSIVE_SG_SET_HPP