1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2005-2009. Distributed under the Boost
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)
6 //
7 // See http://www.boost.org/libs/container for documentation.
8 //
9 //////////////////////////////////////////////////////////////////////////////
10 //
11 // This file comes from SGI's stl_map/stl_multimap files. Modified by Ion Gaztanaga.
12 // Renaming, isolating and porting to generic algorithms. Pointer typedef
13 // set to allocator::pointer to allow placing it in shared memory.
14 //
15 ///////////////////////////////////////////////////////////////////////////////
16 /*
17 *
18 * Copyright (c) 1994
19 * Hewlett-Packard Company
20 *
21 * Permission to use, copy, modify, distribute and sell this software
22 * and its documentation for any purpose is hereby granted without fee,
23 * provided that the above copyright notice appear in all copies and
24 * that both that copyright notice and this permission notice appear
25 * in supporting documentation. Hewlett-Packard Company makes no
26 * representations about the suitability of this software for any
27 * purpose. It is provided "as is" without express or implied warranty.
28 *
29 *
30 * Copyright (c) 1996
31 * Silicon Graphics Computer Systems, Inc.
32 *
33 * Permission to use, copy, modify, distribute and sell this software
34 * and its documentation for any purpose is hereby granted without fee,
35 * provided that the above copyright notice appear in all copies and
36 * that both that copyright notice and this permission notice appear
37 * in supporting documentation. Silicon Graphics makes no
38 * representations about the suitability of this software for any
39 * purpose. It is provided "as is" without express or implied warranty.
40 *
41 */
42
43 #ifndef BOOST_CONTAINERS_MAP_HPP
44 #define BOOST_CONTAINERS_MAP_HPP
45
46 #if (defined _MSC_VER) && (_MSC_VER >= 1200)
47 # pragma once
48 #endif
49
50 #include "detail/config_begin.hpp"
51 #include INCLUDE_BOOST_CONTAINER_DETAIL_WORKAROUND_HPP
52
53 #include INCLUDE_BOOST_CONTAINER_CONTAINER_FWD_HPP
54 #include <utility>
55 #include <functional>
56 #include <memory>
57 #include <stdexcept>
58 #include INCLUDE_BOOST_CONTAINER_DETAIL_TREE_HPP
59 #include INCLUDE_BOOST_CONTAINER_DETAIL_VALUE_INIT_HPP
60 #include <boost/type_traits/has_trivial_destructor.hpp>
61 #include INCLUDE_BOOST_CONTAINER_DETAIL_MPL_HPP
62 #include INCLUDE_BOOST_CONTAINER_DETAIL_UTILITIES_HPP
63 #include INCLUDE_BOOST_CONTAINER_DETAIL_PAIR_HPP
64 #include INCLUDE_BOOST_CONTAINER_MOVE_HPP
65
66 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
67 namespace boost {
68 namespace container {
69 #else
70 namespace boost {
71 namespace container {
72 #endif
73
74 /// @cond
75 // Forward declarations of operators == and <, needed for friend declarations.
76 template <class Key, class T, class Pred, class Alloc>
77 inline bool operator==(const map<Key,T,Pred,Alloc>& x,
78 const map<Key,T,Pred,Alloc>& y);
79
80 template <class Key, class T, class Pred, class Alloc>
81 inline bool operator<(const map<Key,T,Pred,Alloc>& x,
82 const map<Key,T,Pred,Alloc>& y);
83 /// @endcond
84
85 //! A map is a kind of associative container that supports unique keys (contains at
86 //! most one of each key value) and provides for fast retrieval of values of another
87 //! type T based on the keys. The map class supports bidirectional iterators.
88 //!
89 //! A map satisfies all of the requirements of a container and of a reversible
90 //! container and of an associative container. For a
91 //! map<Key,T> the key_type is Key and the value_type is std::pair<const Key,T>.
92 //!
93 //! Pred is the ordering function for Keys (e.g. <i>std::less<Key></i>).
94 //!
95 //! Alloc is the allocator to allocate the value_types
96 //! (e.g. <i>allocator< std::pair<const Key, T> > </i>).
97 template <class Key, class T, class Pred, class Alloc>
98 class map
99 {
100 /// @cond
101 private:
102 BOOST_MOVE_MACRO_COPYABLE_AND_MOVABLE(map)
103 typedef containers_detail::rbtree<Key,
104 std::pair<const Key, T>,
105 containers_detail::select1st< std::pair<const Key, T> >,
106 Pred,
107 Alloc> tree_t;
108 tree_t m_tree; // red-black tree representing map
109 /// @endcond
110
111 public:
112
113 // typedefs:
114 typedef typename tree_t::key_type key_type;
115 typedef typename tree_t::value_type value_type;
116 typedef typename tree_t::pointer pointer;
117 typedef typename tree_t::const_pointer const_pointer;
118 typedef typename tree_t::reference reference;
119 typedef typename tree_t::const_reference const_reference;
120 typedef T mapped_type;
121 typedef Pred key_compare;
122 typedef typename tree_t::iterator iterator;
123 typedef typename tree_t::const_iterator const_iterator;
124 typedef typename tree_t::reverse_iterator reverse_iterator;
125 typedef typename tree_t::const_reverse_iterator const_reverse_iterator;
126 typedef typename tree_t::size_type size_type;
127 typedef typename tree_t::difference_type difference_type;
128 typedef typename tree_t::allocator_type allocator_type;
129 typedef typename tree_t::stored_allocator_type stored_allocator_type;
130 typedef std::pair<key_type, mapped_type> nonconst_value_type;
131 typedef containers_detail::pair
132 <key_type, mapped_type> nonconst_impl_value_type;
133
134 /// @cond
135 class value_compare_impl
136 : public Pred,
137 public std::binary_function<value_type, value_type, bool>
138 {
139 friend class map<Key,T,Pred,Alloc>;
140 protected :
value_compare_impl(const Pred & c)141 value_compare_impl(const Pred &c) : Pred(c) {}
142 public:
operator ()(const value_type & x,const value_type & y) const143 bool operator()(const value_type& x, const value_type& y) const {
144 return Pred::operator()(x.first, y.first);
145 }
146 };
147 /// @endcond
148 typedef value_compare_impl value_compare;
149
150 //! <b>Effects</b>: Constructs an empty map using the specified comparison object
151 //! and allocator.
152 //!
153 //! <b>Complexity</b>: Constant.
map(const Pred & comp=Pred (),const allocator_type & a=allocator_type ())154 explicit map(const Pred& comp = Pred(),
155 const allocator_type& a = allocator_type())
156 : m_tree(comp, a)
157 {}
158
159 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
160 //! allocator, and inserts elements from the range [first ,last ).
161 //!
162 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
163 //! comp and otherwise N logN, where N is last - first.
164 template <class InputIterator>
map(InputIterator first,InputIterator last,const Pred & comp=Pred (),const allocator_type & a=allocator_type ())165 map(InputIterator first, InputIterator last, const Pred& comp = Pred(),
166 const allocator_type& a = allocator_type())
167 : m_tree(first, last, comp, a, true)
168 {}
169
170 //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
171 //! allocator, and inserts elements from the ordered unique range [first ,last). This function
172 //! is more efficient than the normal range creation for ordered ranges.
173 //!
174 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
175 //! unique values.
176 //!
177 //! <b>Complexity</b>: Linear in N.
178 template <class InputIterator>
map(ordered_unique_range_t,InputIterator first,InputIterator last,const Pred & comp=Pred (),const allocator_type & a=allocator_type ())179 map( ordered_unique_range_t, InputIterator first, InputIterator last
180 , const Pred& comp = Pred(), const allocator_type& a = allocator_type())
181 : m_tree(ordered_range, first, last, comp, a)
182 {}
183
184 //! <b>Effects</b>: Copy constructs a map.
185 //!
186 //! <b>Complexity</b>: Linear in x.size().
map(const map<Key,T,Pred,Alloc> & x)187 map(const map<Key,T,Pred,Alloc>& x)
188 : m_tree(x.m_tree)
189 {}
190
191 //! <b>Effects</b>: Move constructs a map. Constructs *this using x's resources.
192 //!
193 //! <b>Complexity</b>: Construct.
194 //!
195 //! <b>Postcondition</b>: x is emptied.
map(BOOST_MOVE_MACRO_RV_REF (map)x)196 map(BOOST_MOVE_MACRO_RV_REF(map) x)
197 : m_tree(BOOST_CONTAINER_MOVE_NAMESPACE::move(x.m_tree))
198 {}
199
200 //! <b>Effects</b>: Makes *this a copy of x.
201 //!
202 //! <b>Complexity</b>: Linear in x.size().
operator =(BOOST_MOVE_MACRO_COPY_ASSIGN_REF (map)x)203 map& operator=(BOOST_MOVE_MACRO_COPY_ASSIGN_REF(map) x)
204 { m_tree = x.m_tree; return *this; }
205
206 //! <b>Effects</b>: this->swap(x.get()).
207 //!
208 //! <b>Complexity</b>: Constant.
operator =(BOOST_MOVE_MACRO_RV_REF (map)x)209 map& operator=(BOOST_MOVE_MACRO_RV_REF(map) x)
210 { m_tree = BOOST_CONTAINER_MOVE_NAMESPACE::move(x.m_tree); return *this; }
211
212 //! <b>Effects</b>: Returns the comparison object out
213 //! of which a was constructed.
214 //!
215 //! <b>Complexity</b>: Constant.
key_comp() const216 key_compare key_comp() const
217 { return m_tree.key_comp(); }
218
219 //! <b>Effects</b>: Returns an object of value_compare constructed out
220 //! of the comparison object.
221 //!
222 //! <b>Complexity</b>: Constant.
value_comp() const223 value_compare value_comp() const
224 { return value_compare(m_tree.key_comp()); }
225
226 //! <b>Effects</b>: Returns a copy of the Allocator that
227 //! was passed to the object's constructor.
228 //!
229 //! <b>Complexity</b>: Constant.
get_allocator() const230 allocator_type get_allocator() const
231 { return m_tree.get_allocator(); }
232
get_stored_allocator() const233 const stored_allocator_type &get_stored_allocator() const
234 { return m_tree.get_stored_allocator(); }
235
get_stored_allocator()236 stored_allocator_type &get_stored_allocator()
237 { return m_tree.get_stored_allocator(); }
238
239 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
240 //!
241 //! <b>Throws</b>: Nothing.
242 //!
243 //! <b>Complexity</b>: Constant.
begin()244 iterator begin()
245 { return m_tree.begin(); }
246
247 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
248 //!
249 //! <b>Throws</b>: Nothing.
250 //!
251 //! <b>Complexity</b>: Constant.
begin() const252 const_iterator begin() const
253 { return m_tree.begin(); }
254
255 //! <b>Effects</b>: Returns an iterator to the end of the container.
256 //!
257 //! <b>Throws</b>: Nothing.
258 //!
259 //! <b>Complexity</b>: Constant.
end()260 iterator end()
261 { return m_tree.end(); }
262
263 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
264 //!
265 //! <b>Throws</b>: Nothing.
266 //!
267 //! <b>Complexity</b>: Constant.
end() const268 const_iterator end() const
269 { return m_tree.end(); }
270
271 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
272 //! of the reversed container.
273 //!
274 //! <b>Throws</b>: Nothing.
275 //!
276 //! <b>Complexity</b>: Constant.
rbegin()277 reverse_iterator rbegin()
278 { return m_tree.rbegin(); }
279
280 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
281 //! of the reversed container.
282 //!
283 //! <b>Throws</b>: Nothing.
284 //!
285 //! <b>Complexity</b>: Constant.
rbegin() const286 const_reverse_iterator rbegin() const
287 { return m_tree.rbegin(); }
288
289 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
290 //! of the reversed container.
291 //!
292 //! <b>Throws</b>: Nothing.
293 //!
294 //! <b>Complexity</b>: Constant.
rend()295 reverse_iterator rend()
296 { return m_tree.rend(); }
297
298 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
299 //! of the reversed container.
300 //!
301 //! <b>Throws</b>: Nothing.
302 //!
303 //! <b>Complexity</b>: Constant.
rend() const304 const_reverse_iterator rend() const
305 { return m_tree.rend(); }
306
307 //! <b>Effects</b>: Returns true if the container contains no elements.
308 //!
309 //! <b>Throws</b>: Nothing.
310 //!
311 //! <b>Complexity</b>: Constant.
empty() const312 bool empty() const
313 { return m_tree.empty(); }
314
315 //! <b>Effects</b>: Returns the number of the elements contained in the container.
316 //!
317 //! <b>Throws</b>: Nothing.
318 //!
319 //! <b>Complexity</b>: Constant.
size() const320 size_type size() const
321 { return m_tree.size(); }
322
323 //! <b>Effects</b>: Returns the largest possible size of the container.
324 //!
325 //! <b>Throws</b>: Nothing.
326 //!
327 //! <b>Complexity</b>: Constant.
max_size() const328 size_type max_size() const
329 { return m_tree.max_size(); }
330
331 //! Effects: If there is no key equivalent to x in the map, inserts
332 //! value_type(x, T()) into the map.
333 //!
334 //! Returns: A reference to the mapped_type corresponding to x in *this.
335 //!
336 //! Complexity: Logarithmic.
operator [](const key_type & k)337 T& operator[](const key_type& k)
338 {
339 //we can optimize this
340 iterator i = lower_bound(k);
341 // i->first is greater than or equivalent to k.
342 if (i == end() || key_comp()(k, (*i).first)){
343 containers_detail::value_init<T> v;
344 value_type val(k, BOOST_CONTAINER_MOVE_NAMESPACE::move(v.m_t));
345 i = insert(i, BOOST_CONTAINER_MOVE_NAMESPACE::move(val));
346 }
347 return (*i).second;
348 }
349
350 //! Effects: If there is no key equivalent to x in the map, inserts
351 //! value_type(BOOST_CONTAINER_MOVE_NAMESPACE::move(x), T()) into the map (the key is move-constructed)
352 //!
353 //! Returns: A reference to the mapped_type corresponding to x in *this.
354 //!
355 //! Complexity: Logarithmic.
operator [](BOOST_MOVE_MACRO_RV_REF (key_type)mk)356 T& operator[](BOOST_MOVE_MACRO_RV_REF(key_type) mk)
357 {
358 key_type &k = mk;
359 //we can optimize this
360 iterator i = lower_bound(k);
361 // i->first is greater than or equivalent to k.
362 if (i == end() || key_comp()(k, (*i).first)){
363 value_type val(BOOST_CONTAINER_MOVE_NAMESPACE::move(k), BOOST_CONTAINER_MOVE_NAMESPACE::move(T()));
364 i = insert(i, BOOST_CONTAINER_MOVE_NAMESPACE::move(val));
365 }
366 return (*i).second;
367 }
368
369 //! Returns: A reference to the element whose key is equivalent to x.
370 //! Throws: An exception object of type out_of_range if no such element is present.
371 //! Complexity: logarithmic.
at(const key_type & k)372 T& at(const key_type& k)
373 {
374 iterator i = this->find(k);
375 if(i == this->end()){
376 throw std::out_of_range("key not found");
377 }
378 return i->second;
379 }
380
381 //! Returns: A reference to the element whose key is equivalent to x.
382 //! Throws: An exception object of type out_of_range if no such element is present.
383 //! Complexity: logarithmic.
at(const key_type & k) const384 const T& at(const key_type& k) const
385 {
386 const_iterator i = this->find(k);
387 if(i == this->end()){
388 throw std::out_of_range("key not found");
389 }
390 return i->second;
391 }
392
393 //! <b>Effects</b>: Swaps the contents of *this and x.
394 //! If this->allocator_type() != x.allocator_type() allocators are also swapped.
395 //!
396 //! <b>Throws</b>: Nothing.
397 //!
398 //! <b>Complexity</b>: Constant.
swap(map & x)399 void swap(map& x)
400 { m_tree.swap(x.m_tree); }
401
402 //! <b>Effects</b>: Inserts x if and only if there is no element in the container
403 //! with key equivalent to the key of x.
404 //!
405 //! <b>Returns</b>: The bool component of the returned pair is true if and only
406 //! if the insertion takes place, and the iterator component of the pair
407 //! points to the element with key equivalent to the key of x.
408 //!
409 //! <b>Complexity</b>: Logarithmic.
insert(const value_type & x)410 std::pair<iterator,bool> insert(const value_type& x)
411 { return m_tree.insert_unique(x); }
412
413 //! <b>Effects</b>: Inserts a new value_type created from the pair if and only if
414 //! there is no element in the container with key equivalent to the key of x.
415 //!
416 //! <b>Returns</b>: The bool component of the returned pair is true if and only
417 //! if the insertion takes place, and the iterator component of the pair
418 //! points to the element with key equivalent to the key of x.
419 //!
420 //! <b>Complexity</b>: Logarithmic.
insert(const nonconst_value_type & x)421 std::pair<iterator,bool> insert(const nonconst_value_type& x)
422 { return m_tree.insert_unique(x); }
423
424 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
425 //! only if there is no element in the container with key equivalent to the key of x.
426 //!
427 //! <b>Returns</b>: The bool component of the returned pair is true if and only
428 //! if the insertion takes place, and the iterator component of the pair
429 //! points to the element with key equivalent to the key of x.
430 //!
431 //! <b>Complexity</b>: Logarithmic.
insert(BOOST_MOVE_MACRO_RV_REF (nonconst_value_type)x)432 std::pair<iterator,bool> insert(BOOST_MOVE_MACRO_RV_REF(nonconst_value_type) x)
433 { return m_tree.insert_unique(BOOST_CONTAINER_MOVE_NAMESPACE::move(x)); }
434
435 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
436 //! only if there is no element in the container with key equivalent to the key of x.
437 //!
438 //! <b>Returns</b>: The bool component of the returned pair is true if and only
439 //! if the insertion takes place, and the iterator component of the pair
440 //! points to the element with key equivalent to the key of x.
441 //!
442 //! <b>Complexity</b>: Logarithmic.
insert(BOOST_MOVE_MACRO_RV_REF (nonconst_impl_value_type)x)443 std::pair<iterator,bool> insert(BOOST_MOVE_MACRO_RV_REF(nonconst_impl_value_type) x)
444 { return m_tree.insert_unique(BOOST_CONTAINER_MOVE_NAMESPACE::move(x)); }
445
446 //! <b>Effects</b>: Move constructs a new value from x if and only if there is
447 //! no element in the container with key equivalent to the key of x.
448 //!
449 //! <b>Returns</b>: The bool component of the returned pair is true if and only
450 //! if the insertion takes place, and the iterator component of the pair
451 //! points to the element with key equivalent to the key of x.
452 //!
453 //! <b>Complexity</b>: Logarithmic.
insert(BOOST_MOVE_MACRO_RV_REF (value_type)x)454 std::pair<iterator,bool> insert(BOOST_MOVE_MACRO_RV_REF(value_type) x)
455 { return m_tree.insert_unique(BOOST_CONTAINER_MOVE_NAMESPACE::move(x)); }
456
457 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
458 //! no element in the container with key equivalent to the key of x.
459 //! p is a hint pointing to where the insert should start to search.
460 //!
461 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
462 //! to the key of x.
463 //!
464 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
465 //! is inserted right before p.
insert(iterator position,const value_type & x)466 iterator insert(iterator position, const value_type& x)
467 { return m_tree.insert_unique(position, x); }
468
469 //! <b>Effects</b>: Move constructs a new value from x if and only if there is
470 //! no element in the container with key equivalent to the key of x.
471 //! p is a hint pointing to where the insert should start to search.
472 //!
473 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
474 //! to the key of x.
475 //!
476 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
477 //! is inserted right before p.
insert(iterator position,BOOST_MOVE_MACRO_RV_REF (nonconst_value_type)x)478 iterator insert(iterator position, BOOST_MOVE_MACRO_RV_REF(nonconst_value_type) x)
479 { return m_tree.insert_unique(position, BOOST_CONTAINER_MOVE_NAMESPACE::move(x)); }
480
481 //! <b>Effects</b>: Move constructs a new value from x if and only if there is
482 //! no element in the container with key equivalent to the key of x.
483 //! p is a hint pointing to where the insert should start to search.
484 //!
485 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
486 //! to the key of x.
487 //!
488 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
489 //! is inserted right before p.
insert(iterator position,BOOST_MOVE_MACRO_RV_REF (nonconst_impl_value_type)x)490 iterator insert(iterator position, BOOST_MOVE_MACRO_RV_REF(nonconst_impl_value_type) x)
491 { return m_tree.insert_unique(position, BOOST_CONTAINER_MOVE_NAMESPACE::move(x)); }
492
493 //! <b>Effects</b>: Inserts a copy of x in the container.
494 //! p is a hint pointing to where the insert should start to search.
495 //!
496 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
497 //!
498 //! <b>Complexity</b>: Logarithmic.
insert(iterator position,const nonconst_value_type & x)499 iterator insert(iterator position, const nonconst_value_type& x)
500 { return m_tree.insert_unique(position, x); }
501
502 //! <b>Effects</b>: Inserts an element move constructed from x in the container.
503 //! p is a hint pointing to where the insert should start to search.
504 //!
505 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
506 //!
507 //! <b>Complexity</b>: Logarithmic.
insert(iterator position,BOOST_MOVE_MACRO_RV_REF (value_type)x)508 iterator insert(iterator position, BOOST_MOVE_MACRO_RV_REF(value_type) x)
509 { return m_tree.insert_unique(position, BOOST_CONTAINER_MOVE_NAMESPACE::move(x)); }
510
511 //! <b>Requires</b>: i, j are not iterators into *this.
512 //!
513 //! <b>Effects</b>: inserts each element from the range [i,j) if and only
514 //! if there is no element with key equivalent to the key of that element.
515 //!
516 //! <b>Complexity</b>: N log(size()+N) (N is the distance from i to j)
517 template <class InputIterator>
insert(InputIterator first,InputIterator last)518 void insert(InputIterator first, InputIterator last)
519 { m_tree.insert_unique(first, last); }
520
521 #if defined(BOOST_CONTAINERS_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
522
523 //! <b>Effects</b>: Inserts an object of type T constructed with
524 //! std::forward<Args>(args)... in the container if and only if there is
525 //! no element in the container with an equivalent key.
526 //! p is a hint pointing to where the insert should start to search.
527 //!
528 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
529 //! to the key of x.
530 //!
531 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
532 //! is inserted right before p.
533 template <class... Args>
emplace(Args &&...args)534 iterator emplace(Args&&... args)
535 { return m_tree.emplace_unique(BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...); }
536
537 //! <b>Effects</b>: Inserts an object of type T constructed with
538 //! std::forward<Args>(args)... in the container if and only if there is
539 //! no element in the container with an equivalent key.
540 //! p is a hint pointing to where the insert should start to search.
541 //!
542 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
543 //! to the key of x.
544 //!
545 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
546 //! is inserted right before p.
547 template <class... Args>
emplace_hint(const_iterator hint,Args &&...args)548 iterator emplace_hint(const_iterator hint, Args&&... args)
549 { return m_tree.emplace_hint_unique(hint, BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...); }
550
551 #else //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING
552
emplace()553 iterator emplace()
554 { return m_tree.emplace_unique(); }
555
emplace_hint(const_iterator hint)556 iterator emplace_hint(const_iterator hint)
557 { return m_tree.emplace_hint_unique(hint); }
558
559 #define BOOST_PP_LOCAL_MACRO(n) \
560 template<BOOST_PP_ENUM_PARAMS(n, class P)> \
561 iterator emplace(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \
562 { return m_tree.emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); } \
563 \
564 template<BOOST_PP_ENUM_PARAMS(n, class P)> \
565 iterator emplace_hint(const_iterator hint, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \
566 { return m_tree.emplace_hint_unique(hint, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _));}\
567 //!
568 #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS)
569 #include BOOST_PP_LOCAL_ITERATE()
570
571 #endif //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING
572
573 //! <b>Effects</b>: Erases the element pointed to by position.
574 //!
575 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
576 //! following q prior to the element being erased. If no such element exists,
577 //! returns end().
578 //!
579 //! <b>Complexity</b>: Amortized constant time
erase(const_iterator position)580 iterator erase(const_iterator position)
581 { return m_tree.erase(position); }
582
583 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
584 //!
585 //! <b>Returns</b>: Returns the number of erased elements.
586 //!
587 //! <b>Complexity</b>: log(size()) + count(k)
erase(const key_type & x)588 size_type erase(const key_type& x)
589 { return m_tree.erase(x); }
590
591 //! <b>Effects</b>: Erases all the elements in the range [first, last).
592 //!
593 //! <b>Returns</b>: Returns last.
594 //!
595 //! <b>Complexity</b>: log(size())+N where N is the distance from first to last.
erase(const_iterator first,const_iterator last)596 iterator erase(const_iterator first, const_iterator last)
597 { return m_tree.erase(first, last); }
598
599 //! <b>Effects</b>: erase(a.begin(),a.end()).
600 //!
601 //! <b>Postcondition</b>: size() == 0.
602 //!
603 //! <b>Complexity</b>: linear in size().
clear()604 void clear()
605 { m_tree.clear(); }
606
607 //! <b>Returns</b>: An iterator pointing to an element with the key
608 //! equivalent to x, or end() if such an element is not found.
609 //!
610 //! <b>Complexity</b>: Logarithmic.
find(const key_type & x)611 iterator find(const key_type& x)
612 { return m_tree.find(x); }
613
614 //! <b>Returns</b>: A const_iterator pointing to an element with the key
615 //! equivalent to x, or end() if such an element is not found.
616 //!
617 //! <b>Complexity</b>: Logarithmic.
find(const key_type & x) const618 const_iterator find(const key_type& x) const
619 { return m_tree.find(x); }
620
621 //! <b>Returns</b>: The number of elements with key equivalent to x.
622 //!
623 //! <b>Complexity</b>: log(size())+count(k)
count(const key_type & x) const624 size_type count(const key_type& x) const
625 { return m_tree.find(x) == m_tree.end() ? 0 : 1; }
626
627 //! <b>Returns</b>: An iterator pointing to the first element with key not less
628 //! than k, or a.end() if such an element is not found.
629 //!
630 //! <b>Complexity</b>: Logarithmic
lower_bound(const key_type & x)631 iterator lower_bound(const key_type& x)
632 { return m_tree.lower_bound(x); }
633
634 //! <b>Returns</b>: A const iterator pointing to the first element with key not
635 //! less than k, or a.end() if such an element is not found.
636 //!
637 //! <b>Complexity</b>: Logarithmic
lower_bound(const key_type & x) const638 const_iterator lower_bound(const key_type& x) const
639 { return m_tree.lower_bound(x); }
640
641 //! <b>Returns</b>: An iterator pointing to the first element with key not less
642 //! than x, or end() if such an element is not found.
643 //!
644 //! <b>Complexity</b>: Logarithmic
upper_bound(const key_type & x)645 iterator upper_bound(const key_type& x)
646 { return m_tree.upper_bound(x); }
647
648 //! <b>Returns</b>: A const iterator pointing to the first element with key not
649 //! less than x, or end() if such an element is not found.
650 //!
651 //! <b>Complexity</b>: Logarithmic
upper_bound(const key_type & x) const652 const_iterator upper_bound(const key_type& x) const
653 { return m_tree.upper_bound(x); }
654
655 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
656 //!
657 //! <b>Complexity</b>: Logarithmic
equal_range(const key_type & x)658 std::pair<iterator,iterator> equal_range(const key_type& x)
659 { return m_tree.equal_range(x); }
660
661 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
662 //!
663 //! <b>Complexity</b>: Logarithmic
equal_range(const key_type & x) const664 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const
665 { return m_tree.equal_range(x); }
666
667 /// @cond
668 template <class K1, class T1, class C1, class A1>
669 friend bool operator== (const map<K1, T1, C1, A1>&,
670 const map<K1, T1, C1, A1>&);
671 template <class K1, class T1, class C1, class A1>
672 friend bool operator< (const map<K1, T1, C1, A1>&,
673 const map<K1, T1, C1, A1>&);
674 /// @endcond
675 };
676
677 template <class Key, class T, class Pred, class Alloc>
operator ==(const map<Key,T,Pred,Alloc> & x,const map<Key,T,Pred,Alloc> & y)678 inline bool operator==(const map<Key,T,Pred,Alloc>& x,
679 const map<Key,T,Pred,Alloc>& y)
680 { return x.m_tree == y.m_tree; }
681
682 template <class Key, class T, class Pred, class Alloc>
operator <(const map<Key,T,Pred,Alloc> & x,const map<Key,T,Pred,Alloc> & y)683 inline bool operator<(const map<Key,T,Pred,Alloc>& x,
684 const map<Key,T,Pred,Alloc>& y)
685 { return x.m_tree < y.m_tree; }
686
687 template <class Key, class T, class Pred, class Alloc>
operator !=(const map<Key,T,Pred,Alloc> & x,const map<Key,T,Pred,Alloc> & y)688 inline bool operator!=(const map<Key,T,Pred,Alloc>& x,
689 const map<Key,T,Pred,Alloc>& y)
690 { return !(x == y); }
691
692 template <class Key, class T, class Pred, class Alloc>
operator >(const map<Key,T,Pred,Alloc> & x,const map<Key,T,Pred,Alloc> & y)693 inline bool operator>(const map<Key,T,Pred,Alloc>& x,
694 const map<Key,T,Pred,Alloc>& y)
695 { return y < x; }
696
697 template <class Key, class T, class Pred, class Alloc>
operator <=(const map<Key,T,Pred,Alloc> & x,const map<Key,T,Pred,Alloc> & y)698 inline bool operator<=(const map<Key,T,Pred,Alloc>& x,
699 const map<Key,T,Pred,Alloc>& y)
700 { return !(y < x); }
701
702 template <class Key, class T, class Pred, class Alloc>
operator >=(const map<Key,T,Pred,Alloc> & x,const map<Key,T,Pred,Alloc> & y)703 inline bool operator>=(const map<Key,T,Pred,Alloc>& x,
704 const map<Key,T,Pred,Alloc>& y)
705 { return !(x < y); }
706
707 template <class Key, class T, class Pred, class Alloc>
swap(map<Key,T,Pred,Alloc> & x,map<Key,T,Pred,Alloc> & y)708 inline void swap(map<Key,T,Pred,Alloc>& x, map<Key,T,Pred,Alloc>& y)
709 { x.swap(y); }
710
711 /// @cond
712
713 // Forward declaration of operators < and ==, needed for friend declaration.
714
715 template <class Key, class T, class Pred, class Alloc>
716 inline bool operator==(const multimap<Key,T,Pred,Alloc>& x,
717 const multimap<Key,T,Pred,Alloc>& y);
718
719 template <class Key, class T, class Pred, class Alloc>
720 inline bool operator<(const multimap<Key,T,Pred,Alloc>& x,
721 const multimap<Key,T,Pred,Alloc>& y);
722
723 } //namespace container {
724 /*
725 //!has_trivial_destructor_after_move<> == true_type
726 //!specialization for optimizations
727 template <class K, class T, class C, class A>
728 struct has_trivial_destructor_after_move<boost::container::map<K, T, C, A> >
729 {
730 static const bool value = has_trivial_destructor<A>::value && has_trivial_destructor<C>::value;
731 };
732 */
733 namespace container {
734
735 /// @endcond
736
737 //! A multimap is a kind of associative container that supports equivalent keys
738 //! (possibly containing multiple copies of the same key value) and provides for
739 //! fast retrieval of values of another type T based on the keys. The multimap class
740 //! supports bidirectional iterators.
741 //!
742 //! A multimap satisfies all of the requirements of a container and of a reversible
743 //! container and of an associative container. For a
744 //! map<Key,T> the key_type is Key and the value_type is std::pair<const Key,T>.
745 //!
746 //! Pred is the ordering function for Keys (e.g. <i>std::less<Key></i>).
747 //!
748 //! Alloc is the allocator to allocate the value_types
749 //!(e.g. <i>allocator< std::pair<<b>const</b> Key, T> ></i>).
750 template <class Key, class T, class Pred, class Alloc>
751 class multimap
752 {
753 /// @cond
754 private:
755 BOOST_MOVE_MACRO_COPYABLE_AND_MOVABLE(multimap)
756 typedef containers_detail::rbtree<Key,
757 std::pair<const Key, T>,
758 containers_detail::select1st< std::pair<const Key, T> >,
759 Pred,
760 Alloc> tree_t;
761 tree_t m_tree; // red-black tree representing map
762 /// @endcond
763
764 public:
765
766 // typedefs:
767 typedef typename tree_t::key_type key_type;
768 typedef typename tree_t::value_type value_type;
769 typedef typename tree_t::pointer pointer;
770 typedef typename tree_t::const_pointer const_pointer;
771 typedef typename tree_t::reference reference;
772 typedef typename tree_t::const_reference const_reference;
773 typedef T mapped_type;
774 typedef Pred key_compare;
775 typedef typename tree_t::iterator iterator;
776 typedef typename tree_t::const_iterator const_iterator;
777 typedef typename tree_t::reverse_iterator reverse_iterator;
778 typedef typename tree_t::const_reverse_iterator const_reverse_iterator;
779 typedef typename tree_t::size_type size_type;
780 typedef typename tree_t::difference_type difference_type;
781 typedef typename tree_t::allocator_type allocator_type;
782 typedef typename tree_t::stored_allocator_type stored_allocator_type;
783 typedef std::pair<key_type, mapped_type> nonconst_value_type;
784 typedef containers_detail::pair
785 <key_type, mapped_type> nonconst_impl_value_type;
786
787 /// @cond
788 class value_compare_impl
789 : public Pred,
790 public std::binary_function<value_type, value_type, bool>
791 {
792 friend class multimap<Key,T,Pred,Alloc>;
793 protected :
value_compare_impl(const Pred & c)794 value_compare_impl(const Pred &c) : Pred(c) {}
795 public:
operator ()(const value_type & x,const value_type & y) const796 bool operator()(const value_type& x, const value_type& y) const {
797 return Pred::operator()(x.first, y.first);
798 }
799 };
800 /// @endcond
801 typedef value_compare_impl value_compare;
802
803 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison
804 //! object and allocator.
805 //!
806 //! <b>Complexity</b>: Constant.
multimap(const Pred & comp=Pred (),const allocator_type & a=allocator_type ())807 explicit multimap(const Pred& comp = Pred(),
808 const allocator_type& a = allocator_type())
809 : m_tree(comp, a)
810 {}
811
812 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object
813 //! and allocator, and inserts elements from the range [first ,last ).
814 //!
815 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
816 //! comp and otherwise N logN, where N is last - first.
817 template <class InputIterator>
multimap(InputIterator first,InputIterator last,const Pred & comp=Pred (),const allocator_type & a=allocator_type ())818 multimap(InputIterator first, InputIterator last,
819 const Pred& comp = Pred(),
820 const allocator_type& a = allocator_type())
821 : m_tree(first, last, comp, a, false)
822 {}
823
824 //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and
825 //! allocator, and inserts elements from the ordered range [first ,last). This function
826 //! is more efficient than the normal range creation for ordered ranges.
827 //!
828 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
829 //!
830 //! <b>Complexity</b>: Linear in N.
831 template <class InputIterator>
multimap(ordered_range_t ordered_range,InputIterator first,InputIterator last,const Pred & comp=Pred (),const allocator_type & a=allocator_type ())832 multimap(ordered_range_t ordered_range, InputIterator first, InputIterator last, const Pred& comp = Pred(),
833 const allocator_type& a = allocator_type())
834 : m_tree(ordered_range, first, last, comp, a)
835 {}
836
837
838 //! <b>Effects</b>: Copy constructs a multimap.
839 //!
840 //! <b>Complexity</b>: Linear in x.size().
multimap(const multimap<Key,T,Pred,Alloc> & x)841 multimap(const multimap<Key,T,Pred,Alloc>& x)
842 : m_tree(x.m_tree)
843 {}
844
845 //! <b>Effects</b>: Move constructs a multimap. Constructs *this using x's resources.
846 //!
847 //! <b>Complexity</b>: Construct.
848 //!
849 //! <b>Postcondition</b>: x is emptied.
multimap(BOOST_MOVE_MACRO_RV_REF (multimap)x)850 multimap(BOOST_MOVE_MACRO_RV_REF(multimap) x)
851 : m_tree(BOOST_CONTAINER_MOVE_NAMESPACE::move(x.m_tree))
852 {}
853
854 //! <b>Effects</b>: Makes *this a copy of x.
855 //!
856 //! <b>Complexity</b>: Linear in x.size().
operator =(BOOST_MOVE_MACRO_COPY_ASSIGN_REF (multimap)x)857 multimap& operator=(BOOST_MOVE_MACRO_COPY_ASSIGN_REF(multimap) x)
858 { m_tree = x.m_tree; return *this; }
859
860 //! <b>Effects</b>: this->swap(x.get()).
861 //!
862 //! <b>Complexity</b>: Constant.
operator =(BOOST_MOVE_MACRO_RV_REF (multimap)x)863 multimap& operator=(BOOST_MOVE_MACRO_RV_REF(multimap) x)
864 { m_tree = BOOST_CONTAINER_MOVE_NAMESPACE::move(x.m_tree); return *this; }
865
866 //! <b>Effects</b>: Returns the comparison object out
867 //! of which a was constructed.
868 //!
869 //! <b>Complexity</b>: Constant.
key_comp() const870 key_compare key_comp() const
871 { return m_tree.key_comp(); }
872
873 //! <b>Effects</b>: Returns an object of value_compare constructed out
874 //! of the comparison object.
875 //!
876 //! <b>Complexity</b>: Constant.
value_comp() const877 value_compare value_comp() const
878 { return value_compare(m_tree.key_comp()); }
879
880 //! <b>Effects</b>: Returns a copy of the Allocator that
881 //! was passed to the object's constructor.
882 //!
883 //! <b>Complexity</b>: Constant.
get_allocator() const884 allocator_type get_allocator() const
885 { return m_tree.get_allocator(); }
886
get_stored_allocator() const887 const stored_allocator_type &get_stored_allocator() const
888 { return m_tree.get_stored_allocator(); }
889
get_stored_allocator()890 stored_allocator_type &get_stored_allocator()
891 { return m_tree.get_stored_allocator(); }
892
893 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
894 //!
895 //! <b>Throws</b>: Nothing.
896 //!
897 //! <b>Complexity</b>: Constant.
begin()898 iterator begin()
899 { return m_tree.begin(); }
900
901 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
902 //!
903 //! <b>Throws</b>: Nothing.
904 //!
905 //! <b>Complexity</b>: Constant.
begin() const906 const_iterator begin() const
907 { return m_tree.begin(); }
908
909 //! <b>Effects</b>: Returns an iterator to the end of the container.
910 //!
911 //! <b>Throws</b>: Nothing.
912 //!
913 //! <b>Complexity</b>: Constant.
end()914 iterator end()
915 { return m_tree.end(); }
916
917 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
918 //!
919 //! <b>Throws</b>: Nothing.
920 //!
921 //! <b>Complexity</b>: Constant.
end() const922 const_iterator end() const
923 { return m_tree.end(); }
924
925 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
926 //! of the reversed container.
927 //!
928 //! <b>Throws</b>: Nothing.
929 //!
930 //! <b>Complexity</b>: Constant.
rbegin()931 reverse_iterator rbegin()
932 { return m_tree.rbegin(); }
933
934 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
935 //! of the reversed container.
936 //!
937 //! <b>Throws</b>: Nothing.
938 //!
939 //! <b>Complexity</b>: Constant.
rbegin() const940 const_reverse_iterator rbegin() const
941 { return m_tree.rbegin(); }
942
943 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
944 //! of the reversed container.
945 //!
946 //! <b>Throws</b>: Nothing.
947 //!
948 //! <b>Complexity</b>: Constant.
rend()949 reverse_iterator rend()
950 { return m_tree.rend(); }
951
952 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
953 //! of the reversed container.
954 //!
955 //! <b>Throws</b>: Nothing.
956 //!
957 //! <b>Complexity</b>: Constant.
rend() const958 const_reverse_iterator rend() const
959 { return m_tree.rend(); }
960
961 //! <b>Effects</b>: Returns true if the container contains no elements.
962 //!
963 //! <b>Throws</b>: Nothing.
964 //!
965 //! <b>Complexity</b>: Constant.
empty() const966 bool empty() const
967 { return m_tree.empty(); }
968
969 //! <b>Effects</b>: Returns the number of the elements contained in the container.
970 //!
971 //! <b>Throws</b>: Nothing.
972 //!
973 //! <b>Complexity</b>: Constant.
size() const974 size_type size() const
975 { return m_tree.size(); }
976
977 //! <b>Effects</b>: Returns the largest possible size of the container.
978 //!
979 //! <b>Throws</b>: Nothing.
980 //!
981 //! <b>Complexity</b>: Constant.
max_size() const982 size_type max_size() const
983 { return m_tree.max_size(); }
984
985 //! <b>Effects</b>: Swaps the contents of *this and x.
986 //! If this->allocator_type() != x.allocator_type() allocators are also swapped.
987 //!
988 //! <b>Throws</b>: Nothing.
989 //!
990 //! <b>Complexity</b>: Constant.
swap(multimap & x)991 void swap(multimap& x)
992 { m_tree.swap(x.m_tree); }
993
994 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
995 //! newly inserted element.
996 //!
997 //! <b>Complexity</b>: Logarithmic.
insert(const value_type & x)998 iterator insert(const value_type& x)
999 { return m_tree.insert_equal(x); }
1000
1001 //! <b>Effects</b>: Inserts a new value constructed from x and returns
1002 //! the iterator pointing to the newly inserted element.
1003 //!
1004 //! <b>Complexity</b>: Logarithmic.
insert(const nonconst_value_type & x)1005 iterator insert(const nonconst_value_type& x)
1006 { return m_tree.insert_equal(x); }
1007
1008 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
1009 //! the iterator pointing to the newly inserted element.
1010 //!
1011 //! <b>Complexity</b>: Logarithmic.
insert(BOOST_MOVE_MACRO_RV_REF (nonconst_value_type)x)1012 iterator insert(BOOST_MOVE_MACRO_RV_REF(nonconst_value_type) x)
1013 { return m_tree.insert_equal(BOOST_CONTAINER_MOVE_NAMESPACE::move(x)); }
1014
1015 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
1016 //! the iterator pointing to the newly inserted element.
1017 //!
1018 //! <b>Complexity</b>: Logarithmic.
insert(BOOST_MOVE_MACRO_RV_REF (nonconst_impl_value_type)x)1019 iterator insert(BOOST_MOVE_MACRO_RV_REF(nonconst_impl_value_type) x)
1020 { return m_tree.insert_equal(BOOST_CONTAINER_MOVE_NAMESPACE::move(x)); }
1021
1022 //! <b>Effects</b>: Inserts a copy of x in the container.
1023 //! p is a hint pointing to where the insert should start to search.
1024 //!
1025 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1026 //! to the key of x.
1027 //!
1028 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1029 //! is inserted right before p.
insert(iterator position,const value_type & x)1030 iterator insert(iterator position, const value_type& x)
1031 { return m_tree.insert_equal(position, x); }
1032
1033 //! <b>Effects</b>: Inserts a new value constructed from x in the container.
1034 //! p is a hint pointing to where the insert should start to search.
1035 //!
1036 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1037 //! to the key of x.
1038 //!
1039 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1040 //! is inserted right before p.
insert(iterator position,const nonconst_value_type & x)1041 iterator insert(iterator position, const nonconst_value_type& x)
1042 { return m_tree.insert_equal(position, x); }
1043
1044 //! <b>Effects</b>: Inserts a new value move constructed from x in the container.
1045 //! p is a hint pointing to where the insert should start to search.
1046 //!
1047 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1048 //! to the key of x.
1049 //!
1050 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1051 //! is inserted right before p.
insert(iterator position,BOOST_MOVE_MACRO_RV_REF (nonconst_value_type)x)1052 iterator insert(iterator position, BOOST_MOVE_MACRO_RV_REF(nonconst_value_type) x)
1053 { return m_tree.insert_equal(position, BOOST_CONTAINER_MOVE_NAMESPACE::move(x)); }
1054
1055 //! <b>Effects</b>: Inserts a new value move constructed from x in the container.
1056 //! p is a hint pointing to where the insert should start to search.
1057 //!
1058 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1059 //! to the key of x.
1060 //!
1061 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1062 //! is inserted right before p.
insert(iterator position,BOOST_MOVE_MACRO_RV_REF (nonconst_impl_value_type)x)1063 iterator insert(iterator position, BOOST_MOVE_MACRO_RV_REF(nonconst_impl_value_type) x)
1064 { return m_tree.insert_equal(position, BOOST_CONTAINER_MOVE_NAMESPACE::move(x)); }
1065
1066 //! <b>Requires</b>: i, j are not iterators into *this.
1067 //!
1068 //! <b>Effects</b>: inserts each element from the range [i,j) .
1069 //!
1070 //! <b>Complexity</b>: N log(size()+N) (N is the distance from i to j)
1071 template <class InputIterator>
insert(InputIterator first,InputIterator last)1072 void insert(InputIterator first, InputIterator last)
1073 { m_tree.insert_equal(first, last); }
1074
1075 #if defined(BOOST_CONTAINERS_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1076
1077 //! <b>Effects</b>: Inserts an object of type T constructed with
1078 //! std::forward<Args>(args)... in the container.
1079 //! p is a hint pointing to where the insert should start to search.
1080 //!
1081 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1082 //! to the key of x.
1083 //!
1084 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1085 //! is inserted right before p.
1086 template <class... Args>
emplace(Args &&...args)1087 iterator emplace(Args&&... args)
1088 { return m_tree.emplace_equal(BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...); }
1089
1090 //! <b>Effects</b>: Inserts an object of type T constructed with
1091 //! std::forward<Args>(args)... in the container.
1092 //! p is a hint pointing to where the insert should start to search.
1093 //!
1094 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1095 //! to the key of x.
1096 //!
1097 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1098 //! is inserted right before p.
1099 template <class... Args>
emplace_hint(const_iterator hint,Args &&...args)1100 iterator emplace_hint(const_iterator hint, Args&&... args)
1101 { return m_tree.emplace_hint_equal(hint, BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...); }
1102
1103 #else //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING
1104
emplace()1105 iterator emplace()
1106 { return m_tree.emplace_equal(); }
1107
emplace_hint(const_iterator hint)1108 iterator emplace_hint(const_iterator hint)
1109 { return m_tree.emplace_hint_equal(hint); }
1110
1111 #define BOOST_PP_LOCAL_MACRO(n) \
1112 template<BOOST_PP_ENUM_PARAMS(n, class P)> \
1113 iterator emplace(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \
1114 { return m_tree.emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); } \
1115 \
1116 template<BOOST_PP_ENUM_PARAMS(n, class P)> \
1117 iterator emplace_hint(const_iterator hint, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \
1118 { return m_tree.emplace_hint_equal(hint, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); }\
1119 //!
1120 #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS)
1121 #include BOOST_PP_LOCAL_ITERATE()
1122
1123 #endif //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING
1124
1125 //! <b>Effects</b>: Erases the element pointed to by position.
1126 //!
1127 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
1128 //! following q prior to the element being erased. If no such element exists,
1129 //! returns end().
1130 //!
1131 //! <b>Complexity</b>: Amortized constant time
erase(const_iterator position)1132 iterator erase(const_iterator position)
1133 { return m_tree.erase(position); }
1134
1135 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
1136 //!
1137 //! <b>Returns</b>: Returns the number of erased elements.
1138 //!
1139 //! <b>Complexity</b>: log(size()) + count(k)
erase(const key_type & x)1140 size_type erase(const key_type& x)
1141 { return m_tree.erase(x); }
1142
1143 //! <b>Effects</b>: Erases all the elements in the range [first, last).
1144 //!
1145 //! <b>Returns</b>: Returns last.
1146 //!
1147 //! <b>Complexity</b>: log(size())+N where N is the distance from first to last.
erase(const_iterator first,const_iterator last)1148 iterator erase(const_iterator first, const_iterator last)
1149 { return m_tree.erase(first, last); }
1150
1151 //! <b>Effects</b>: erase(a.begin(),a.end()).
1152 //!
1153 //! <b>Postcondition</b>: size() == 0.
1154 //!
1155 //! <b>Complexity</b>: linear in size().
clear()1156 void clear()
1157 { m_tree.clear(); }
1158
1159 //! <b>Returns</b>: An iterator pointing to an element with the key
1160 //! equivalent to x, or end() if such an element is not found.
1161 //!
1162 //! <b>Complexity</b>: Logarithmic.
find(const key_type & x)1163 iterator find(const key_type& x)
1164 { return m_tree.find(x); }
1165
1166 //! <b>Returns</b>: A const iterator pointing to an element with the key
1167 //! equivalent to x, or end() if such an element is not found.
1168 //!
1169 //! <b>Complexity</b>: Logarithmic.
find(const key_type & x) const1170 const_iterator find(const key_type& x) const
1171 { return m_tree.find(x); }
1172
1173 //! <b>Returns</b>: The number of elements with key equivalent to x.
1174 //!
1175 //! <b>Complexity</b>: log(size())+count(k)
count(const key_type & x) const1176 size_type count(const key_type& x) const
1177 { return m_tree.count(x); }
1178
1179 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1180 //! than k, or a.end() if such an element is not found.
1181 //!
1182 //! <b>Complexity</b>: Logarithmic
lower_bound(const key_type & x)1183 iterator lower_bound(const key_type& x)
1184 {return m_tree.lower_bound(x); }
1185
1186 //! <b>Returns</b>: A const iterator pointing to the first element with key not
1187 //! less than k, or a.end() if such an element is not found.
1188 //!
1189 //! <b>Complexity</b>: Logarithmic
lower_bound(const key_type & x) const1190 const_iterator lower_bound(const key_type& x) const
1191 { return m_tree.lower_bound(x); }
1192
1193 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1194 //! than x, or end() if such an element is not found.
1195 //!
1196 //! <b>Complexity</b>: Logarithmic
upper_bound(const key_type & x)1197 iterator upper_bound(const key_type& x)
1198 { return m_tree.upper_bound(x); }
1199
1200 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1201 //!
1202 //! <b>Complexity</b>: Logarithmic
equal_range(const key_type & x)1203 std::pair<iterator,iterator> equal_range(const key_type& x)
1204 { return m_tree.equal_range(x); }
1205
1206 //! <b>Returns</b>: A const iterator pointing to the first element with key not
1207 //! less than x, or end() if such an element is not found.
1208 //!
1209 //! <b>Complexity</b>: Logarithmic
upper_bound(const key_type & x) const1210 const_iterator upper_bound(const key_type& x) const
1211 { return m_tree.upper_bound(x); }
1212
1213 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1214 //!
1215 //! <b>Complexity</b>: Logarithmic
1216 std::pair<const_iterator,const_iterator>
equal_range(const key_type & x) const1217 equal_range(const key_type& x) const
1218 { return m_tree.equal_range(x); }
1219
1220 /// @cond
1221 template <class K1, class T1, class C1, class A1>
1222 friend bool operator== (const multimap<K1, T1, C1, A1>& x,
1223 const multimap<K1, T1, C1, A1>& y);
1224
1225 template <class K1, class T1, class C1, class A1>
1226 friend bool operator< (const multimap<K1, T1, C1, A1>& x,
1227 const multimap<K1, T1, C1, A1>& y);
1228 /// @endcond
1229 };
1230
1231 template <class Key, class T, class Pred, class Alloc>
operator ==(const multimap<Key,T,Pred,Alloc> & x,const multimap<Key,T,Pred,Alloc> & y)1232 inline bool operator==(const multimap<Key,T,Pred,Alloc>& x,
1233 const multimap<Key,T,Pred,Alloc>& y)
1234 { return x.m_tree == y.m_tree; }
1235
1236 template <class Key, class T, class Pred, class Alloc>
operator <(const multimap<Key,T,Pred,Alloc> & x,const multimap<Key,T,Pred,Alloc> & y)1237 inline bool operator<(const multimap<Key,T,Pred,Alloc>& x,
1238 const multimap<Key,T,Pred,Alloc>& y)
1239 { return x.m_tree < y.m_tree; }
1240
1241 template <class Key, class T, class Pred, class Alloc>
operator !=(const multimap<Key,T,Pred,Alloc> & x,const multimap<Key,T,Pred,Alloc> & y)1242 inline bool operator!=(const multimap<Key,T,Pred,Alloc>& x,
1243 const multimap<Key,T,Pred,Alloc>& y)
1244 { return !(x == y); }
1245
1246 template <class Key, class T, class Pred, class Alloc>
operator >(const multimap<Key,T,Pred,Alloc> & x,const multimap<Key,T,Pred,Alloc> & y)1247 inline bool operator>(const multimap<Key,T,Pred,Alloc>& x,
1248 const multimap<Key,T,Pred,Alloc>& y)
1249 { return y < x; }
1250
1251 template <class Key, class T, class Pred, class Alloc>
operator <=(const multimap<Key,T,Pred,Alloc> & x,const multimap<Key,T,Pred,Alloc> & y)1252 inline bool operator<=(const multimap<Key,T,Pred,Alloc>& x,
1253 const multimap<Key,T,Pred,Alloc>& y)
1254 { return !(y < x); }
1255
1256 template <class Key, class T, class Pred, class Alloc>
operator >=(const multimap<Key,T,Pred,Alloc> & x,const multimap<Key,T,Pred,Alloc> & y)1257 inline bool operator>=(const multimap<Key,T,Pred,Alloc>& x,
1258 const multimap<Key,T,Pred,Alloc>& y)
1259 { return !(x < y); }
1260
1261 template <class Key, class T, class Pred, class Alloc>
swap(multimap<Key,T,Pred,Alloc> & x,multimap<Key,T,Pred,Alloc> & y)1262 inline void swap(multimap<Key,T,Pred,Alloc>& x, multimap<Key,T,Pred,Alloc>& y)
1263 { x.swap(y); }
1264
1265 /// @cond
1266
1267 } //namespace container {
1268 /*
1269 //!has_trivial_destructor_after_move<> == true_type
1270 //!specialization for optimizations
1271 template <class K, class T, class C, class A>
1272 struct has_trivial_destructor_after_move<boost::container::multimap<K, T, C, A> >
1273 {
1274 static const bool value = has_trivial_destructor<A>::value && has_trivial_destructor<C>::value;
1275 };
1276 */
1277 namespace container {
1278
1279 /// @endcond
1280
1281 }}
1282
1283 #include INCLUDE_BOOST_CONTAINER_DETAIL_CONFIG_END_HPP
1284
1285 #endif /* BOOST_CONTAINERS_MAP_HPP */
1286
1287