1// Multimap implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2004, 2005 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 2, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30/* 31 * 32 * Copyright (c) 1994 33 * Hewlett-Packard Company 34 * 35 * Permission to use, copy, modify, distribute and sell this software 36 * and its documentation for any purpose is hereby granted without fee, 37 * provided that the above copyright notice appear in all copies and 38 * that both that copyright notice and this permission notice appear 39 * in supporting documentation. Hewlett-Packard Company makes no 40 * representations about the suitability of this software for any 41 * purpose. It is provided "as is" without express or implied warranty. 42 * 43 * 44 * Copyright (c) 1996,1997 45 * Silicon Graphics Computer Systems, Inc. 46 * 47 * Permission to use, copy, modify, distribute and sell this software 48 * and its documentation for any purpose is hereby granted without fee, 49 * provided that the above copyright notice appear in all copies and 50 * that both that copyright notice and this permission notice appear 51 * in supporting documentation. Silicon Graphics makes no 52 * representations about the suitability of this software for any 53 * purpose. It is provided "as is" without express or implied warranty. 54 */ 55 56/** @file stl_multimap.h 57 * This is an internal header file, included by other library headers. 58 * You should not attempt to use it directly. 59 */ 60 61#ifndef _MULTIMAP_H 62#define _MULTIMAP_H 1 63 64#include <bits/concept_check.h> 65 66namespace _GLIBCXX_STD 67{ 68 // Forward declaration of operators < and ==, needed for friend declaration. 69 70 template <typename _Key, typename _Tp, 71 typename _Compare = std::less<_Key>, 72 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 73 class multimap; 74 75 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 76 inline bool 77 operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 78 const multimap<_Key, _Tp, _Compare, _Alloc>& __y); 79 80 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 81 inline bool 82 operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 83 const multimap<_Key, _Tp, _Compare, _Alloc>& __y); 84 85 /** 86 * @brief A standard container made up of (key,value) pairs, which can be 87 * retrieved based on a key, in logarithmic time. 88 * 89 * @ingroup Containers 90 * @ingroup Assoc_containers 91 * 92 * Meets the requirements of a <a href="tables.html#65">container</a>, a 93 * <a href="tables.html#66">reversible container</a>, and an 94 * <a href="tables.html#69">associative container</a> (using equivalent 95 * keys). For a @c multimap<Key,T> the key_type is Key, the mapped_type 96 * is T, and the value_type is std::pair<const Key,T>. 97 * 98 * Multimaps support bidirectional iterators. 99 * 100 * @if maint 101 * The private tree data is declared exactly the same way for map and 102 * multimap; the distinction is made entirely in how the tree functions are 103 * called (*_unique versus *_equal, same as the standard). 104 * @endif 105 */ 106 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 107 class multimap 108 { 109 public: 110 typedef _Key key_type; 111 typedef _Tp mapped_type; 112 typedef std::pair<const _Key, _Tp> value_type; 113 typedef _Compare key_compare; 114 typedef _Alloc allocator_type; 115 116 private: 117 // concept requirements 118 typedef typename _Alloc::value_type _Alloc_value_type; 119 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 120 __glibcxx_class_requires4(_Compare, bool, _Key, _Key, 121 _BinaryFunctionConcept) 122 __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept) 123 124 public: 125 class value_compare 126 : public std::binary_function<value_type, value_type, bool> 127 { 128 friend class multimap<_Key, _Tp, _Compare, _Alloc>; 129 protected: 130 _Compare comp; 131 132 value_compare(_Compare __c) 133 : comp(__c) { } 134 135 public: 136 bool operator()(const value_type& __x, const value_type& __y) const 137 { return comp(__x.first, __y.first); } 138 }; 139 140 private: 141 /// @if maint This turns a red-black tree into a [multi]map. @endif 142 typedef typename _Alloc::template rebind<value_type>::other 143 _Pair_alloc_type; 144 145 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>, 146 key_compare, _Pair_alloc_type> _Rep_type; 147 /// @if maint The actual tree structure. @endif 148 _Rep_type _M_t; 149 150 public: 151 // many of these are specified differently in ISO, but the following are 152 // "functionally equivalent" 153 typedef typename _Pair_alloc_type::pointer pointer; 154 typedef typename _Pair_alloc_type::const_pointer const_pointer; 155 typedef typename _Pair_alloc_type::reference reference; 156 typedef typename _Pair_alloc_type::const_reference const_reference; 157 typedef typename _Rep_type::iterator iterator; 158 typedef typename _Rep_type::const_iterator const_iterator; 159 typedef typename _Rep_type::size_type size_type; 160 typedef typename _Rep_type::difference_type difference_type; 161 typedef typename _Rep_type::reverse_iterator reverse_iterator; 162 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 163 164 // [23.3.2] construct/copy/destroy 165 // (get_allocator() is also listed in this section) 166 /** 167 * @brief Default constructor creates no elements. 168 */ 169 multimap() 170 : _M_t(_Compare(), allocator_type()) { } 171 172 // for some reason this was made a separate function 173 /** 174 * @brief Default constructor creates no elements. 175 */ 176 explicit 177 multimap(const _Compare& __comp, 178 const allocator_type& __a = allocator_type()) 179 : _M_t(__comp, __a) { } 180 181 /** 182 * @brief %Multimap copy constructor. 183 * @param x A %multimap of identical element and allocator types. 184 * 185 * The newly-created %multimap uses a copy of the allocation object used 186 * by @a x. 187 */ 188 multimap(const multimap& __x) 189 : _M_t(__x._M_t) { } 190 191 /** 192 * @brief Builds a %multimap from a range. 193 * @param first An input iterator. 194 * @param last An input iterator. 195 * 196 * Create a %multimap consisting of copies of the elements from 197 * [first,last). This is linear in N if the range is already sorted, 198 * and NlogN otherwise (where N is distance(first,last)). 199 */ 200 template <typename _InputIterator> 201 multimap(_InputIterator __first, _InputIterator __last) 202 : _M_t(_Compare(), allocator_type()) 203 { _M_t.insert_equal(__first, __last); } 204 205 /** 206 * @brief Builds a %multimap from a range. 207 * @param first An input iterator. 208 * @param last An input iterator. 209 * @param comp A comparison functor. 210 * @param a An allocator object. 211 * 212 * Create a %multimap consisting of copies of the elements from 213 * [first,last). This is linear in N if the range is already sorted, 214 * and NlogN otherwise (where N is distance(first,last)). 215 */ 216 template <typename _InputIterator> 217 multimap(_InputIterator __first, _InputIterator __last, 218 const _Compare& __comp, 219 const allocator_type& __a = allocator_type()) 220 : _M_t(__comp, __a) 221 { _M_t.insert_equal(__first, __last); } 222 223 // FIXME There is no dtor declared, but we should have something generated 224 // by Doxygen. I don't know what tags to add to this paragraph to make 225 // that happen: 226 /** 227 * The dtor only erases the elements, and note that if the elements 228 * themselves are pointers, the pointed-to memory is not touched in any 229 * way. Managing the pointer is the user's responsibilty. 230 */ 231 232 /** 233 * @brief %Multimap assignment operator. 234 * @param x A %multimap of identical element and allocator types. 235 * 236 * All the elements of @a x are copied, but unlike the copy constructor, 237 * the allocator object is not copied. 238 */ 239 multimap& 240 operator=(const multimap& __x) 241 { 242 _M_t = __x._M_t; 243 return *this; 244 } 245 246 /// Get a copy of the memory allocation object. 247 allocator_type 248 get_allocator() const 249 { return _M_t.get_allocator(); } 250 251 // iterators 252 /** 253 * Returns a read/write iterator that points to the first pair in the 254 * %multimap. Iteration is done in ascending order according to the 255 * keys. 256 */ 257 iterator 258 begin() 259 { return _M_t.begin(); } 260 261 /** 262 * Returns a read-only (constant) iterator that points to the first pair 263 * in the %multimap. Iteration is done in ascending order according to 264 * the keys. 265 */ 266 const_iterator 267 begin() const 268 { return _M_t.begin(); } 269 270 /** 271 * Returns a read/write iterator that points one past the last pair in 272 * the %multimap. Iteration is done in ascending order according to the 273 * keys. 274 */ 275 iterator 276 end() 277 { return _M_t.end(); } 278 279 /** 280 * Returns a read-only (constant) iterator that points one past the last 281 * pair in the %multimap. Iteration is done in ascending order according 282 * to the keys. 283 */ 284 const_iterator 285 end() const 286 { return _M_t.end(); } 287 288 /** 289 * Returns a read/write reverse iterator that points to the last pair in 290 * the %multimap. Iteration is done in descending order according to the 291 * keys. 292 */ 293 reverse_iterator 294 rbegin() 295 { return _M_t.rbegin(); } 296 297 /** 298 * Returns a read-only (constant) reverse iterator that points to the 299 * last pair in the %multimap. Iteration is done in descending order 300 * according to the keys. 301 */ 302 const_reverse_iterator 303 rbegin() const 304 { return _M_t.rbegin(); } 305 306 /** 307 * Returns a read/write reverse iterator that points to one before the 308 * first pair in the %multimap. Iteration is done in descending order 309 * according to the keys. 310 */ 311 reverse_iterator 312 rend() 313 { return _M_t.rend(); } 314 315 /** 316 * Returns a read-only (constant) reverse iterator that points to one 317 * before the first pair in the %multimap. Iteration is done in 318 * descending order according to the keys. 319 */ 320 const_reverse_iterator 321 rend() const 322 { return _M_t.rend(); } 323 324 // capacity 325 /** Returns true if the %multimap is empty. */ 326 bool 327 empty() const 328 { return _M_t.empty(); } 329 330 /** Returns the size of the %multimap. */ 331 size_type 332 size() const 333 { return _M_t.size(); } 334 335 /** Returns the maximum size of the %multimap. */ 336 size_type 337 max_size() const 338 { return _M_t.max_size(); } 339 340 // modifiers 341 /** 342 * @brief Inserts a std::pair into the %multimap. 343 * @param x Pair to be inserted (see std::make_pair for easy creation 344 * of pairs). 345 * @return An iterator that points to the inserted (key,value) pair. 346 * 347 * This function inserts a (key, value) pair into the %multimap. 348 * Contrary to a std::map the %multimap does not rely on unique keys and 349 * thus multiple pairs with the same key can be inserted. 350 * 351 * Insertion requires logarithmic time. 352 */ 353 iterator 354 insert(const value_type& __x) 355 { return _M_t.insert_equal(__x); } 356 357 /** 358 * @brief Inserts a std::pair into the %multimap. 359 * @param position An iterator that serves as a hint as to where the 360 * pair should be inserted. 361 * @param x Pair to be inserted (see std::make_pair for easy creation 362 * of pairs). 363 * @return An iterator that points to the inserted (key,value) pair. 364 * 365 * This function inserts a (key, value) pair into the %multimap. 366 * Contrary to a std::map the %multimap does not rely on unique keys and 367 * thus multiple pairs with the same key can be inserted. 368 * Note that the first parameter is only a hint and can potentially 369 * improve the performance of the insertion process. A bad hint would 370 * cause no gains in efficiency. 371 * 372 * See http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4 373 * for more on "hinting". 374 * 375 * Insertion requires logarithmic time (if the hint is not taken). 376 */ 377 iterator 378 insert(iterator __position, const value_type& __x) 379 { return _M_t.insert_equal(__position, __x); } 380 381 /** 382 * @brief A template function that attemps to insert a range of elements. 383 * @param first Iterator pointing to the start of the range to be 384 * inserted. 385 * @param last Iterator pointing to the end of the range. 386 * 387 * Complexity similar to that of the range constructor. 388 */ 389 template <typename _InputIterator> 390 void 391 insert(_InputIterator __first, _InputIterator __last) 392 { _M_t.insert_equal(__first, __last); } 393 394 /** 395 * @brief Erases an element from a %multimap. 396 * @param position An iterator pointing to the element to be erased. 397 * 398 * This function erases an element, pointed to by the given iterator, 399 * from a %multimap. Note that this function only erases the element, 400 * and that if the element is itself a pointer, the pointed-to memory is 401 * not touched in any way. Managing the pointer is the user's 402 * responsibilty. 403 */ 404 void 405 erase(iterator __position) 406 { _M_t.erase(__position); } 407 408 /** 409 * @brief Erases elements according to the provided key. 410 * @param x Key of element to be erased. 411 * @return The number of elements erased. 412 * 413 * This function erases all elements located by the given key from a 414 * %multimap. 415 * Note that this function only erases the element, and that if 416 * the element is itself a pointer, the pointed-to memory is not touched 417 * in any way. Managing the pointer is the user's responsibilty. 418 */ 419 size_type 420 erase(const key_type& __x) 421 { return _M_t.erase(__x); } 422 423 /** 424 * @brief Erases a [first,last) range of elements from a %multimap. 425 * @param first Iterator pointing to the start of the range to be 426 * erased. 427 * @param last Iterator pointing to the end of the range to be erased. 428 * 429 * This function erases a sequence of elements from a %multimap. 430 * Note that this function only erases the elements, and that if 431 * the elements themselves are pointers, the pointed-to memory is not 432 * touched in any way. Managing the pointer is the user's responsibilty. 433 */ 434 void 435 erase(iterator __first, iterator __last) 436 { _M_t.erase(__first, __last); } 437 438 /** 439 * @brief Swaps data with another %multimap. 440 * @param x A %multimap of the same element and allocator types. 441 * 442 * This exchanges the elements between two multimaps in constant time. 443 * (It is only swapping a pointer, an integer, and an instance of 444 * the @c Compare type (which itself is often stateless and empty), so it 445 * should be quite fast.) 446 * Note that the global std::swap() function is specialized such that 447 * std::swap(m1,m2) will feed to this function. 448 */ 449 void 450 swap(multimap& __x) 451 { _M_t.swap(__x._M_t); } 452 453 /** 454 * Erases all elements in a %multimap. Note that this function only 455 * erases the elements, and that if the elements themselves are pointers, 456 * the pointed-to memory is not touched in any way. Managing the pointer 457 * is the user's responsibilty. 458 */ 459 void 460 clear() 461 { _M_t.clear(); } 462 463 // observers 464 /** 465 * Returns the key comparison object out of which the %multimap 466 * was constructed. 467 */ 468 key_compare 469 key_comp() const 470 { return _M_t.key_comp(); } 471 472 /** 473 * Returns a value comparison object, built from the key comparison 474 * object out of which the %multimap was constructed. 475 */ 476 value_compare 477 value_comp() const 478 { return value_compare(_M_t.key_comp()); } 479 480 // multimap operations 481 /** 482 * @brief Tries to locate an element in a %multimap. 483 * @param x Key of (key, value) pair to be located. 484 * @return Iterator pointing to sought-after element, 485 * or end() if not found. 486 * 487 * This function takes a key and tries to locate the element with which 488 * the key matches. If successful the function returns an iterator 489 * pointing to the sought after %pair. If unsuccessful it returns the 490 * past-the-end ( @c end() ) iterator. 491 */ 492 iterator 493 find(const key_type& __x) 494 { return _M_t.find(__x); } 495 496 /** 497 * @brief Tries to locate an element in a %multimap. 498 * @param x Key of (key, value) pair to be located. 499 * @return Read-only (constant) iterator pointing to sought-after 500 * element, or end() if not found. 501 * 502 * This function takes a key and tries to locate the element with which 503 * the key matches. If successful the function returns a constant 504 * iterator pointing to the sought after %pair. If unsuccessful it 505 * returns the past-the-end ( @c end() ) iterator. 506 */ 507 const_iterator 508 find(const key_type& __x) const 509 { return _M_t.find(__x); } 510 511 /** 512 * @brief Finds the number of elements with given key. 513 * @param x Key of (key, value) pairs to be located. 514 * @return Number of elements with specified key. 515 */ 516 size_type 517 count(const key_type& __x) const 518 { return _M_t.count(__x); } 519 520 /** 521 * @brief Finds the beginning of a subsequence matching given key. 522 * @param x Key of (key, value) pair to be located. 523 * @return Iterator pointing to first element equal to or greater 524 * than key, or end(). 525 * 526 * This function returns the first element of a subsequence of elements 527 * that matches the given key. If unsuccessful it returns an iterator 528 * pointing to the first element that has a greater value than given key 529 * or end() if no such element exists. 530 */ 531 iterator 532 lower_bound(const key_type& __x) 533 { return _M_t.lower_bound(__x); } 534 535 /** 536 * @brief Finds the beginning of a subsequence matching given key. 537 * @param x Key of (key, value) pair to be located. 538 * @return Read-only (constant) iterator pointing to first element 539 * equal to or greater than key, or end(). 540 * 541 * This function returns the first element of a subsequence of elements 542 * that matches the given key. If unsuccessful the iterator will point 543 * to the next greatest element or, if no such greater element exists, to 544 * end(). 545 */ 546 const_iterator 547 lower_bound(const key_type& __x) const 548 { return _M_t.lower_bound(__x); } 549 550 /** 551 * @brief Finds the end of a subsequence matching given key. 552 * @param x Key of (key, value) pair to be located. 553 * @return Iterator pointing to the first element 554 * greater than key, or end(). 555 */ 556 iterator 557 upper_bound(const key_type& __x) 558 { return _M_t.upper_bound(__x); } 559 560 /** 561 * @brief Finds the end of a subsequence matching given key. 562 * @param x Key of (key, value) pair to be located. 563 * @return Read-only (constant) iterator pointing to first iterator 564 * greater than key, or end(). 565 */ 566 const_iterator 567 upper_bound(const key_type& __x) const 568 { return _M_t.upper_bound(__x); } 569 570 /** 571 * @brief Finds a subsequence matching given key. 572 * @param x Key of (key, value) pairs to be located. 573 * @return Pair of iterators that possibly points to the subsequence 574 * matching given key. 575 * 576 * This function is equivalent to 577 * @code 578 * std::make_pair(c.lower_bound(val), 579 * c.upper_bound(val)) 580 * @endcode 581 * (but is faster than making the calls separately). 582 */ 583 std::pair<iterator, iterator> 584 equal_range(const key_type& __x) 585 { return _M_t.equal_range(__x); } 586 587 /** 588 * @brief Finds a subsequence matching given key. 589 * @param x Key of (key, value) pairs to be located. 590 * @return Pair of read-only (constant) iterators that possibly points 591 * to the subsequence matching given key. 592 * 593 * This function is equivalent to 594 * @code 595 * std::make_pair(c.lower_bound(val), 596 * c.upper_bound(val)) 597 * @endcode 598 * (but is faster than making the calls separately). 599 */ 600 std::pair<const_iterator, const_iterator> 601 equal_range(const key_type& __x) const 602 { return _M_t.equal_range(__x); } 603 604 template <typename _K1, typename _T1, typename _C1, typename _A1> 605 friend bool 606 operator== (const multimap<_K1, _T1, _C1, _A1>&, 607 const multimap<_K1, _T1, _C1, _A1>&); 608 609 template <typename _K1, typename _T1, typename _C1, typename _A1> 610 friend bool 611 operator< (const multimap<_K1, _T1, _C1, _A1>&, 612 const multimap<_K1, _T1, _C1, _A1>&); 613 }; 614 615 /** 616 * @brief Multimap equality comparison. 617 * @param x A %multimap. 618 * @param y A %multimap of the same type as @a x. 619 * @return True iff the size and elements of the maps are equal. 620 * 621 * This is an equivalence relation. It is linear in the size of the 622 * multimaps. Multimaps are considered equivalent if their sizes are equal, 623 * and if corresponding elements compare equal. 624 */ 625 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 626 inline bool 627 operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 628 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 629 { return __x._M_t == __y._M_t; } 630 631 /** 632 * @brief Multimap ordering relation. 633 * @param x A %multimap. 634 * @param y A %multimap of the same type as @a x. 635 * @return True iff @a x is lexicographically less than @a y. 636 * 637 * This is a total ordering relation. It is linear in the size of the 638 * multimaps. The elements must be comparable with @c <. 639 * 640 * See std::lexicographical_compare() for how the determination is made. 641 */ 642 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 643 inline bool 644 operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 645 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 646 { return __x._M_t < __y._M_t; } 647 648 /// Based on operator== 649 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 650 inline bool 651 operator!=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 652 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 653 { return !(__x == __y); } 654 655 /// Based on operator< 656 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 657 inline bool 658 operator>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 659 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 660 { return __y < __x; } 661 662 /// Based on operator< 663 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 664 inline bool 665 operator<=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 666 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 667 { return !(__y < __x); } 668 669 /// Based on operator< 670 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 671 inline bool 672 operator>=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, 673 const multimap<_Key, _Tp, _Compare, _Alloc>& __y) 674 { return !(__x < __y); } 675 676 /// See std::multimap::swap(). 677 template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> 678 inline void 679 swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x, 680 multimap<_Key, _Tp, _Compare, _Alloc>& __y) 681 { __x.swap(__y); } 682} // namespace std 683 684#endif /* _MULTIMAP_H */ 685