Mercurial > hg > vamp-build-and-test

comparison DEPENDENCIES/generic/include/boost/container/flat_set.hpp @ 101:c530137014c0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update Boost headers (1.58.0)
author Chris Cannam
date Mon, 07 Sep 2015 11:12:49 +0100
parents 2665513ce2d3
children
comparison
equal deleted inserted replaced
100:793467b5e61c 101:c530137014c0
1 ////////////////////////////////////////////////////////////////////////////// 1 //////////////////////////////////////////////////////////////////////////////
2 // 2 //
3 // (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost 3 // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost
4 // Software License, Version 1.0. (See accompanying file 4 // Software License, Version 1.0. (See accompanying file
5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 // 6 //
7 // See http://www.boost.org/libs/container for documentation. 7 // See http://www.boost.org/libs/container for documentation.
8 // 8 //
9 ////////////////////////////////////////////////////////////////////////////// 9 //////////////////////////////////////////////////////////////////////////////
10
11 #ifndef BOOST_CONTAINER_FLAT_SET_HPP 10 #ifndef BOOST_CONTAINER_FLAT_SET_HPP
12 #define BOOST_CONTAINER_FLAT_SET_HPP 11 #define BOOST_CONTAINER_FLAT_SET_HPP
13 12
14 #if defined(_MSC_VER) 13 #ifndef BOOST_CONFIG_HPP
14 # include <boost/config.hpp>
15 #endif
16
17 #if defined(BOOST_HAS_PRAGMA_ONCE)
15 # pragma once 18 # pragma once
16 #endif 19 #endif
17 20
18 #include <boost/container/detail/config_begin.hpp> 21 #include <boost/container/detail/config_begin.hpp>
19 #include <boost/container/detail/workaround.hpp> 22 #include <boost/container/detail/workaround.hpp>
20 23
24 // container
25 #include <boost/container/allocator_traits.hpp>
21 #include <boost/container/container_fwd.hpp> 26 #include <boost/container/container_fwd.hpp>
22 #include <utility> 27 #include <boost/container/new_allocator.hpp> //new_allocator
23 #include <functional> 28 // container/detail
24 #include <memory>
25 #include <boost/container/detail/flat_tree.hpp> 29 #include <boost/container/detail/flat_tree.hpp>
26 #include <boost/container/detail/mpl.hpp> 30 #include <boost/container/detail/mpl.hpp>
27 #include <boost/container/allocator_traits.hpp> 31 // move
28 #include <boost/move/utility.hpp> 32 #include <boost/move/traits.hpp>
33 #include <boost/move/utility_core.hpp>
34 // move/detail
35 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
36 #include <boost/move/detail/fwd_macros.hpp>
37 #endif
29 #include <boost/move/detail/move_helpers.hpp> 38 #include <boost/move/detail/move_helpers.hpp>
39 // intrusive/detail
40 #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
41 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal
42 // std
43 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
44 #include <initializer_list>
45 #endif
30 46
31 namespace boost { 47 namespace boost {
32 namespace container { 48 namespace container {
33
34 /// @cond
35 // Forward declarations of operators < and ==, needed for friend declaration.
36
37 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
38 template <class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key> >
39 #else
40 template <class Key, class Compare, class Allocator>
41 #endif
42 class flat_set;
43
44 template <class Key, class Compare, class Allocator>
45 inline bool operator==(const flat_set<Key,Compare,Allocator>& x,
46 const flat_set<Key,Compare,Allocator>& y);
47
48 template <class Key, class Compare, class Allocator>
49 inline bool operator<(const flat_set<Key,Compare,Allocator>& x,
50 const flat_set<Key,Compare,Allocator>& y);
51 /// @endcond
52 49
53 //! flat_set is a Sorted Associative Container that stores objects of type Key. 50 //! flat_set is a Sorted Associative Container that stores objects of type Key.
54 //! It is also a Unique Associative Container, meaning that no two elements are the same. 51 //! It is also a Unique Associative Container, meaning that no two elements are the same.
55 //! 52 //!
56 //! flat_set is similar to std::set but it's implemented like an ordered vector. 53 //! flat_set is similar to std::set but it's implemented like an ordered vector.
59 //! 56 //!
60 //! Erasing an element of a flat_set invalidates iterators and references 57 //! Erasing an element of a flat_set invalidates iterators and references
61 //! pointing to elements that come after (their keys are bigger) the erased element. 58 //! pointing to elements that come after (their keys are bigger) the erased element.
62 //! 59 //!
63 //! This container provides random-access iterators. 60 //! This container provides random-access iterators.
61 //!
62 //! \tparam Key is the type to be inserted in the set, which is also the key_type
63 //! \tparam Compare is the comparison functor used to order keys
64 //! \tparam Allocator is the allocator to be used to allocate memory for this container
64 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED 65 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
65 template <class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key> > 66 template <class Key, class Compare = std::less<Key>, class Allocator = new_allocator<Key> >
66 #else 67 #else
67 template <class Key, class Compare, class Allocator> 68 template <class Key, class Compare, class Allocator>
68 #endif 69 #endif
69 class flat_set 70 class flat_set
71 ///@cond
72 : public container_detail::flat_tree<Key, Key, container_detail::identity<Key>, Compare, Allocator>
73 ///@endcond
70 { 74 {
71 /// @cond 75 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
72 private: 76 private:
73 BOOST_COPYABLE_AND_MOVABLE(flat_set) 77 BOOST_COPYABLE_AND_MOVABLE(flat_set)
74 typedef container_detail::flat_tree<Key, Key, container_detail::identity<Key>, Compare, Allocator> tree_t; 78 typedef container_detail::flat_tree<Key, Key, container_detail::identity<Key>, Compare, Allocator> base_t;
75 tree_t m_flat_tree; // flat tree representing flat_set 79 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
76 /// @endcond
77 80
78 public: 81 public:
79 ////////////////////////////////////////////// 82 //////////////////////////////////////////////
80 // 83 //
81 // types 84 // types
83 ////////////////////////////////////////////// 86 //////////////////////////////////////////////
84 typedef Key key_type; 87 typedef Key key_type;
85 typedef Key value_type; 88 typedef Key value_type;
86 typedef Compare key_compare; 89 typedef Compare key_compare;
87 typedef Compare value_compare; 90 typedef Compare value_compare;
91 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
88 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; 92 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
89 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer; 93 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
90 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference; 94 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference;
91 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference; 95 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference;
92 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type; 96 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type;
93 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type; 97 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
94 typedef Allocator allocator_type; 98 typedef Allocator allocator_type;
95 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type; 99 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type;
96 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::iterator) iterator; 100 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator;
97 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_iterator) const_iterator; 101 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator;
98 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator) reverse_iterator; 102 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator;
99 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator) const_reverse_iterator; 103 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator;
100 104
101 public: 105 public:
102 ////////////////////////////////////////////// 106 //////////////////////////////////////////////
103 // 107 //
104 // construct/copy/destroy 108 // construct/copy/destroy
105 // 109 //
106 ////////////////////////////////////////////// 110 //////////////////////////////////////////////
107 111
108 //! <b>Effects</b>: Default constructs an empty flat_set. 112 //! <b>Effects</b>: Default constructs an empty container.
109 //! 113 //!
110 //! <b>Complexity</b>: Constant. 114 //! <b>Complexity</b>: Constant.
111 explicit flat_set() 115 explicit flat_set()
112 : m_flat_tree() 116 : base_t()
113 {} 117 {}
114 118
115 //! <b>Effects</b>: Constructs an empty flat_set using the specified 119 //! <b>Effects</b>: Constructs an empty container using the specified
116 //! comparison object and allocator. 120 //! comparison object and allocator.
117 //! 121 //!
118 //! <b>Complexity</b>: Constant. 122 //! <b>Complexity</b>: Constant.
119 explicit flat_set(const Compare& comp, 123 explicit flat_set(const Compare& comp,
120 const allocator_type& a = allocator_type()) 124 const allocator_type& a = allocator_type())
121 : m_flat_tree(comp, a) 125 : base_t(comp, a)
122 {} 126 {}
123 127
124 //! <b>Effects</b>: Constructs an empty flat_set using the specified allocator. 128 //! <b>Effects</b>: Constructs an empty container using the specified allocator.
125 //! 129 //!
126 //! <b>Complexity</b>: Constant. 130 //! <b>Complexity</b>: Constant.
127 explicit flat_set(const allocator_type& a) 131 explicit flat_set(const allocator_type& a)
128 : m_flat_tree(a) 132 : base_t(a)
129 {} 133 {}
130 134
131 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and 135 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
132 //! allocator, and inserts elements from the range [first ,last ). 136 //! allocator, and inserts elements from the range [first ,last ).
133 //! 137 //!
134 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using 138 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
135 //! comp and otherwise N logN, where N is last - first. 139 //! comp and otherwise N logN, where N is last - first.
136 template <class InputIterator> 140 template <class InputIterator>
137 flat_set(InputIterator first, InputIterator last, 141 flat_set(InputIterator first, InputIterator last,
138 const Compare& comp = Compare(), 142 const Compare& comp = Compare(),
139 const allocator_type& a = allocator_type()) 143 const allocator_type& a = allocator_type())
140 : m_flat_tree(true, first, last, comp, a) 144 : base_t(true, first, last, comp, a)
141 {} 145 {}
142 146
143 //! <b>Effects</b>: Constructs an empty flat_set using the specified comparison object and 147 //! <b>Effects</b>: Constructs an empty container using the specified
148 //! allocator, and inserts elements from the range [first ,last ).
149 //!
150 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
151 //! comp and otherwise N logN, where N is last - first.
152 template <class InputIterator>
153 flat_set(InputIterator first, InputIterator last, const allocator_type& a)
154 : base_t(true, first, last, Compare(), a)
155 {}
156
157 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
144 //! allocator, and inserts elements from the ordered unique range [first ,last). This function 158 //! allocator, and inserts elements from the ordered unique range [first ,last). This function
145 //! is more efficient than the normal range creation for ordered ranges. 159 //! is more efficient than the normal range creation for ordered ranges.
146 //! 160 //!
147 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be 161 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
148 //! unique values. 162 //! unique values.
152 //! <b>Note</b>: Non-standard extension. 166 //! <b>Note</b>: Non-standard extension.
153 template <class InputIterator> 167 template <class InputIterator>
154 flat_set(ordered_unique_range_t, InputIterator first, InputIterator last, 168 flat_set(ordered_unique_range_t, InputIterator first, InputIterator last,
155 const Compare& comp = Compare(), 169 const Compare& comp = Compare(),
156 const allocator_type& a = allocator_type()) 170 const allocator_type& a = allocator_type())
157 : m_flat_tree(ordered_range, first, last, comp, a) 171 : base_t(ordered_range, first, last, comp, a)
158 {} 172 {}
159 173
160 //! <b>Effects</b>: Copy constructs a set. 174 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
175 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
176 //! allocator, and inserts elements from the range [il.begin(), il.end()).
177 //!
178 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
179 //! comp and otherwise N logN, where N is il.begin() - il.end().
180 flat_set(std::initializer_list<value_type> il, const Compare& comp = Compare(),
181 const allocator_type& a = allocator_type())
182 : base_t(true, il.begin(), il.end(), comp, a)
183 {}
184
185 //! <b>Effects</b>: Constructs an empty container using the specified
186 //! allocator, and inserts elements from the range [il.begin(), il.end()).
187 //!
188 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
189 //! comp and otherwise N logN, where N is il.begin() - il.end().
190 flat_set(std::initializer_list<value_type> il, const allocator_type& a)
191 : base_t(true, il.begin(), il.end(), Compare(), a)
192 {}
193
194 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
195 //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function
196 //! is more efficient than the normal range creation for ordered ranges.
197 //!
198 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
199 //! unique values.
200 //!
201 //! <b>Complexity</b>: Linear in N.
202 //!
203 //! <b>Note</b>: Non-standard extension.
204 flat_set(ordered_unique_range_t, std::initializer_list<value_type> il,
205 const Compare& comp = Compare(), const allocator_type& a = allocator_type())
206 : base_t(ordered_range, il.begin(), il.end(), comp, a)
207 {}
208 #endif
209
210 //! <b>Effects</b>: Copy constructs the container.
161 //! 211 //!
162 //! <b>Complexity</b>: Linear in x.size(). 212 //! <b>Complexity</b>: Linear in x.size().
163 flat_set(const flat_set& x) 213 flat_set(const flat_set& x)
164 : m_flat_tree(x.m_flat_tree) 214 : base_t(static_cast<const base_t&>(x))
165 {} 215 {}
166 216
167 //! <b>Effects</b>: Move constructs a set. Constructs *this using x's resources. 217 //! <b>Effects</b>: Move constructs thecontainer. Constructs *this using x's resources.
168 //! 218 //!
169 //! <b>Complexity</b>: Constant. 219 //! <b>Complexity</b>: Constant.
170 //! 220 //!
171 //! <b>Postcondition</b>: x is emptied. 221 //! <b>Postcondition</b>: x is emptied.
172 flat_set(BOOST_RV_REF(flat_set) mx) 222 flat_set(BOOST_RV_REF(flat_set) x)
173 : m_flat_tree(boost::move(mx.m_flat_tree)) 223 : base_t(BOOST_MOVE_BASE(base_t, x))
174 {} 224 {}
175 225
176 //! <b>Effects</b>: Copy constructs a set using the specified allocator. 226 //! <b>Effects</b>: Copy constructs a container using the specified allocator.
177 //! 227 //!
178 //! <b>Complexity</b>: Linear in x.size(). 228 //! <b>Complexity</b>: Linear in x.size().
179 flat_set(const flat_set& x, const allocator_type &a) 229 flat_set(const flat_set& x, const allocator_type &a)
180 : m_flat_tree(x.m_flat_tree, a) 230 : base_t(static_cast<const base_t&>(x), a)
181 {} 231 {}
182 232
183 //! <b>Effects</b>: Move constructs a set using the specified allocator. 233 //! <b>Effects</b>: Move constructs a container using the specified allocator.
184 //! Constructs *this using x's resources. 234 //! Constructs *this using x's resources.
185 //! 235 //!
186 //! <b>Complexity</b>: Constant if a == mx.get_allocator(), linear otherwise 236 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise
187 flat_set(BOOST_RV_REF(flat_set) mx, const allocator_type &a) 237 flat_set(BOOST_RV_REF(flat_set) x, const allocator_type &a)
188 : m_flat_tree(boost::move(mx.m_flat_tree), a) 238 : base_t(BOOST_MOVE_BASE(base_t, x), a)
189 {} 239 {}
190 240
191 //! <b>Effects</b>: Makes *this a copy of x. 241 //! <b>Effects</b>: Makes *this a copy of x.
192 //! 242 //!
193 //! <b>Complexity</b>: Linear in x.size(). 243 //! <b>Complexity</b>: Linear in x.size().
194 flat_set& operator=(BOOST_COPY_ASSIGN_REF(flat_set) x) 244 flat_set& operator=(BOOST_COPY_ASSIGN_REF(flat_set) x)
195 { m_flat_tree = x.m_flat_tree; return *this; } 245 { return static_cast<flat_set&>(this->base_t::operator=(static_cast<const base_t&>(x))); }
196 246
197 //! <b>Effects</b>: Makes *this a copy of the previous value of xx. 247 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
198 //! 248 //! is false and (allocation throws or value_type's move constructor throws)
199 //! <b>Complexity</b>: Linear in x.size(). 249 //!
200 flat_set& operator=(BOOST_RV_REF(flat_set) mx) 250 //! <b>Complexity</b>: Constant if allocator_traits_type::
201 { m_flat_tree = boost::move(mx.m_flat_tree); return *this; } 251 //! propagate_on_container_move_assignment is true or
202 252 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
203 //! <b>Effects</b>: Returns a copy of the Allocator that 253 flat_set& operator=(BOOST_RV_REF(flat_set) x)
254 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
255 && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value )
256 { return static_cast<flat_set&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); }
257
258 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
259 //! <b>Effects</b>: Copy all elements from il to *this.
260 //!
261 //! <b>Complexity</b>: Linear in il.size().
262 flat_set& operator=(std::initializer_list<value_type> il)
263 {
264 this->clear();
265 this->insert(il.begin(), il.end());
266 return *this;
267 }
268 #endif
269
270 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
271 //! <b>Effects</b>: Returns a copy of the allocator that
204 //! was passed to the object's constructor. 272 //! was passed to the object's constructor.
205 //! 273 //!
206 //! <b>Complexity</b>: Constant. 274 //! <b>Complexity</b>: Constant.
207 allocator_type get_allocator() const BOOST_CONTAINER_NOEXCEPT 275 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW;
208 { return m_flat_tree.get_allocator(); }
209 276
210 //! <b>Effects</b>: Returns a reference to the internal allocator. 277 //! <b>Effects</b>: Returns a reference to the internal allocator.
211 //! 278 //!
212 //! <b>Throws</b>: Nothing 279 //! <b>Throws</b>: Nothing
213 //! 280 //!
214 //! <b>Complexity</b>: Constant. 281 //! <b>Complexity</b>: Constant.
215 //! 282 //!
216 //! <b>Note</b>: Non-standard extension. 283 //! <b>Note</b>: Non-standard extension.
217 stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT 284 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW;
218 { return m_flat_tree.get_stored_allocator(); }
219 285
220 //! <b>Effects</b>: Returns a reference to the internal allocator. 286 //! <b>Effects</b>: Returns a reference to the internal allocator.
221 //! 287 //!
222 //! <b>Throws</b>: Nothing 288 //! <b>Throws</b>: Nothing
223 //! 289 //!
224 //! <b>Complexity</b>: Constant. 290 //! <b>Complexity</b>: Constant.
225 //! 291 //!
226 //! <b>Note</b>: Non-standard extension. 292 //! <b>Note</b>: Non-standard extension.
227 const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT 293 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW;
228 { return m_flat_tree.get_stored_allocator(); }
229
230 //////////////////////////////////////////////
231 //
232 // iterators
233 //
234 //////////////////////////////////////////////
235 294
236 //! <b>Effects</b>: Returns an iterator to the first element contained in the container. 295 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
237 //! 296 //!
238 //! <b>Throws</b>: Nothing. 297 //! <b>Throws</b>: Nothing.
239 //! 298 //!
240 //! <b>Complexity</b>: Constant. 299 //! <b>Complexity</b>: Constant.
241 iterator begin() BOOST_CONTAINER_NOEXCEPT 300 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW;
242 { return m_flat_tree.begin(); }
243 301
244 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. 302 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
245 //! 303 //!
246 //! <b>Throws</b>: Nothing. 304 //! <b>Throws</b>: Nothing.
247 //! 305 //!
248 //! <b>Complexity</b>: Constant. 306 //! <b>Complexity</b>: Constant.
249 const_iterator begin() const BOOST_CONTAINER_NOEXCEPT 307 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW;
250 { return m_flat_tree.begin(); }
251 308
252 //! <b>Effects</b>: Returns an iterator to the end of the container. 309 //! <b>Effects</b>: Returns an iterator to the end of the container.
253 //! 310 //!
254 //! <b>Throws</b>: Nothing. 311 //! <b>Throws</b>: Nothing.
255 //! 312 //!
256 //! <b>Complexity</b>: Constant. 313 //! <b>Complexity</b>: Constant.
257 iterator end() BOOST_CONTAINER_NOEXCEPT 314 iterator end() BOOST_NOEXCEPT_OR_NOTHROW;
258 { return m_flat_tree.end(); }
259 315
260 //! <b>Effects</b>: Returns a const_iterator to the end of the container. 316 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
261 //! 317 //!
262 //! <b>Throws</b>: Nothing. 318 //! <b>Throws</b>: Nothing.
263 //! 319 //!
264 //! <b>Complexity</b>: Constant. 320 //! <b>Complexity</b>: Constant.
265 const_iterator end() const BOOST_CONTAINER_NOEXCEPT 321 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW;
266 { return m_flat_tree.end(); }
267 322
268 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning 323 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
269 //! of the reversed container. 324 //! of the reversed container.
270 //! 325 //!
271 //! <b>Throws</b>: Nothing. 326 //! <b>Throws</b>: Nothing.
272 //! 327 //!
273 //! <b>Complexity</b>: Constant. 328 //! <b>Complexity</b>: Constant.
274 reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT 329 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW;
275 { return m_flat_tree.rbegin(); }
276 330
277 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 331 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
278 //! of the reversed container. 332 //! of the reversed container.
279 //! 333 //!
280 //! <b>Throws</b>: Nothing. 334 //! <b>Throws</b>: Nothing.
281 //! 335 //!
282 //! <b>Complexity</b>: Constant. 336 //! <b>Complexity</b>: Constant.
283 const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT 337 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
284 { return m_flat_tree.rbegin(); }
285 338
286 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end 339 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
287 //! of the reversed container. 340 //! of the reversed container.
288 //! 341 //!
289 //! <b>Throws</b>: Nothing. 342 //! <b>Throws</b>: Nothing.
290 //! 343 //!
291 //! <b>Complexity</b>: Constant. 344 //! <b>Complexity</b>: Constant.
292 reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT 345 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW;
293 { return m_flat_tree.rend(); }
294 346
295 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 347 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
296 //! of the reversed container. 348 //! of the reversed container.
297 //! 349 //!
298 //! <b>Throws</b>: Nothing. 350 //! <b>Throws</b>: Nothing.
299 //! 351 //!
300 //! <b>Complexity</b>: Constant. 352 //! <b>Complexity</b>: Constant.
301 const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT 353 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW;
302 { return m_flat_tree.rend(); }
303 354
304 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. 355 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
305 //! 356 //!
306 //! <b>Throws</b>: Nothing. 357 //! <b>Throws</b>: Nothing.
307 //! 358 //!
308 //! <b>Complexity</b>: Constant. 359 //! <b>Complexity</b>: Constant.
309 const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT 360 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
310 { return m_flat_tree.cbegin(); }
311 361
312 //! <b>Effects</b>: Returns a const_iterator to the end of the container. 362 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
313 //! 363 //!
314 //! <b>Throws</b>: Nothing. 364 //! <b>Throws</b>: Nothing.
315 //! 365 //!
316 //! <b>Complexity</b>: Constant. 366 //! <b>Complexity</b>: Constant.
317 const_iterator cend() const BOOST_CONTAINER_NOEXCEPT 367 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW;
318 { return m_flat_tree.cend(); }
319 368
320 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 369 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
321 //! of the reversed container. 370 //! of the reversed container.
322 //! 371 //!
323 //! <b>Throws</b>: Nothing. 372 //! <b>Throws</b>: Nothing.
324 //! 373 //!
325 //! <b>Complexity</b>: Constant. 374 //! <b>Complexity</b>: Constant.
326 const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT 375 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
327 { return m_flat_tree.crbegin(); }
328 376
329 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 377 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
330 //! of the reversed container. 378 //! of the reversed container.
331 //! 379 //!
332 //! <b>Throws</b>: Nothing. 380 //! <b>Throws</b>: Nothing.
333 //! 381 //!
334 //! <b>Complexity</b>: Constant. 382 //! <b>Complexity</b>: Constant.
335 const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT 383 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW;
336 { return m_flat_tree.crend(); }
337
338
339 //////////////////////////////////////////////
340 //
341 // capacity
342 //
343 //////////////////////////////////////////////
344 384
345 //! <b>Effects</b>: Returns true if the container contains no elements. 385 //! <b>Effects</b>: Returns true if the container contains no elements.
346 //! 386 //!
347 //! <b>Throws</b>: Nothing. 387 //! <b>Throws</b>: Nothing.
348 //! 388 //!
349 //! <b>Complexity</b>: Constant. 389 //! <b>Complexity</b>: Constant.
350 bool empty() const BOOST_CONTAINER_NOEXCEPT 390 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW;
351 { return m_flat_tree.empty(); }
352 391
353 //! <b>Effects</b>: Returns the number of the elements contained in the container. 392 //! <b>Effects</b>: Returns the number of the elements contained in the container.
354 //! 393 //!
355 //! <b>Throws</b>: Nothing. 394 //! <b>Throws</b>: Nothing.
356 //! 395 //!
357 //! <b>Complexity</b>: Constant. 396 //! <b>Complexity</b>: Constant.
358 size_type size() const BOOST_CONTAINER_NOEXCEPT 397 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW;
359 { return m_flat_tree.size(); }
360 398
361 //! <b>Effects</b>: Returns the largest possible size of the container. 399 //! <b>Effects</b>: Returns the largest possible size of the container.
362 //! 400 //!
363 //! <b>Throws</b>: Nothing. 401 //! <b>Throws</b>: Nothing.
364 //! 402 //!
365 //! <b>Complexity</b>: Constant. 403 //! <b>Complexity</b>: Constant.
366 size_type max_size() const BOOST_CONTAINER_NOEXCEPT 404 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW;
367 { return m_flat_tree.max_size(); }
368 405
369 //! <b>Effects</b>: Number of elements for which memory has been allocated. 406 //! <b>Effects</b>: Number of elements for which memory has been allocated.
370 //! capacity() is always greater than or equal to size(). 407 //! capacity() is always greater than or equal to size().
371 //! 408 //!
372 //! <b>Throws</b>: Nothing. 409 //! <b>Throws</b>: Nothing.
373 //! 410 //!
374 //! <b>Complexity</b>: Constant. 411 //! <b>Complexity</b>: Constant.
375 size_type capacity() const BOOST_CONTAINER_NOEXCEPT 412 size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW;
376 { return m_flat_tree.capacity(); }
377 413
378 //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no 414 //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no
379 //! effect. Otherwise, it is a request for allocation of additional memory. 415 //! effect. Otherwise, it is a request for allocation of additional memory.
380 //! If the request is successful, then capacity() is greater than or equal to 416 //! If the request is successful, then capacity() is greater than or equal to
381 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged. 417 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
382 //! 418 //!
383 //! <b>Throws</b>: If memory allocation allocation throws or Key's copy constructor throws. 419 //! <b>Throws</b>: If memory allocation allocation throws or Key's copy constructor throws.
384 //! 420 //!
385 //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to 421 //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to
386 //! to values might be invalidated. 422 //! to values might be invalidated.
387 void reserve(size_type cnt) 423 void reserve(size_type cnt);
388 { m_flat_tree.reserve(cnt); }
389 424
390 //! <b>Effects</b>: Tries to deallocate the excess of memory created 425 //! <b>Effects</b>: Tries to deallocate the excess of memory created
391 // with previous allocations. The size of the vector is unchanged 426 // with previous allocations. The size of the vector is unchanged
392 //! 427 //!
393 //! <b>Throws</b>: If memory allocation throws, or Key's copy constructor throws. 428 //! <b>Throws</b>: If memory allocation throws, or Key's copy constructor throws.
394 //! 429 //!
395 //! <b>Complexity</b>: Linear to size(). 430 //! <b>Complexity</b>: Linear to size().
396 void shrink_to_fit() 431 void shrink_to_fit();
397 { m_flat_tree.shrink_to_fit(); } 432
433 #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
398 434
399 ////////////////////////////////////////////// 435 //////////////////////////////////////////////
400 // 436 //
401 // modifiers 437 // modifiers
402 // 438 //
403 ////////////////////////////////////////////// 439 //////////////////////////////////////////////
404 440
405 #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 441 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
406 442
407 //! <b>Effects</b>: Inserts an object x of type Key constructed with 443 //! <b>Effects</b>: Inserts an object x of type Key constructed with
408 //! std::forward<Args>(args)... if and only if there is no element in the container 444 //! std::forward<Args>(args)... if and only if there is no element in the container
409 //! with key equivalent to the key of x. 445 //! with key equivalent to the key of x.
410 //! 446 //!
415 //! <b>Complexity</b>: Logarithmic search time plus linear insertion 451 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
416 //! to the elements with bigger keys than x. 452 //! to the elements with bigger keys than x.
417 //! 453 //!
418 //! <b>Note</b>: If an element is inserted it might invalidate elements. 454 //! <b>Note</b>: If an element is inserted it might invalidate elements.
419 template <class... Args> 455 template <class... Args>
420 std::pair<iterator,bool> emplace(Args&&... args) 456 std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args)
421 { return m_flat_tree.emplace_unique(boost::forward<Args>(args)...); } 457 { return this->base_t::emplace_unique(boost::forward<Args>(args)...); }
422 458
423 //! <b>Effects</b>: Inserts an object of type Key constructed with 459 //! <b>Effects</b>: Inserts an object of type Key constructed with
424 //! std::forward<Args>(args)... in the container if and only if there is 460 //! std::forward<Args>(args)... in the container if and only if there is
425 //! no element in the container with key equivalent to the key of x. 461 //! no element in the container with key equivalent to the key of x.
426 //! p is a hint pointing to where the insert should start to search. 462 //! p is a hint pointing to where the insert should start to search.
431 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted 467 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
432 //! right before p) plus insertion linear to the elements with bigger keys than x. 468 //! right before p) plus insertion linear to the elements with bigger keys than x.
433 //! 469 //!
434 //! <b>Note</b>: If an element is inserted it might invalidate elements. 470 //! <b>Note</b>: If an element is inserted it might invalidate elements.
435 template <class... Args> 471 template <class... Args>
436 iterator emplace_hint(const_iterator hint, Args&&... args) 472 iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args)
437 { return m_flat_tree.emplace_hint_unique(hint, boost::forward<Args>(args)...); } 473 { return this->base_t::emplace_hint_unique(p, boost::forward<Args>(args)...); }
438 474
439 #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING 475 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
440 476
441 #define BOOST_PP_LOCAL_MACRO(n) \ 477 #define BOOST_CONTAINER_FLAT_SET_EMPLACE_CODE(N) \
442 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ 478 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
443 std::pair<iterator,bool> emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ 479 std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\
444 { return m_flat_tree.emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \ 480 { return this->base_t::emplace_unique(BOOST_MOVE_FWD##N); }\
445 \ 481 \
446 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ 482 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
447 iterator emplace_hint(const_iterator hint \ 483 iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
448 BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ 484 { return this->base_t::emplace_hint_unique(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
449 { return m_flat_tree.emplace_hint_unique \ 485 //
450 (hint BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \ 486 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_SET_EMPLACE_CODE)
451 //! 487 #undef BOOST_CONTAINER_FLAT_SET_EMPLACE_CODE
452 #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) 488
453 #include BOOST_PP_LOCAL_ITERATE() 489 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
454
455 #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
456 490
457 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 491 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
458 //! <b>Effects</b>: Inserts x if and only if there is no element in the container 492 //! <b>Effects</b>: Inserts x if and only if there is no element in the container
459 //! with key equivalent to the key of x. 493 //! with key equivalent to the key of x.
460 //! 494 //!
508 //! 542 //!
509 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted 543 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
510 //! right before p) plus insertion linear to the elements with bigger keys than x. 544 //! right before p) plus insertion linear to the elements with bigger keys than x.
511 //! 545 //!
512 //! <b>Note</b>: If an element is inserted it might invalidate elements. 546 //! <b>Note</b>: If an element is inserted it might invalidate elements.
513 iterator insert(const_iterator position, value_type &&x); 547 iterator insert(const_iterator p, value_type &&x);
514 #else 548 #else
515 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator) 549 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator)
516 #endif 550 #endif
517 551
518 //! <b>Requires</b>: first, last are not iterators into *this. 552 //! <b>Requires</b>: first, last are not iterators into *this.
524 //! search time plus N*size() insertion time. 558 //! search time plus N*size() insertion time.
525 //! 559 //!
526 //! <b>Note</b>: If an element is inserted it might invalidate elements. 560 //! <b>Note</b>: If an element is inserted it might invalidate elements.
527 template <class InputIterator> 561 template <class InputIterator>
528 void insert(InputIterator first, InputIterator last) 562 void insert(InputIterator first, InputIterator last)
529 { m_flat_tree.insert_unique(first, last); } 563 { this->base_t::insert_unique(first, last); }
530 564
531 //! <b>Requires</b>: first, last are not iterators into *this and 565 //! <b>Requires</b>: first, last are not iterators into *this and
532 //! must be ordered according to the predicate and must be 566 //! must be ordered according to the predicate and must be
533 //! unique values. 567 //! unique values.
534 //! 568 //!
539 //! search time plus N*size() insertion time. 573 //! search time plus N*size() insertion time.
540 //! 574 //!
541 //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements. 575 //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements.
542 template <class InputIterator> 576 template <class InputIterator>
543 void insert(ordered_unique_range_t, InputIterator first, InputIterator last) 577 void insert(ordered_unique_range_t, InputIterator first, InputIterator last)
544 { m_flat_tree.insert_unique(ordered_unique_range, first, last); } 578 { this->base_t::insert_unique(ordered_unique_range, first, last); }
545 579
546 //! <b>Effects</b>: Erases the element pointed to by position. 580 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
581 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
582 //! if there is no element with key equivalent to the key of that element.
583 //!
584 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end())
585 //! search time plus N*size() insertion time.
586 //!
587 //! <b>Note</b>: If an element is inserted it might invalidate elements.
588 void insert(std::initializer_list<value_type> il)
589 { this->base_t::insert_unique(il.begin(), il.end()); }
590
591 //! <b>Requires</b>: Range [il.begin(), il.end()) must be ordered according to the predicate
592 //! and must be unique values.
593 //!
594 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) .This function
595 //! is more efficient than the normal range creation for ordered ranges.
596 //!
597 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end())
598 //! search time plus N*size() insertion time.
599 //!
600 //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements.
601 void insert(ordered_unique_range_t, std::initializer_list<value_type> il)
602 { this->base_t::insert_unique(ordered_unique_range, il.begin(), il.end()); }
603 #endif
604
605 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
606
607 //! <b>Effects</b>: Erases the element pointed to by p.
547 //! 608 //!
548 //! <b>Returns</b>: Returns an iterator pointing to the element immediately 609 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
549 //! following q prior to the element being erased. If no such element exists, 610 //! following q prior to the element being erased. If no such element exists,
550 //! returns end(). 611 //! returns end().
551 //! 612 //!
552 //! <b>Complexity</b>: Linear to the elements with keys bigger than position 613 //! <b>Complexity</b>: Linear to the elements with keys bigger than p
553 //! 614 //!
554 //! <b>Note</b>: Invalidates elements with keys 615 //! <b>Note</b>: Invalidates elements with keys
555 //! not less than the erased element. 616 //! not less than the erased element.
556 iterator erase(const_iterator position) 617 iterator erase(const_iterator p);
557 { return m_flat_tree.erase(position); }
558 618
559 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. 619 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
560 //! 620 //!
561 //! <b>Returns</b>: Returns the number of erased elements. 621 //! <b>Returns</b>: Returns the number of erased elements.
562 //! 622 //!
563 //! <b>Complexity</b>: Logarithmic search time plus erasure time 623 //! <b>Complexity</b>: Logarithmic search time plus erasure time
564 //! linear to the elements with bigger keys. 624 //! linear to the elements with bigger keys.
565 size_type erase(const key_type& x) 625 size_type erase(const key_type& x);
566 { return m_flat_tree.erase(x); }
567 626
568 //! <b>Effects</b>: Erases all the elements in the range [first, last). 627 //! <b>Effects</b>: Erases all the elements in the range [first, last).
569 //! 628 //!
570 //! <b>Returns</b>: Returns last. 629 //! <b>Returns</b>: Returns last.
571 //! 630 //!
572 //! <b>Complexity</b>: size()*N where N is the distance from first to last. 631 //! <b>Complexity</b>: size()*N where N is the distance from first to last.
573 //! 632 //!
574 //! <b>Complexity</b>: Logarithmic search time plus erasure time 633 //! <b>Complexity</b>: Logarithmic search time plus erasure time
575 //! linear to the elements with bigger keys. 634 //! linear to the elements with bigger keys.
576 iterator erase(const_iterator first, const_iterator last) 635 iterator erase(const_iterator first, const_iterator last);
577 { return m_flat_tree.erase(first, last); }
578 636
579 //! <b>Effects</b>: Swaps the contents of *this and x. 637 //! <b>Effects</b>: Swaps the contents of *this and x.
580 //! 638 //!
581 //! <b>Throws</b>: Nothing. 639 //! <b>Throws</b>: Nothing.
582 //! 640 //!
583 //! <b>Complexity</b>: Constant. 641 //! <b>Complexity</b>: Constant.
584 void swap(flat_set& x) 642 void swap(flat_set& x)
585 { m_flat_tree.swap(x.m_flat_tree); } 643 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
644 && boost::container::container_detail::is_nothrow_swappable<Compare>::value );
586 645
587 //! <b>Effects</b>: erase(a.begin(),a.end()). 646 //! <b>Effects</b>: erase(a.begin(),a.end()).
588 //! 647 //!
589 //! <b>Postcondition</b>: size() == 0. 648 //! <b>Postcondition</b>: size() == 0.
590 //! 649 //!
591 //! <b>Complexity</b>: linear in size(). 650 //! <b>Complexity</b>: linear in size().
592 void clear() BOOST_CONTAINER_NOEXCEPT 651 void clear() BOOST_NOEXCEPT_OR_NOTHROW;
593 { m_flat_tree.clear(); }
594
595 //////////////////////////////////////////////
596 //
597 // observers
598 //
599 //////////////////////////////////////////////
600 652
601 //! <b>Effects</b>: Returns the comparison object out 653 //! <b>Effects</b>: Returns the comparison object out
602 //! of which a was constructed. 654 //! of which a was constructed.
603 //! 655 //!
604 //! <b>Complexity</b>: Constant. 656 //! <b>Complexity</b>: Constant.
605 key_compare key_comp() const 657 key_compare key_comp() const;
606 { return m_flat_tree.key_comp(); }
607 658
608 //! <b>Effects</b>: Returns an object of value_compare constructed out 659 //! <b>Effects</b>: Returns an object of value_compare constructed out
609 //! of the comparison object. 660 //! of the comparison object.
610 //! 661 //!
611 //! <b>Complexity</b>: Constant. 662 //! <b>Complexity</b>: Constant.
612 value_compare value_comp() const 663 value_compare value_comp() const;
613 { return m_flat_tree.key_comp(); }
614
615 //////////////////////////////////////////////
616 //
617 // set operations
618 //
619 //////////////////////////////////////////////
620 664
621 //! <b>Returns</b>: An iterator pointing to an element with the key 665 //! <b>Returns</b>: An iterator pointing to an element with the key
622 //! equivalent to x, or end() if such an element is not found. 666 //! equivalent to x, or end() if such an element is not found.
623 //! 667 //!
624 //! <b>Complexity</b>: Logarithmic. 668 //! <b>Complexity</b>: Logarithmic.
625 iterator find(const key_type& x) 669 iterator find(const key_type& x);
626 { return m_flat_tree.find(x); } 670
627 671 //! <b>Returns</b>: A const_iterator pointing to an element with the key
628 //! <b>Returns</b>: Allocator const_iterator pointing to an element with the key
629 //! equivalent to x, or end() if such an element is not found. 672 //! equivalent to x, or end() if such an element is not found.
630 //! 673 //!
631 //! <b>Complexity</b>: Logarithmic.s 674 //! <b>Complexity</b>: Logarithmic.
632 const_iterator find(const key_type& x) const 675 const_iterator find(const key_type& x) const;
633 { return m_flat_tree.find(x); } 676
677 //! <b>Requires</b>: size() >= n.
678 //!
679 //! <b>Effects</b>: Returns an iterator to the nth element
680 //! from the beginning of the container. Returns end()
681 //! if n == size().
682 //!
683 //! <b>Throws</b>: Nothing.
684 //!
685 //! <b>Complexity</b>: Constant.
686 //!
687 //! <b>Note</b>: Non-standard extension
688 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW;
689
690 //! <b>Requires</b>: size() >= n.
691 //!
692 //! <b>Effects</b>: Returns a const_iterator to the nth element
693 //! from the beginning of the container. Returns end()
694 //! if n == size().
695 //!
696 //! <b>Throws</b>: Nothing.
697 //!
698 //! <b>Complexity</b>: Constant.
699 //!
700 //! <b>Note</b>: Non-standard extension
701 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW;
702
703 //! <b>Requires</b>: size() >= n.
704 //!
705 //! <b>Effects</b>: Returns an iterator to the nth element
706 //! from the beginning of the container. Returns end()
707 //! if n == size().
708 //!
709 //! <b>Throws</b>: Nothing.
710 //!
711 //! <b>Complexity</b>: Constant.
712 //!
713 //! <b>Note</b>: Non-standard extension
714 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW;
715
716 //! <b>Requires</b>: begin() <= p <= end().
717 //!
718 //! <b>Effects</b>: Returns the index of the element pointed by p
719 //! and size() if p == end().
720 //!
721 //! <b>Throws</b>: Nothing.
722 //!
723 //! <b>Complexity</b>: Constant.
724 //!
725 //! <b>Note</b>: Non-standard extension
726 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW;
727
728 #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
634 729
635 //! <b>Returns</b>: The number of elements with key equivalent to x. 730 //! <b>Returns</b>: The number of elements with key equivalent to x.
636 //! 731 //!
637 //! <b>Complexity</b>: log(size())+count(k) 732 //! <b>Complexity</b>: log(size())+count(k)
638 size_type count(const key_type& x) const 733 size_type count(const key_type& x) const
639 { return static_cast<size_type>(m_flat_tree.find(x) != m_flat_tree.end()); } 734 { return static_cast<size_type>(this->base_t::find(x) != this->base_t::cend()); }
640 735
736 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
641 //! <b>Returns</b>: An iterator pointing to the first element with key not less 737 //! <b>Returns</b>: An iterator pointing to the first element with key not less
642 //! than k, or a.end() if such an element is not found. 738 //! than k, or a.end() if such an element is not found.
643 //! 739 //!
644 //! <b>Complexity</b>: Logarithmic 740 //! <b>Complexity</b>: Logarithmic
645 iterator lower_bound(const key_type& x) 741 iterator lower_bound(const key_type& x);
646 { return m_flat_tree.lower_bound(x); } 742
647 743 //! <b>Returns</b>: A const iterator pointing to the first element with key not
648 //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
649 //! less than k, or a.end() if such an element is not found. 744 //! less than k, or a.end() if such an element is not found.
650 //! 745 //!
651 //! <b>Complexity</b>: Logarithmic 746 //! <b>Complexity</b>: Logarithmic
652 const_iterator lower_bound(const key_type& x) const 747 const_iterator lower_bound(const key_type& x) const;
653 { return m_flat_tree.lower_bound(x); }
654 748
655 //! <b>Returns</b>: An iterator pointing to the first element with key not less 749 //! <b>Returns</b>: An iterator pointing to the first element with key not less
656 //! than x, or end() if such an element is not found. 750 //! than x, or end() if such an element is not found.
657 //! 751 //!
658 //! <b>Complexity</b>: Logarithmic 752 //! <b>Complexity</b>: Logarithmic
659 iterator upper_bound(const key_type& x) 753 iterator upper_bound(const key_type& x);
660 { return m_flat_tree.upper_bound(x); } 754
661 755 //! <b>Returns</b>: A const iterator pointing to the first element with key not
662 //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
663 //! less than x, or end() if such an element is not found. 756 //! less than x, or end() if such an element is not found.
664 //! 757 //!
665 //! <b>Complexity</b>: Logarithmic 758 //! <b>Complexity</b>: Logarithmic
666 const_iterator upper_bound(const key_type& x) const 759 const_iterator upper_bound(const key_type& x) const;
667 { return m_flat_tree.upper_bound(x); } 760
761 #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
668 762
669 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 763 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
670 //! 764 //!
671 //! <b>Complexity</b>: Logarithmic 765 //! <b>Complexity</b>: Logarithmic
672 std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const 766 std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
673 { return m_flat_tree.equal_range(x); } 767 { return this->base_t::lower_bound_range(x); }
674 768
675 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 769 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
676 //! 770 //!
677 //! <b>Complexity</b>: Logarithmic 771 //! <b>Complexity</b>: Logarithmic
678 std::pair<iterator,iterator> equal_range(const key_type& x) 772 std::pair<iterator,iterator> equal_range(const key_type& x)
679 { return m_flat_tree.equal_range(x); } 773 { return this->base_t::lower_bound_range(x); }
680 774
681 /// @cond 775 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
682 template <class K1, class C1, class A1> 776
683 friend bool operator== (const flat_set<K1,C1,A1>&, const flat_set<K1,C1,A1>&); 777 //! <b>Effects</b>: Returns true if x and y are equal
684 778 //!
685 template <class K1, class C1, class A1> 779 //! <b>Complexity</b>: Linear to the number of elements in the container.
686 friend bool operator< (const flat_set<K1,C1,A1>&, const flat_set<K1,C1,A1>&); 780 friend bool operator==(const flat_set& x, const flat_set& y);
687 781
782 //! <b>Effects</b>: Returns true if x and y are unequal
783 //!
784 //! <b>Complexity</b>: Linear to the number of elements in the container.
785 friend bool operator!=(const flat_set& x, const flat_set& y);
786
787 //! <b>Effects</b>: Returns true if x is less than y
788 //!
789 //! <b>Complexity</b>: Linear to the number of elements in the container.
790 friend bool operator<(const flat_set& x, const flat_set& y);
791
792 //! <b>Effects</b>: Returns true if x is greater than y
793 //!
794 //! <b>Complexity</b>: Linear to the number of elements in the container.
795 friend bool operator>(const flat_set& x, const flat_set& y);
796
797 //! <b>Effects</b>: Returns true if x is equal or less than y
798 //!
799 //! <b>Complexity</b>: Linear to the number of elements in the container.
800 friend bool operator<=(const flat_set& x, const flat_set& y);
801
802 //! <b>Effects</b>: Returns true if x is equal or greater than y
803 //!
804 //! <b>Complexity</b>: Linear to the number of elements in the container.
805 friend bool operator>=(const flat_set& x, const flat_set& y);
806
807 //! <b>Effects</b>: x.swap(y)
808 //!
809 //! <b>Complexity</b>: Constant.
810 friend void swap(flat_set& x, flat_set& y);
811
812 #endif //#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
813
814 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
688 private: 815 private:
689 template<class KeyType> 816 template<class KeyType>
690 std::pair<iterator, bool> priv_insert(BOOST_FWD_REF(KeyType) x) 817 std::pair<iterator, bool> priv_insert(BOOST_FWD_REF(KeyType) x)
691 { return m_flat_tree.insert_unique(::boost::forward<KeyType>(x)); } 818 { return this->base_t::insert_unique(::boost::forward<KeyType>(x)); }
692 819
693 template<class KeyType> 820 template<class KeyType>
694 iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x) 821 iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x)
695 { return m_flat_tree.insert_unique(p, ::boost::forward<KeyType>(x)); } 822 { return this->base_t::insert_unique(p, ::boost::forward<KeyType>(x)); }
696 /// @endcond 823 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
697 }; 824 };
698 825
699 template <class Key, class Compare, class Allocator> 826 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
700 inline bool operator==(const flat_set<Key,Compare,Allocator>& x,
701 const flat_set<Key,Compare,Allocator>& y)
702 { return x.m_flat_tree == y.m_flat_tree; }
703
704 template <class Key, class Compare, class Allocator>
705 inline bool operator<(const flat_set<Key,Compare,Allocator>& x,
706 const flat_set<Key,Compare,Allocator>& y)
707 { return x.m_flat_tree < y.m_flat_tree; }
708
709 template <class Key, class Compare, class Allocator>
710 inline bool operator!=(const flat_set<Key,Compare,Allocator>& x,
711 const flat_set<Key,Compare,Allocator>& y)
712 { return !(x == y); }
713
714 template <class Key, class Compare, class Allocator>
715 inline bool operator>(const flat_set<Key,Compare,Allocator>& x,
716 const flat_set<Key,Compare,Allocator>& y)
717 { return y < x; }
718
719 template <class Key, class Compare, class Allocator>
720 inline bool operator<=(const flat_set<Key,Compare,Allocator>& x,
721 const flat_set<Key,Compare,Allocator>& y)
722 { return !(y < x); }
723
724 template <class Key, class Compare, class Allocator>
725 inline bool operator>=(const flat_set<Key,Compare,Allocator>& x,
726 const flat_set<Key,Compare,Allocator>& y)
727 { return !(x < y); }
728
729 template <class Key, class Compare, class Allocator>
730 inline void swap(flat_set<Key,Compare,Allocator>& x, flat_set<Key,Compare,Allocator>& y)
731 { x.swap(y); }
732
733 /// @cond
734 827
735 } //namespace container { 828 } //namespace container {
736 829
737 //!has_trivial_destructor_after_move<> == true_type 830 //!has_trivial_destructor_after_move<> == true_type
738 //!specialization for optimizations 831 //!specialization for optimizations
739 template <class Key, class C, class Allocator> 832 template <class Key, class Compare, class Allocator>
740 struct has_trivial_destructor_after_move<boost::container::flat_set<Key, C, Allocator> > 833 struct has_trivial_destructor_after_move<boost::container::flat_set<Key, Compare, Allocator> >
741 { 834 {
742 static const bool value = has_trivial_destructor_after_move<Allocator>::value &&has_trivial_destructor_after_move<C>::value; 835 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
836 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
837 ::boost::has_trivial_destructor_after_move<pointer>::value &&
838 ::boost::has_trivial_destructor_after_move<Compare>::value;
743 }; 839 };
744 840
745 namespace container { 841 namespace container {
746 842
747 // Forward declaration of operators < and ==, needed for friend declaration. 843 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
748
749 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
750 template <class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key> >
751 #else
752 template <class Key, class Compare, class Allocator>
753 #endif
754 class flat_multiset;
755
756 template <class Key, class Compare, class Allocator>
757 inline bool operator==(const flat_multiset<Key,Compare,Allocator>& x,
758 const flat_multiset<Key,Compare,Allocator>& y);
759
760 template <class Key, class Compare, class Allocator>
761 inline bool operator<(const flat_multiset<Key,Compare,Allocator>& x,
762 const flat_multiset<Key,Compare,Allocator>& y);
763 /// @endcond
764 844
765 //! flat_multiset is a Sorted Associative Container that stores objects of type Key. 845 //! flat_multiset is a Sorted Associative Container that stores objects of type Key.
766 //! 846 //!
767 //! flat_multiset can store multiple copies of the same key value. 847 //! flat_multiset can store multiple copies of the same key value.
768 //! 848 //!
772 //! 852 //!
773 //! Erasing an element invalidates iterators and references 853 //! Erasing an element invalidates iterators and references
774 //! pointing to elements that come after (their keys are bigger) the erased element. 854 //! pointing to elements that come after (their keys are bigger) the erased element.
775 //! 855 //!
776 //! This container provides random-access iterators. 856 //! This container provides random-access iterators.
857 //!
858 //! \tparam Key is the type to be inserted in the multiset, which is also the key_type
859 //! \tparam Compare is the comparison functor used to order keys
860 //! \tparam Allocator is the allocator to be used to allocate memory for this container
777 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED 861 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
778 template <class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key> > 862 template <class Key, class Compare = std::less<Key>, class Allocator = new_allocator<Key> >
779 #else 863 #else
780 template <class Key, class Compare, class Allocator> 864 template <class Key, class Compare, class Allocator>
781 #endif 865 #endif
782 class flat_multiset 866 class flat_multiset
867 ///@cond
868 : public container_detail::flat_tree<Key, Key, container_detail::identity<Key>, Compare, Allocator>
869 ///@endcond
783 { 870 {
784 /// @cond 871 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
785 private: 872 private:
786 BOOST_COPYABLE_AND_MOVABLE(flat_multiset) 873 BOOST_COPYABLE_AND_MOVABLE(flat_multiset)
787 typedef container_detail::flat_tree<Key, Key, container_detail::identity<Key>, Compare, Allocator> tree_t; 874 typedef container_detail::flat_tree<Key, Key, container_detail::identity<Key>, Compare, Allocator> base_t;
788 tree_t m_flat_tree; // flat tree representing flat_multiset 875 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
789 /// @endcond
790 876
791 public: 877 public:
792 ////////////////////////////////////////////// 878 //////////////////////////////////////////////
793 // 879 //
794 // types 880 // types
796 ////////////////////////////////////////////// 882 //////////////////////////////////////////////
797 typedef Key key_type; 883 typedef Key key_type;
798 typedef Key value_type; 884 typedef Key value_type;
799 typedef Compare key_compare; 885 typedef Compare key_compare;
800 typedef Compare value_compare; 886 typedef Compare value_compare;
887 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
801 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; 888 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
802 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer; 889 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
803 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference; 890 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference;
804 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference; 891 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference;
805 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type; 892 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type;
806 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type; 893 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
807 typedef Allocator allocator_type; 894 typedef Allocator allocator_type;
808 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type; 895 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type;
809 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::iterator) iterator; 896 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator;
810 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_iterator) const_iterator; 897 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator;
811 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator) reverse_iterator; 898 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator;
812 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator) const_reverse_iterator; 899 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator;
813 900
814 //! <b>Effects</b>: Default constructs an empty flat_multiset. 901 //! @copydoc ::boost::container::flat_set::flat_set()
815 //!
816 //! <b>Complexity</b>: Constant.
817 explicit flat_multiset() 902 explicit flat_multiset()
818 : m_flat_tree() 903 : base_t()
819 {} 904 {}
820 905
821 //! <b>Effects</b>: Constructs an empty flat_multiset using the specified 906 //! @copydoc ::boost::container::flat_set::flat_set(const Compare&, const allocator_type&)
822 //! comparison object and allocator.
823 //!
824 //! <b>Complexity</b>: Constant.
825 explicit flat_multiset(const Compare& comp, 907 explicit flat_multiset(const Compare& comp,
826 const allocator_type& a = allocator_type()) 908 const allocator_type& a = allocator_type())
827 : m_flat_tree(comp, a) 909 : base_t(comp, a)
828 {} 910 {}
829 911
830 //! <b>Effects</b>: Constructs an empty flat_multiset using the specified allocator. 912 //! @copydoc ::boost::container::flat_set::flat_set(const allocator_type&)
831 //!
832 //! <b>Complexity</b>: Constant.
833 explicit flat_multiset(const allocator_type& a) 913 explicit flat_multiset(const allocator_type& a)
834 : m_flat_tree(a) 914 : base_t(a)
835 {} 915 {}
836 916
917 //! @copydoc ::boost::container::flat_set::flat_set(InputIterator, InputIterator, const Compare& comp, const allocator_type&)
837 template <class InputIterator> 918 template <class InputIterator>
838 flat_multiset(InputIterator first, InputIterator last, 919 flat_multiset(InputIterator first, InputIterator last,
839 const Compare& comp = Compare(), 920 const Compare& comp = Compare(),
840 const allocator_type& a = allocator_type()) 921 const allocator_type& a = allocator_type())
841 : m_flat_tree(false, first, last, comp, a) 922 : base_t(false, first, last, comp, a)
923 {}
924
925 //! @copydoc ::boost::container::flat_set::flat_set(InputIterator, InputIterator, const allocator_type&)
926 template <class InputIterator>
927 flat_multiset(InputIterator first, InputIterator last, const allocator_type& a)
928 : base_t(false, first, last, Compare(), a)
842 {} 929 {}
843 930
844 //! <b>Effects</b>: Constructs an empty flat_multiset using the specified comparison object and 931 //! <b>Effects</b>: Constructs an empty flat_multiset using the specified comparison object and
845 //! allocator, and inserts elements from the ordered range [first ,last ). This function 932 //! allocator, and inserts elements from the ordered range [first ,last ). This function
846 //! is more efficient than the normal range creation for ordered ranges. 933 //! is more efficient than the normal range creation for ordered ranges.
852 //! <b>Note</b>: Non-standard extension. 939 //! <b>Note</b>: Non-standard extension.
853 template <class InputIterator> 940 template <class InputIterator>
854 flat_multiset(ordered_range_t, InputIterator first, InputIterator last, 941 flat_multiset(ordered_range_t, InputIterator first, InputIterator last,
855 const Compare& comp = Compare(), 942 const Compare& comp = Compare(),
856 const allocator_type& a = allocator_type()) 943 const allocator_type& a = allocator_type())
857 : m_flat_tree(ordered_range, first, last, comp, a) 944 : base_t(ordered_range, first, last, comp, a)
858 {} 945 {}
859 946
860 //! <b>Effects</b>: Copy constructs a flat_multiset. 947 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
861 //! 948 //! @copydoc ::boost::container::flat_set::flat_set(std::initializer_list<value_type>, const Compare& comp, const allocator_type&)
862 //! <b>Complexity</b>: Linear in x.size(). 949 flat_multiset(std::initializer_list<value_type> il, const Compare& comp = Compare(),
950 const allocator_type& a = allocator_type())
951 : base_t(false, il.begin(), il.end(), comp, a)
952 {}
953
954 //! @copydoc ::boost::container::flat_set::flat_set(std::initializer_list<value_type>, const allocator_type&)
955 flat_multiset(std::initializer_list<value_type> il, const allocator_type& a)
956 : base_t(false, il.begin(), il.end(), Compare(), a)
957 {}
958
959 //! @copydoc ::boost::container::flat_set::flat_set(ordered_unique_range_t, std::initializer_list<value_type>, const Compare& comp, const allocator_type&)
960 flat_multiset(ordered_unique_range_t, std::initializer_list<value_type> il,
961 const Compare& comp = Compare(), const allocator_type& a = allocator_type())
962 : base_t(ordered_range, il.begin(), il.end(), comp, a)
963 {}
964 #endif
965
966 //! @copydoc ::boost::container::flat_set::flat_set(const flat_set &)
863 flat_multiset(const flat_multiset& x) 967 flat_multiset(const flat_multiset& x)
864 : m_flat_tree(x.m_flat_tree) 968 : base_t(static_cast<const base_t&>(x))
865 {} 969 {}
866 970
867 //! <b>Effects</b>: Move constructs a flat_multiset. Constructs *this using x's resources. 971 //! @copydoc ::boost::container::flat_set(flat_set &&)
868 //! 972 flat_multiset(BOOST_RV_REF(flat_multiset) x)
869 //! <b>Complexity</b>: Constant. 973 : base_t(boost::move(static_cast<base_t&>(x)))
870 //! 974 {}
871 //! <b>Postcondition</b>: x is emptied. 975
872 flat_multiset(BOOST_RV_REF(flat_multiset) mx) 976 //! @copydoc ::boost::container::flat_set(const flat_set &, const allocator_type &)
873 : m_flat_tree(boost::move(mx.m_flat_tree))
874 {}
875
876 //! <b>Effects</b>: Copy constructs a flat_multiset using the specified allocator.
877 //!
878 //! <b>Complexity</b>: Linear in x.size().
879 flat_multiset(const flat_multiset& x, const allocator_type &a) 977 flat_multiset(const flat_multiset& x, const allocator_type &a)
880 : m_flat_tree(x.m_flat_tree, a) 978 : base_t(static_cast<const base_t&>(x), a)
881 {} 979 {}
882 980
883 //! <b>Effects</b>: Move constructs a flat_multiset using the specified allocator. 981 //! @copydoc ::boost::container::flat_set(flat_set &&, const allocator_type &)
884 //! Constructs *this using x's resources. 982 flat_multiset(BOOST_RV_REF(flat_multiset) x, const allocator_type &a)
885 //! 983 : base_t(BOOST_MOVE_BASE(base_t, x), a)
886 //! <b>Complexity</b>: Constant if a == mx.get_allocator(), linear otherwise 984 {}
887 flat_multiset(BOOST_RV_REF(flat_multiset) mx, const allocator_type &a) 985
888 : m_flat_tree(boost::move(mx.m_flat_tree), a) 986 //! @copydoc ::boost::container::flat_set::operator=(const flat_set &)
889 {}
890
891 //! <b>Effects</b>: Makes *this a copy of x.
892 //!
893 //! <b>Complexity</b>: Linear in x.size().
894 flat_multiset& operator=(BOOST_COPY_ASSIGN_REF(flat_multiset) x) 987 flat_multiset& operator=(BOOST_COPY_ASSIGN_REF(flat_multiset) x)
895 { m_flat_tree = x.m_flat_tree; return *this; } 988 { return static_cast<flat_multiset&>(this->base_t::operator=(static_cast<const base_t&>(x))); }
896 989
897 //! <b>Effects</b>: Makes *this a copy of x. 990 //! @copydoc ::boost::container::flat_set::operator=(flat_set &&)
898 //! 991 flat_multiset& operator=(BOOST_RV_REF(flat_multiset) x)
899 //! <b>Complexity</b>: Linear in x.size(). 992 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
900 flat_multiset& operator=(BOOST_RV_REF(flat_multiset) mx) 993 && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value )
901 { m_flat_tree = boost::move(mx.m_flat_tree); return *this; } 994 { return static_cast<flat_multiset&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); }
902 995
903 //! <b>Effects</b>: Returns a copy of the Allocator that 996 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
904 //! was passed to the object's constructor. 997 //! @copydoc ::boost::container::flat_set::operator=(std::initializer_list<value_type>)
905 //! 998 flat_multiset& operator=(std::initializer_list<value_type> il)
906 //! <b>Complexity</b>: Constant. 999 {
907 allocator_type get_allocator() const BOOST_CONTAINER_NOEXCEPT 1000 this->clear();
908 { return m_flat_tree.get_allocator(); } 1001 this->insert(il.begin(), il.end());
909 1002 return *this;
910 //! <b>Effects</b>: Returns a reference to the internal allocator. 1003 }
911 //! 1004 #endif
912 //! <b>Throws</b>: Nothing 1005
913 //! 1006 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
914 //! <b>Complexity</b>: Constant. 1007
915 //! 1008 //! @copydoc ::boost::container::flat_set::get_allocator()
916 //! <b>Note</b>: Non-standard extension. 1009 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW;
917 stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT 1010
918 { return m_flat_tree.get_stored_allocator(); } 1011 //! @copydoc ::boost::container::flat_set::get_stored_allocator()
919 1012 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW;
920 //! <b>Effects</b>: Returns a reference to the internal allocator. 1013
921 //! 1014 //! @copydoc ::boost::container::flat_set::get_stored_allocator() const
922 //! <b>Throws</b>: Nothing 1015 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW;
923 //! 1016
924 //! <b>Complexity</b>: Constant. 1017 //! @copydoc ::boost::container::flat_set::begin()
925 //! 1018 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW;
926 //! <b>Note</b>: Non-standard extension. 1019
927 const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT 1020 //! @copydoc ::boost::container::flat_set::begin() const
928 { return m_flat_tree.get_stored_allocator(); } 1021 const_iterator begin() const;
929 1022
930 //! <b>Effects</b>: Returns an iterator to the first element contained in the container. 1023 //! @copydoc ::boost::container::flat_set::cbegin() const
931 //! 1024 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
932 //! <b>Throws</b>: Nothing. 1025
933 //! 1026 //! @copydoc ::boost::container::flat_set::end()
934 //! <b>Complexity</b>: Constant. 1027 iterator end() BOOST_NOEXCEPT_OR_NOTHROW;
935 iterator begin() BOOST_CONTAINER_NOEXCEPT 1028
936 { return m_flat_tree.begin(); } 1029 //! @copydoc ::boost::container::flat_set::end() const
937 1030 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW;
938 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. 1031
939 //! 1032 //! @copydoc ::boost::container::flat_set::cend() const
940 //! <b>Throws</b>: Nothing. 1033 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW;
941 //! 1034
942 //! <b>Complexity</b>: Constant. 1035 //! @copydoc ::boost::container::flat_set::rbegin()
943 const_iterator begin() const 1036 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW;
944 { return m_flat_tree.begin(); } 1037
945 1038 //! @copydoc ::boost::container::flat_set::rbegin() const
946 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. 1039 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
947 //! 1040
948 //! <b>Throws</b>: Nothing. 1041 //! @copydoc ::boost::container::flat_set::crbegin() const
949 //! 1042 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
950 //! <b>Complexity</b>: Constant. 1043
951 const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT 1044 //! @copydoc ::boost::container::flat_set::rend()
952 { return m_flat_tree.cbegin(); } 1045 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW;
953 1046
954 //! <b>Effects</b>: Returns an iterator to the end of the container. 1047 //! @copydoc ::boost::container::flat_set::rend() const
955 //! 1048 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW;
956 //! <b>Throws</b>: Nothing. 1049
957 //! 1050 //! @copydoc ::boost::container::flat_set::crend() const
958 //! <b>Complexity</b>: Constant. 1051 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW;
959 iterator end() BOOST_CONTAINER_NOEXCEPT 1052
960 { return m_flat_tree.end(); } 1053 //! @copydoc ::boost::container::flat_set::empty() const
961 1054 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW;
962 //! <b>Effects</b>: Returns a const_iterator to the end of the container. 1055
963 //! 1056 //! @copydoc ::boost::container::flat_set::size() const
964 //! <b>Throws</b>: Nothing. 1057 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW;
965 //! 1058
966 //! <b>Complexity</b>: Constant. 1059 //! @copydoc ::boost::container::flat_set::max_size() const
967 const_iterator end() const BOOST_CONTAINER_NOEXCEPT 1060 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW;
968 { return m_flat_tree.end(); } 1061
969 1062 //! @copydoc ::boost::container::flat_set::capacity() const
970 //! <b>Effects</b>: Returns a const_iterator to the end of the container. 1063 size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW;
971 //! 1064
972 //! <b>Throws</b>: Nothing. 1065 //! @copydoc ::boost::container::flat_set::reserve(size_type)
973 //! 1066 void reserve(size_type cnt);
974 //! <b>Complexity</b>: Constant. 1067
975 const_iterator cend() const BOOST_CONTAINER_NOEXCEPT 1068 //! @copydoc ::boost::container::flat_set::shrink_to_fit()
976 { return m_flat_tree.cend(); } 1069 void shrink_to_fit();
977 1070
978 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning 1071 #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
979 //! of the reversed container.
980 //!
981 //! <b>Throws</b>: Nothing.
982 //!
983 //! <b>Complexity</b>: Constant.
984 reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT
985 { return m_flat_tree.rbegin(); }
986
987 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
988 //! of the reversed container.
989 //!
990 //! <b>Throws</b>: Nothing.
991 //!
992 //! <b>Complexity</b>: Constant.
993 const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT
994 { return m_flat_tree.rbegin(); }
995
996 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
997 //! of the reversed container.
998 //!
999 //! <b>Throws</b>: Nothing.
1000 //!
1001 //! <b>Complexity</b>: Constant.
1002 const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT
1003 { return m_flat_tree.crbegin(); }
1004
1005 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
1006 //! of the reversed container.
1007 //!
1008 //! <b>Throws</b>: Nothing.
1009 //!
1010 //! <b>Complexity</b>: Constant.
1011 reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT
1012 { return m_flat_tree.rend(); }
1013
1014 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1015 //! of the reversed container.
1016 //!
1017 //! <b>Throws</b>: Nothing.
1018 //!
1019 //! <b>Complexity</b>: Constant.
1020 const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT
1021 { return m_flat_tree.rend(); }
1022
1023 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1024 //! of the reversed container.
1025 //!
1026 //! <b>Throws</b>: Nothing.
1027 //!
1028 //! <b>Complexity</b>: Constant.
1029 const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT
1030 { return m_flat_tree.crend(); }
1031
1032 //////////////////////////////////////////////
1033 //
1034 // capacity
1035 //
1036 //////////////////////////////////////////////
1037
1038 //! <b>Effects</b>: Returns true if the container contains no elements.
1039 //!
1040 //! <b>Throws</b>: Nothing.
1041 //!
1042 //! <b>Complexity</b>: Constant.
1043 bool empty() const BOOST_CONTAINER_NOEXCEPT
1044 { return m_flat_tree.empty(); }
1045
1046 //! <b>Effects</b>: Returns the number of the elements contained in the container.
1047 //!
1048 //! <b>Throws</b>: Nothing.
1049 //!
1050 //! <b>Complexity</b>: Constant.
1051 size_type size() const BOOST_CONTAINER_NOEXCEPT
1052 { return m_flat_tree.size(); }
1053
1054 //! <b>Effects</b>: Returns the largest possible size of the container.
1055 //!
1056 //! <b>Throws</b>: Nothing.
1057 //!
1058 //! <b>Complexity</b>: Constant.
1059 size_type max_size() const BOOST_CONTAINER_NOEXCEPT
1060 { return m_flat_tree.max_size(); }
1061
1062 //! <b>Effects</b>: Number of elements for which memory has been allocated.
1063 //! capacity() is always greater than or equal to size().
1064 //!
1065 //! <b>Throws</b>: Nothing.
1066 //!
1067 //! <b>Complexity</b>: Constant.
1068 size_type capacity() const BOOST_CONTAINER_NOEXCEPT
1069 { return m_flat_tree.capacity(); }
1070
1071 //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no
1072 //! effect. Otherwise, it is a request for allocation of additional memory.
1073 //! If the request is successful, then capacity() is greater than or equal to
1074 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
1075 //!
1076 //! <b>Throws</b>: If memory allocation allocation throws or Key's copy constructor throws.
1077 //!
1078 //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to
1079 //! to values might be invalidated.
1080 void reserve(size_type cnt)
1081 { m_flat_tree.reserve(cnt); }
1082
1083 //! <b>Effects</b>: Tries to deallocate the excess of memory created
1084 // with previous allocations. The size of the vector is unchanged
1085 //!
1086 //! <b>Throws</b>: If memory allocation throws, or Key's copy constructor throws.
1087 //!
1088 //! <b>Complexity</b>: Linear to size().
1089 void shrink_to_fit()
1090 { m_flat_tree.shrink_to_fit(); }
1091 1072
1092 ////////////////////////////////////////////// 1073 //////////////////////////////////////////////
1093 // 1074 //
1094 // modifiers 1075 // modifiers
1095 // 1076 //
1096 ////////////////////////////////////////////// 1077 //////////////////////////////////////////////
1097 1078
1098 #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1079 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1099 1080
1100 //! <b>Effects</b>: Inserts an object of type Key constructed with 1081 //! <b>Effects</b>: Inserts an object of type Key constructed with
1101 //! std::forward<Args>(args)... and returns the iterator pointing to the 1082 //! std::forward<Args>(args)... and returns the iterator pointing to the
1102 //! newly inserted element. 1083 //! newly inserted element.
1103 //! 1084 //!
1104 //! <b>Complexity</b>: Logarithmic search time plus linear insertion 1085 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1105 //! to the elements with bigger keys than x. 1086 //! to the elements with bigger keys than x.
1106 //! 1087 //!
1107 //! <b>Note</b>: If an element is inserted it might invalidate elements. 1088 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1108 template <class... Args> 1089 template <class... Args>
1109 iterator emplace(Args&&... args) 1090 iterator emplace(BOOST_FWD_REF(Args)... args)
1110 { return m_flat_tree.emplace_equal(boost::forward<Args>(args)...); } 1091 { return this->base_t::emplace_equal(boost::forward<Args>(args)...); }
1111 1092
1112 //! <b>Effects</b>: Inserts an object of type Key constructed with 1093 //! <b>Effects</b>: Inserts an object of type Key constructed with
1113 //! std::forward<Args>(args)... in the container. 1094 //! std::forward<Args>(args)... in the container.
1114 //! p is a hint pointing to where the insert should start to search. 1095 //! p is a hint pointing to where the insert should start to search.
1115 //! 1096 //!
1119 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted 1100 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
1120 //! right before p) plus insertion linear to the elements with bigger keys than x. 1101 //! right before p) plus insertion linear to the elements with bigger keys than x.
1121 //! 1102 //!
1122 //! <b>Note</b>: If an element is inserted it might invalidate elements. 1103 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1123 template <class... Args> 1104 template <class... Args>
1124 iterator emplace_hint(const_iterator hint, Args&&... args) 1105 iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args)
1125 { return m_flat_tree.emplace_hint_equal(hint, boost::forward<Args>(args)...); } 1106 { return this->base_t::emplace_hint_equal(p, boost::forward<Args>(args)...); }
1126 1107
1127 #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING 1108 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1128 1109
1129 #define BOOST_PP_LOCAL_MACRO(n) \ 1110 #define BOOST_CONTAINER_FLAT_MULTISET_EMPLACE_CODE(N) \
1130 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ 1111 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1131 iterator emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ 1112 iterator emplace(BOOST_MOVE_UREF##N)\
1132 { return m_flat_tree.emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \ 1113 { return this->base_t::emplace_equal(BOOST_MOVE_FWD##N); }\
1133 \ 1114 \
1134 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ 1115 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1135 iterator emplace_hint(const_iterator hint \ 1116 iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1136 BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ 1117 { return this->base_t::emplace_hint_equal(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
1137 { return m_flat_tree.emplace_hint_equal \ 1118 //
1138 (hint BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \ 1119 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MULTISET_EMPLACE_CODE)
1139 //! 1120 #undef BOOST_CONTAINER_FLAT_MULTISET_EMPLACE_CODE
1140 #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) 1121
1141 #include BOOST_PP_LOCAL_ITERATE() 1122 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1142
1143 #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
1144 1123
1145 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1124 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1146 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the 1125 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
1147 //! newly inserted element. 1126 //! newly inserted element.
1148 //! 1127 //!
1185 //! 1164 //!
1186 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted 1165 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
1187 //! right before p) plus insertion linear to the elements with bigger keys than x. 1166 //! right before p) plus insertion linear to the elements with bigger keys than x.
1188 //! 1167 //!
1189 //! <b>Note</b>: If an element is inserted it might invalidate elements. 1168 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1190 iterator insert(const_iterator position, value_type &&x); 1169 iterator insert(const_iterator p, value_type &&x);
1191 #else 1170 #else
1192 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator) 1171 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator)
1193 #endif 1172 #endif
1194 1173
1195 //! <b>Requires</b>: first, last are not iterators into *this. 1174 //! <b>Requires</b>: first, last are not iterators into *this.
1200 //! search time plus N*size() insertion time. 1179 //! search time plus N*size() insertion time.
1201 //! 1180 //!
1202 //! <b>Note</b>: If an element is inserted it might invalidate elements. 1181 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1203 template <class InputIterator> 1182 template <class InputIterator>
1204 void insert(InputIterator first, InputIterator last) 1183 void insert(InputIterator first, InputIterator last)
1205 { m_flat_tree.insert_equal(first, last); } 1184 { this->base_t::insert_equal(first, last); }
1206 1185
1207 //! <b>Requires</b>: first, last are not iterators into *this and 1186 //! <b>Requires</b>: first, last are not iterators into *this and
1208 //! must be ordered according to the predicate. 1187 //! must be ordered according to the predicate.
1209 //! 1188 //!
1210 //! <b>Effects</b>: inserts each element from the range [first,last) .This function 1189 //! <b>Effects</b>: inserts each element from the range [first,last) .This function
1214 //! search time plus N*size() insertion time. 1193 //! search time plus N*size() insertion time.
1215 //! 1194 //!
1216 //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements. 1195 //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements.
1217 template <class InputIterator> 1196 template <class InputIterator>
1218 void insert(ordered_range_t, InputIterator first, InputIterator last) 1197 void insert(ordered_range_t, InputIterator first, InputIterator last)
1219 { m_flat_tree.insert_equal(ordered_range, first, last); } 1198 { this->base_t::insert_equal(ordered_range, first, last); }
1220 1199
1221 //! <b>Effects</b>: Erases the element pointed to by position. 1200 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1222 //! 1201 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()).
1223 //! <b>Returns</b>: Returns an iterator pointing to the element immediately 1202 //!
1224 //! following q prior to the element being erased. If no such element exists, 1203 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1225 //! returns end(). 1204 //! search time plus N*size() insertion time.
1226 //! 1205 //!
1227 //! <b>Complexity</b>: Linear to the elements with keys bigger than position 1206 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1228 //! 1207 void insert(std::initializer_list<value_type> il)
1229 //! <b>Note</b>: Invalidates elements with keys 1208 { this->base_t::insert_equal(il.begin(), il.end()); }
1230 //! not less than the erased element. 1209
1231 iterator erase(const_iterator position) 1210 //! <b>Requires</b>: Range [il.begin(), il.end()) must be ordered according to the predicate.
1232 { return m_flat_tree.erase(position); } 1211 //!
1233 1212 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()). This function
1234 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. 1213 //! is more efficient than the normal range creation for ordered ranges.
1235 //! 1214 //!
1236 //! <b>Returns</b>: Returns the number of erased elements. 1215 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end())
1237 //! 1216 //! search time plus N*size() insertion time.
1238 //! <b>Complexity</b>: Logarithmic search time plus erasure time 1217 //!
1239 //! linear to the elements with bigger keys. 1218 //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements.
1240 size_type erase(const key_type& x) 1219 void insert(ordered_range_t, std::initializer_list<value_type> il)
1241 { return m_flat_tree.erase(x); } 1220 { this->base_t::insert_equal(ordered_range, il.begin(), il.end()); }
1242 1221 #endif
1243 //! <b>Effects</b>: Erases all the elements in the range [first, last). 1222
1244 //! 1223 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1245 //! <b>Returns</b>: Returns last. 1224
1246 //! 1225 //! @copydoc ::boost::container::flat_set::erase(const_iterator)
1247 //! <b>Complexity</b>: size()*N where N is the distance from first to last. 1226 iterator erase(const_iterator p);
1248 //! 1227
1249 //! <b>Complexity</b>: Logarithmic search time plus erasure time 1228 //! @copydoc ::boost::container::flat_set::erase(const key_type&)
1250 //! linear to the elements with bigger keys. 1229 size_type erase(const key_type& x);
1251 iterator erase(const_iterator first, const_iterator last) 1230
1252 { return m_flat_tree.erase(first, last); } 1231 //! @copydoc ::boost::container::flat_set::erase(const_iterator,const_iterator)
1253 1232 iterator erase(const_iterator first, const_iterator last);
1254 //! <b>Effects</b>: Swaps the contents of *this and x. 1233
1255 //! 1234 //! @copydoc ::boost::container::flat_set::swap
1256 //! <b>Throws</b>: Nothing.
1257 //!
1258 //! <b>Complexity</b>: Constant.
1259 void swap(flat_multiset& x) 1235 void swap(flat_multiset& x)
1260 { m_flat_tree.swap(x.m_flat_tree); } 1236 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
1261 1237 && boost::container::container_detail::is_nothrow_swappable<Compare>::value );
1262 //! <b>Effects</b>: erase(a.begin(),a.end()). 1238
1263 //! 1239 //! @copydoc ::boost::container::flat_set::clear
1264 //! <b>Postcondition</b>: size() == 0. 1240 void clear() BOOST_NOEXCEPT_OR_NOTHROW;
1265 //! 1241
1266 //! <b>Complexity</b>: linear in size(). 1242 //! @copydoc ::boost::container::flat_set::key_comp
1267 void clear() BOOST_CONTAINER_NOEXCEPT 1243 key_compare key_comp() const;
1268 { m_flat_tree.clear(); } 1244
1269 1245 //! @copydoc ::boost::container::flat_set::value_comp
1270 ////////////////////////////////////////////// 1246 value_compare value_comp() const;
1271 // 1247
1272 // observers 1248 //! @copydoc ::boost::container::flat_set::find(const key_type& )
1273 // 1249 iterator find(const key_type& x);
1274 ////////////////////////////////////////////// 1250
1275 1251 //! @copydoc ::boost::container::flat_set::find(const key_type& ) const
1276 //! <b>Effects</b>: Returns the comparison object out 1252 const_iterator find(const key_type& x) const;
1277 //! of which a was constructed. 1253
1278 //! 1254 //! @copydoc ::boost::container::flat_set::nth(size_type)
1279 //! <b>Complexity</b>: Constant. 1255 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW;
1280 key_compare key_comp() const 1256
1281 { return m_flat_tree.key_comp(); } 1257 //! @copydoc ::boost::container::flat_set::nth(size_type) const
1282 1258 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW;
1283 //! <b>Effects</b>: Returns an object of value_compare constructed out 1259
1284 //! of the comparison object. 1260 //! @copydoc ::boost::container::flat_set::index_of(iterator)
1285 //! 1261 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW;
1286 //! <b>Complexity</b>: Constant. 1262
1287 value_compare value_comp() const 1263 //! @copydoc ::boost::container::flat_set::index_of(const_iterator) const
1288 { return m_flat_tree.key_comp(); } 1264 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW;
1289 1265
1290 ////////////////////////////////////////////// 1266 //! @copydoc ::boost::container::flat_set::count(const key_type& ) const
1291 // 1267 size_type count(const key_type& x) const;
1292 // set operations 1268
1293 // 1269 //! @copydoc ::boost::container::flat_set::lower_bound(const key_type& )
1294 ////////////////////////////////////////////// 1270 iterator lower_bound(const key_type& x);
1295 1271
1296 //! <b>Returns</b>: An iterator pointing to an element with the key 1272 //! @copydoc ::boost::container::flat_set::lower_bound(const key_type& ) const
1297 //! equivalent to x, or end() if such an element is not found. 1273 const_iterator lower_bound(const key_type& x) const;
1298 //! 1274
1299 //! <b>Complexity</b>: Logarithmic. 1275 //! @copydoc ::boost::container::flat_set::upper_bound(const key_type& )
1300 iterator find(const key_type& x) 1276 iterator upper_bound(const key_type& x);
1301 { return m_flat_tree.find(x); } 1277
1302 1278 //! @copydoc ::boost::container::flat_set::upper_bound(const key_type& ) const
1303 //! <b>Returns</b>: Allocator const_iterator pointing to an element with the key 1279 const_iterator upper_bound(const key_type& x) const;
1304 //! equivalent to x, or end() if such an element is not found. 1280
1305 //! 1281 //! @copydoc ::boost::container::flat_set::equal_range(const key_type& ) const
1306 //! <b>Complexity</b>: Logarithmic.s 1282 std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
1307 const_iterator find(const key_type& x) const 1283
1308 { return m_flat_tree.find(x); } 1284 //! @copydoc ::boost::container::flat_set::equal_range(const key_type& )
1309 1285 std::pair<iterator,iterator> equal_range(const key_type& x);
1310 //! <b>Returns</b>: The number of elements with key equivalent to x. 1286
1311 //! 1287 //! <b>Effects</b>: Returns true if x and y are equal
1312 //! <b>Complexity</b>: log(size())+count(k) 1288 //!
1313 size_type count(const key_type& x) const 1289 //! <b>Complexity</b>: Linear to the number of elements in the container.
1314 { return m_flat_tree.count(x); } 1290 friend bool operator==(const flat_multiset& x, const flat_multiset& y);
1315 1291
1316 //! <b>Returns</b>: An iterator pointing to the first element with key not less 1292 //! <b>Effects</b>: Returns true if x and y are unequal
1317 //! than k, or a.end() if such an element is not found. 1293 //!
1318 //! 1294 //! <b>Complexity</b>: Linear to the number of elements in the container.
1319 //! <b>Complexity</b>: Logarithmic 1295 friend bool operator!=(const flat_multiset& x, const flat_multiset& y);
1320 iterator lower_bound(const key_type& x) 1296
1321 { return m_flat_tree.lower_bound(x); } 1297 //! <b>Effects</b>: Returns true if x is less than y
1322 1298 //!
1323 //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not 1299 //! <b>Complexity</b>: Linear to the number of elements in the container.
1324 //! less than k, or a.end() if such an element is not found. 1300 friend bool operator<(const flat_multiset& x, const flat_multiset& y);
1325 //! 1301
1326 //! <b>Complexity</b>: Logarithmic 1302 //! <b>Effects</b>: Returns true if x is greater than y
1327 const_iterator lower_bound(const key_type& x) const 1303 //!
1328 { return m_flat_tree.lower_bound(x); } 1304 //! <b>Complexity</b>: Linear to the number of elements in the container.
1329 1305 friend bool operator>(const flat_multiset& x, const flat_multiset& y);
1330 //! <b>Returns</b>: An iterator pointing to the first element with key not less 1306
1331 //! than x, or end() if such an element is not found. 1307 //! <b>Effects</b>: Returns true if x is equal or less than y
1332 //! 1308 //!
1333 //! <b>Complexity</b>: Logarithmic 1309 //! <b>Complexity</b>: Linear to the number of elements in the container.
1334 iterator upper_bound(const key_type& x) 1310 friend bool operator<=(const flat_multiset& x, const flat_multiset& y);
1335 { return m_flat_tree.upper_bound(x); } 1311
1336 1312 //! <b>Effects</b>: Returns true if x is equal or greater than y
1337 //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not 1313 //!
1338 //! less than x, or end() if such an element is not found. 1314 //! <b>Complexity</b>: Linear to the number of elements in the container.
1339 //! 1315 friend bool operator>=(const flat_multiset& x, const flat_multiset& y);
1340 //! <b>Complexity</b>: Logarithmic 1316
1341 const_iterator upper_bound(const key_type& x) const 1317 //! <b>Effects</b>: x.swap(y)
1342 { return m_flat_tree.upper_bound(x); } 1318 //!
1343 1319 //! <b>Complexity</b>: Constant.
1344 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). 1320 friend void swap(flat_multiset& x, flat_multiset& y);
1345 //! 1321
1346 //! <b>Complexity</b>: Logarithmic 1322 #endif //#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
1347 std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const 1323
1348 { return m_flat_tree.equal_range(x); } 1324 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1349
1350 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1351 //!
1352 //! <b>Complexity</b>: Logarithmic
1353 std::pair<iterator,iterator> equal_range(const key_type& x)
1354 { return m_flat_tree.equal_range(x); }
1355
1356 /// @cond
1357 template <class K1, class C1, class A1>
1358 friend bool operator== (const flat_multiset<K1,C1,A1>&,
1359 const flat_multiset<K1,C1,A1>&);
1360 template <class K1, class C1, class A1>
1361 friend bool operator< (const flat_multiset<K1,C1,A1>&,
1362 const flat_multiset<K1,C1,A1>&);
1363 private: 1325 private:
1364 template <class KeyType> 1326 template <class KeyType>
1365 iterator priv_insert(BOOST_FWD_REF(KeyType) x) 1327 iterator priv_insert(BOOST_FWD_REF(KeyType) x)
1366 { return m_flat_tree.insert_equal(::boost::forward<KeyType>(x)); } 1328 { return this->base_t::insert_equal(::boost::forward<KeyType>(x)); }
1367 1329
1368 template <class KeyType> 1330 template <class KeyType>
1369 iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x) 1331 iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x)
1370 { return m_flat_tree.insert_equal(p, ::boost::forward<KeyType>(x)); } 1332 { return this->base_t::insert_equal(p, ::boost::forward<KeyType>(x)); }
1371 /// @endcond 1333 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1372 }; 1334 };
1373 1335
1374 template <class Key, class Compare, class Allocator> 1336 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1375 inline bool operator==(const flat_multiset<Key,Compare,Allocator>& x,
1376 const flat_multiset<Key,Compare,Allocator>& y)
1377 { return x.m_flat_tree == y.m_flat_tree; }
1378
1379 template <class Key, class Compare, class Allocator>
1380 inline bool operator<(const flat_multiset<Key,Compare,Allocator>& x,
1381 const flat_multiset<Key,Compare,Allocator>& y)
1382 { return x.m_flat_tree < y.m_flat_tree; }
1383
1384 template <class Key, class Compare, class Allocator>
1385 inline bool operator!=(const flat_multiset<Key,Compare,Allocator>& x,
1386 const flat_multiset<Key,Compare,Allocator>& y)
1387 { return !(x == y); }
1388
1389 template <class Key, class Compare, class Allocator>
1390 inline bool operator>(const flat_multiset<Key,Compare,Allocator>& x,
1391 const flat_multiset<Key,Compare,Allocator>& y)
1392 { return y < x; }
1393
1394 template <class Key, class Compare, class Allocator>
1395 inline bool operator<=(const flat_multiset<Key,Compare,Allocator>& x,
1396 const flat_multiset<Key,Compare,Allocator>& y)
1397 { return !(y < x); }
1398
1399 template <class Key, class Compare, class Allocator>
1400 inline bool operator>=(const flat_multiset<Key,Compare,Allocator>& x,
1401 const flat_multiset<Key,Compare,Allocator>& y)
1402 { return !(x < y); }
1403
1404 template <class Key, class Compare, class Allocator>
1405 inline void swap(flat_multiset<Key,Compare,Allocator>& x, flat_multiset<Key,Compare,Allocator>& y)
1406 { x.swap(y); }
1407
1408 /// @cond
1409 1337
1410 } //namespace container { 1338 } //namespace container {
1411 1339
1412 //!has_trivial_destructor_after_move<> == true_type 1340 //!has_trivial_destructor_after_move<> == true_type
1413 //!specialization for optimizations 1341 //!specialization for optimizations
1414 template <class Key, class C, class Allocator> 1342 template <class Key, class Compare, class Allocator>
1415 struct has_trivial_destructor_after_move<boost::container::flat_multiset<Key, C, Allocator> > 1343 struct has_trivial_destructor_after_move<boost::container::flat_multiset<Key, Compare, Allocator> >
1416 { 1344 {
1417 static const bool value = has_trivial_destructor_after_move<Allocator>::value && has_trivial_destructor_after_move<C>::value; 1345 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
1346 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
1347 ::boost::has_trivial_destructor_after_move<pointer>::value &&
1348 ::boost::has_trivial_destructor_after_move<Compare>::value;
1418 }; 1349 };
1419 1350
1420 namespace container { 1351 namespace container {
1421 1352
1422 /// @endcond 1353 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1423 1354
1424 }} 1355 }}
1425 1356
1426 #include <boost/container/detail/config_end.hpp> 1357 #include <boost/container/detail/config_end.hpp>
1427 1358
1428 #endif /* BOOST_CONTAINER_FLAT_SET_HPP */ 1359 #endif // BOOST_CONTAINER_FLAT_SET_HPP