From Jason Turner

[associative]

C++11 → C++14 23.9 KB 269 lines
Current Draft | LaTeX Source
Archived: C++11 | C++14
Markdown: C++11 | C++14
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpvbza_qov/{from.md → to.md} +127 -122
tmp/tmpvbza_qov/{from.md → to.md} RENAMED
@@ -180,28 +180,32 @@ namespace std {
180
  return comp(x.first, y.first);
181
  }
182
  };
183
 
184
  // [map.cons], construct/copy/destroy:
185
- explicit map(const Compare& comp = Compare(),
 
186
  const Allocator& = Allocator());
187
  template <class InputIterator>
188
  map(InputIterator first, InputIterator last,
189
  const Compare& comp = Compare(), const Allocator& = Allocator());
190
- map(const map<Key,T,Compare,Allocator>& x);
191
- map(map<Key,T,Compare,Allocator>&& x);
192
  explicit map(const Allocator&);
193
  map(const map&, const Allocator&);
194
  map(map&&, const Allocator&);
195
  map(initializer_list<value_type>,
196
  const Compare& = Compare(),
197
  const Allocator& = Allocator());
 
 
 
 
 
198
  ~map();
199
- map<Key,T,Compare,Allocator>&
200
- operator=(const map<Key,T,Compare,Allocator>& x);
201
- map<Key,T,Compare,Allocator>&
202
- operator=(map<Key,T,Compare,Allocator>&& x);
203
  map& operator=(initializer_list<value_type>);
204
  allocator_type get_allocator() const noexcept;
205
 
206
  // iterators:
207
  iterator begin() noexcept;
@@ -243,31 +247,44 @@ namespace std {
243
  void insert(initializer_list<value_type>);
244
 
245
  iterator erase(const_iterator position);
246
  size_type erase(const key_type& x);
247
  iterator erase(const_iterator first, const_iterator last);
248
- void swap(map<Key,T,Compare,Allocator>&);
249
  void clear() noexcept;
250
 
251
  // observers:
252
  key_compare key_comp() const;
253
  value_compare value_comp() const;
254
 
255
- // [map.ops], map operations:
256
  iterator find(const key_type& x);
257
  const_iterator find(const key_type& x) const;
 
 
 
258
  size_type count(const key_type& x) const;
 
259
 
260
  iterator lower_bound(const key_type& x);
261
  const_iterator lower_bound(const key_type& x) const;
 
 
 
262
  iterator upper_bound(const key_type& x);
263
  const_iterator upper_bound(const key_type& x) const;
 
 
264
 
265
  pair<iterator,iterator>
266
  equal_range(const key_type& x);
267
  pair<const_iterator,const_iterator>
268
  equal_range(const key_type& x) const;
 
 
 
 
269
  };
270
 
271
  template <class Key, class T, class Compare, class Allocator>
272
  bool operator==(const map<Key,T,Compare,Allocator>& x,
273
  const map<Key,T,Compare,Allocator>& y);
@@ -295,11 +312,11 @@ namespace std {
295
  ```
296
 
297
  #### `map` constructors, copy, and assignment <a id="map.cons">[[map.cons]]</a>
298
 
299
  ``` cpp
300
- explicit map(const Compare& comp = Compare(),
301
  const Allocator& = Allocator());
302
  ```
303
 
304
  *Effects:* Constructs an empty `map` using the specified comparison
305
  object and allocator.
@@ -310,13 +327,13 @@ object and allocator.
310
  template <class InputIterator>
311
  map(InputIterator first, InputIterator last,
312
  const Compare& comp = Compare(), const Allocator& = Allocator());
313
  ```
314
 
315
- *Requires:* If the iterator’s dereference operator returns an lvalue or
316
  a const rvalue `pair<key_type, mapped_type>`, then both `key_type` and
317
- `mapped_type` shall be `CopyConstructible`.
318
 
319
  *Effects:* Constructs an empty `map` using the specified comparison
320
  object and allocator, and inserts elements from the range \[`first`,
321
  `last`).
322
 
@@ -330,31 +347,31 @@ T& operator[](const key_type& x);
330
  ```
331
 
332
  *Effects:* If there is no key equivalent to `x` in the map, inserts
333
  `value_type(x, T())` into the map.
334
 
335
- *Requires:* `key_type` shall be `CopyConstructible` and `mapped_type`
336
- shall be `DefaultConstructible`.
337
 
338
  *Returns:* A reference to the `mapped_type` corresponding to `x` in
339
  `*this`.
340
 
341
- *Complexity:* logarithmic.
342
 
343
  ``` cpp
344
  T& operator[](key_type&& x);
345
  ```
346
 
347
  *Effects:* If there is no key equivalent to `x` in the map, inserts
348
  `value_type(std::move(x), T())` into the map.
349
 
350
- *Requires:* `mapped_type` shall be `DefaultConstructible`.
351
 
352
  *Returns:* A reference to the `mapped_type` corresponding to `x` in
353
  `*this`.
354
 
355
- *Complexity:* logarithmic.
356
 
357
  ``` cpp
358
  T& at(const key_type& x);
359
  const T& at(const key_type& x) const;
360
  ```
@@ -363,58 +380,27 @@ const T& at(const key_type& x) const;
363
  `*this`.
364
 
365
  *Throws:* An exception object of type `out_of_range` if no such element
366
  is present.
367
 
368
- *Complexity:* logarithmic.
369
 
370
  #### `map` modifiers <a id="map.modifiers">[[map.modifiers]]</a>
371
 
372
  ``` cpp
373
  template <class P> pair<iterator, bool> insert(P&& x);
374
- template <class P> pair<iterator, bool> insert(const_iterator position, P&& x);
375
  template <class InputIterator>
376
  void insert(InputIterator first, InputIterator last);
377
  ```
378
 
379
- *Requires:* `P` shall be convertible to `value_type`.
 
 
380
 
381
- If `P` is instantiated as a reference type, then the argument `x` is
382
- copied from. Otherwise `x` is considered to be an rvalue as it is
383
- converted to `value_type` and inserted into the `map`. Specifically, in
384
- such cases `CopyConstructible` is not required of `key_type` or
385
- `mapped_type` unless the conversion from `P` specifically requires it
386
- (e.g., if `P` is a `tuple<const key_type, mapped_type>`, then `key_type`
387
- must be `CopyConstructible`). The signature taking `InputIterator`
388
- parameters does not require `CopyConstructible` of either `key_type` or
389
- `mapped_type` if the dereferenced `InputIterator` returns a non-const
390
- rvalue `pair<key_type,mapped_type>`. Otherwise `CopyConstructible` is
391
- required for both `key_type` and `mapped_type`.
392
-
393
- #### `map` operations <a id="map.ops">[[map.ops]]</a>
394
-
395
- ``` cpp
396
- iterator find(const key_type& x);
397
- const_iterator find(const key_type& x) const;
398
-
399
- iterator lower_bound(const key_type& x);
400
- const_iterator lower_bound(const key_type& x) const;
401
-
402
- iterator upper_bound(const key_type& x);
403
- const_iterator upper_bound(const key_type &x) const;
404
-
405
- pair<iterator, iterator>
406
- equal_range(const key_type &x);
407
- pair<const_iterator, const_iterator>
408
- equal_range(const key_type& x) const;
409
- ```
410
-
411
- The `find`, `lower_bound`, `upper_bound` and `equal_range` member
412
- functions each have two versions, one const and the other non-const. In
413
- each case the behavior of the two functions is identical except that the
414
- const version returns a `const_iterator` and the non-const version an
415
- `iterator` ([[associative.reqmts]]).
416
 
417
  #### `map` specialized algorithms <a id="map.special">[[map.special]]</a>
418
 
419
  ``` cpp
420
  template <class Key, class T, class Compare, class Allocator>
@@ -485,29 +471,33 @@ namespace std {
485
  return comp(x.first, y.first);
486
  }
487
  };
488
 
489
  // construct/copy/destroy:
490
- explicit multimap(const Compare& comp = Compare(),
 
491
  const Allocator& = Allocator());
492
  template <class InputIterator>
493
  multimap(InputIterator first, InputIterator last,
494
  const Compare& comp = Compare(),
495
  const Allocator& = Allocator());
496
- multimap(const multimap<Key,T,Compare,Allocator>& x);
497
- multimap(multimap<Key,T,Compare,Allocator>&& x);
498
  explicit multimap(const Allocator&);
499
  multimap(const multimap&, const Allocator&);
500
  multimap(multimap&&, const Allocator&);
501
  multimap(initializer_list<value_type>,
502
  const Compare& = Compare(),
503
  const Allocator& = Allocator());
 
 
 
 
 
504
  ~multimap();
505
- multimap<Key,T,Compare,Allocator>&
506
- operator=(const multimap<Key,T,Compare,Allocator>& x);
507
- multimap<Key,T,Compare,Allocator>&
508
- operator=(multimap<Key,T,Compare,Allocator>&& x);
509
  multimap& operator=(initializer_list<value_type>);
510
  allocator_type get_allocator() const noexcept;
511
 
512
  // iterators:
513
  iterator begin() noexcept;
@@ -542,31 +532,44 @@ namespace std {
542
  void insert(initializer_list<value_type>);
543
 
544
  iterator erase(const_iterator position);
545
  size_type erase(const key_type& x);
546
  iterator erase(const_iterator first, const_iterator last);
547
- void swap(multimap<Key,T,Compare,Allocator>&);
548
  void clear() noexcept;
549
 
550
  // observers:
551
  key_compare key_comp() const;
552
  value_compare value_comp() const;
553
 
554
  // map operations:
555
  iterator find(const key_type& x);
556
  const_iterator find(const key_type& x) const;
 
 
 
557
  size_type count(const key_type& x) const;
 
558
 
559
  iterator lower_bound(const key_type& x);
560
  const_iterator lower_bound(const key_type& x) const;
 
 
 
561
  iterator upper_bound(const key_type& x);
562
  const_iterator upper_bound(const key_type& x) const;
 
 
563
 
564
  pair<iterator,iterator>
565
  equal_range(const key_type& x);
566
  pair<const_iterator,const_iterator>
567
  equal_range(const key_type& x) const;
 
 
 
 
568
  };
569
 
570
  template <class Key, class T, class Compare, class Allocator>
571
  bool operator==(const multimap<Key,T,Compare,Allocator>& x,
572
  const multimap<Key,T,Compare,Allocator>& y);
@@ -594,11 +597,11 @@ namespace std {
594
  ```
595
 
596
  #### `multimap` constructors <a id="multimap.cons">[[multimap.cons]]</a>
597
 
598
  ``` cpp
599
- explicit multimap(const Compare& comp = Compare(),
600
  const Allocator& = Allocator());
601
  ```
602
 
603
  *Effects:* Constructs an empty `multimap` using the specified comparison
604
  object and allocator.
@@ -610,13 +613,13 @@ template <class InputIterator>
610
  multimap(InputIterator first, InputIterator last,
611
  const Compare& comp = Compare(),
612
  const Allocator& = Allocator());
613
  ```
614
 
615
- *Requires:* If the iterator’s dereference operator returns an lvalue or
616
  a const rvalue `pair<key_type, mapped_type>`, then both `key_type` and
617
- `mapped_type` shall be `CopyConstructible`.
618
 
619
  *Effects:* Constructs an empty `multimap` using the specified comparison
620
  object and allocator, and inserts elements from the range \[`first`,
621
  `last`).
622
 
@@ -628,44 +631,16 @@ sorted using `comp` and otherwise N log N, where N is `last - first`.
628
  ``` cpp
629
  template <class P> iterator insert(P&& x);
630
  template <class P> iterator insert(const_iterator position, P&& x);
631
  ```
632
 
633
- *Requires:* `P` shall be convertible to `value_type`.
 
 
634
 
635
- If `P` is instantiated as a reference type, then the argument `x` is
636
- copied from. Otherwise `x` is considered to be an rvalue as it is
637
- converted to `value_type` and inserted into the `map`. Specifically, in
638
- such cases `CopyConstructible` is not required of `key_type` or
639
- `mapped_type` unless the conversion from `P` specifically requires it
640
- (e.g., if `P` is a `tuple<const key_type, mapped_type>`, then `key_type`
641
- must be `CopyConstructible`). The signature taking `InputIterator`
642
- parameters does not require `CopyConstructible` of either `key_type` or
643
- `mapped_type` if the dereferenced `InputIterator` returns a non-const
644
- rvalue `pair<key_type, mapped_type>`. Otherwise `CopyConstructible` is
645
- required for both `key_type` and `mapped_type`.
646
-
647
- #### `multimap` operations <a id="multimap.ops">[[multimap.ops]]</a>
648
-
649
- ``` cpp
650
- iterator find(const key_type &x);
651
- const_iterator find(const key_type& x) const;
652
-
653
- iterator lower_bound(const key_type& x);
654
- const_iterator lower_bound(const key_type& x) const;
655
-
656
- pair<iterator, iterator>
657
- equal_range(const key_type& x);
658
- pair<const_iterator, const_iterator>
659
- equal_range(const key_type& x) const;
660
- ```
661
-
662
- The `find`, `lower_bound`, `upper_bound`, and `equal_range` member
663
- functions each have two versions, one const and one non-const. In each
664
- case the behavior of the two versions is identical except that the const
665
- version returns a `const_iterator` and the non-const version an
666
- `iterator` ([[associative.reqmts]]).
667
 
668
  #### `multimap` specialized algorithms <a id="multimap.special">[[multimap.special]]</a>
669
 
670
  ``` cpp
671
  template <class Key, class T, class Compare, class Allocator>
@@ -721,28 +696,32 @@ namespace std {
721
  typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
722
  typedef std::reverse_iterator<iterator> reverse_iterator;
723
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
724
 
725
  // [set.cons], construct/copy/destroy:
726
- explicit set(const Compare& comp = Compare(),
 
727
  const Allocator& = Allocator());
728
  template <class InputIterator>
729
  set(InputIterator first, InputIterator last,
730
  const Compare& comp = Compare(), const Allocator& = Allocator());
731
- set(const set<Key,Compare,Allocator>& x);
732
- set(set<Key,Compare,Allocator>&& x);
733
  explicit set(const Allocator&);
734
  set(const set&, const Allocator&);
735
  set(set&&, const Allocator&);
736
  set(initializer_list<value_type>,
737
  const Compare& = Compare(),
738
  const Allocator& = Allocator());
 
 
 
 
 
739
  ~set();
740
- set<Key,Compare,Allocator>& operator=
741
- (const set<Key,Compare,Allocator>& x);
742
- set<Key,Compare,Allocator>& operator=
743
- (set<Key,Compare,Allocator>&& x);
744
  set& operator=(initializer_list<value_type>);
745
  allocator_type get_allocator() const noexcept;
746
 
747
  // iterators:
748
  iterator begin() noexcept;
@@ -777,31 +756,42 @@ namespace std {
777
  void insert(initializer_list<value_type>);
778
 
779
  iterator erase(const_iterator position);
780
  size_type erase(const key_type& x);
781
  iterator erase(const_iterator first, const_iterator last);
782
- void swap(set<Key,Compare,Allocator>&);
783
  void clear() noexcept;
784
 
785
  // observers:
786
  key_compare key_comp() const;
787
  value_compare value_comp() const;
788
 
789
  // set operations:
790
  iterator find(const key_type& x);
791
  const_iterator find(const key_type& x) const;
 
 
792
 
793
  size_type count(const key_type& x) const;
 
794
 
795
  iterator lower_bound(const key_type& x);
796
  const_iterator lower_bound(const key_type& x) const;
 
 
797
 
798
  iterator upper_bound(const key_type& x);
799
  const_iterator upper_bound(const key_type& x) const;
 
 
800
 
801
  pair<iterator,iterator> equal_range(const key_type& x);
802
  pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
 
 
 
 
803
  };
804
 
805
  template <class Key, class Compare, class Allocator>
806
  bool operator==(const set<Key,Compare,Allocator>& x,
807
  const set<Key,Compare,Allocator>& y);
@@ -829,11 +819,11 @@ namespace std {
829
  ```
830
 
831
  #### `set` constructors, copy, and assignment <a id="set.cons">[[set.cons]]</a>
832
 
833
  ``` cpp
834
- explicit set(const Compare& comp = Compare(),
835
  const Allocator& = Allocator());
836
  ```
837
 
838
  *Effects:* Constructs an empty set using the specified comparison
839
  objects and allocator.
@@ -848,12 +838,12 @@ template <class InputIterator>
848
 
849
  *Effects:* Constructs an empty `set` using the specified comparison
850
  object and allocator, and inserts elements from the range \[`first`,
851
  `last`).
852
 
853
- *Requires:* If the iterator’s dereference operator returns an lvalue or
854
- a non-const rvalue, then `Key` shall be `CopyConstructible`.
855
 
856
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
857
  sorted using `comp` and otherwise N log N, where N is `last - first`.
858
 
859
  #### `set` specialized algorithms <a id="set.special">[[set.special]]</a>
@@ -913,29 +903,33 @@ namespace std {
913
  typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
914
  typedef std::reverse_iterator<iterator> reverse_iterator;
915
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
916
 
917
  // construct/copy/destroy:
918
- explicit multiset(const Compare& comp = Compare(),
 
919
  const Allocator& = Allocator());
920
  template <class InputIterator>
921
  multiset(InputIterator first, InputIterator last,
922
  const Compare& comp = Compare(),
923
  const Allocator& = Allocator());
924
- multiset(const multiset<Key,Compare,Allocator>& x);
925
- multiset(multiset<Key,Compare,Allocator>&& x);
926
  explicit multiset(const Allocator&);
927
  multiset(const multiset&, const Allocator&);
928
  multiset(multiset&&, const Allocator&);
929
  multiset(initializer_list<value_type>,
930
  const Compare& = Compare(),
931
  const Allocator& = Allocator());
 
 
 
 
 
932
  ~multiset();
933
- multiset<Key,Compare,Allocator>&
934
- operator=(const multiset<Key,Compare,Allocator>& x);
935
- multiset<Key,Compare,Allocator>&
936
- operator=(multiset<Key,Compare,Allocator>&& x);
937
  multiset& operator=(initializer_list<value_type>);
938
  allocator_type get_allocator() const noexcept;
939
 
940
  // iterators:
941
  iterator begin() noexcept;
@@ -970,31 +964,42 @@ namespace std {
970
  void insert(initializer_list<value_type>);
971
 
972
  iterator erase(const_iterator position);
973
  size_type erase(const key_type& x);
974
  iterator erase(const_iterator first, const_iterator last);
975
- void swap(multiset<Key,Compare,Allocator>&);
976
  void clear() noexcept;
977
 
978
  // observers:
979
  key_compare key_comp() const;
980
  value_compare value_comp() const;
981
 
982
  // set operations:
983
  iterator find(const key_type& x);
984
  const_iterator find(const key_type& x) const;
 
 
985
 
986
  size_type count(const key_type& x) const;
 
987
 
988
  iterator lower_bound(const key_type& x);
989
  const_iterator lower_bound(const key_type& x) const;
 
 
990
 
991
  iterator upper_bound(const key_type& x);
992
  const_iterator upper_bound(const key_type& x) const;
 
 
993
 
994
  pair<iterator,iterator> equal_range(const key_type& x);
995
  pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
 
 
 
 
996
  };
997
 
998
  template <class Key, class Compare, class Allocator>
999
  bool operator==(const multiset<Key,Compare,Allocator>& x,
1000
  const multiset<Key,Compare,Allocator>& y);
@@ -1022,27 +1027,27 @@ namespace std {
1022
  ```
1023
 
1024
  #### `multiset` constructors <a id="multiset.cons">[[multiset.cons]]</a>
1025
 
1026
  ``` cpp
1027
- explicit multiset(const Compare& comp = Compare(),
1028
  const Allocator& = Allocator());
1029
  ```
1030
 
1031
  *Effects:* Constructs an empty set using the specified comparison object
1032
  and allocator.
1033
 
1034
  *Complexity:* Constant.
1035
 
1036
  ``` cpp
1037
  template <class InputIterator>
1038
- multiset(InputIterator first, last,
1039
  const Compare& comp = Compare(), const Allocator& = Allocator());
1040
  ```
1041
 
1042
- *Requires:* If the iterator’s dereference operator returns an lvalue or
1043
- a const rvalue, then `Key` shall be `CopyConstructible`.
1044
 
1045
  *Effects:* Constructs an empty `multiset` using the specified comparison
1046
  object and allocator, and inserts elements from the range \[`first`,
1047
  `last`).
1048
 
 
180
  return comp(x.first, y.first);
181
  }
182
  };
183
 
184
  // [map.cons], construct/copy/destroy:
185
+ map() : map(Compare()) { }
186
+ explicit map(const Compare& comp,
187
  const Allocator& = Allocator());
188
  template <class InputIterator>
189
  map(InputIterator first, InputIterator last,
190
  const Compare& comp = Compare(), const Allocator& = Allocator());
191
+ map(const map& x);
192
+ map(map&& x);
193
  explicit map(const Allocator&);
194
  map(const map&, const Allocator&);
195
  map(map&&, const Allocator&);
196
  map(initializer_list<value_type>,
197
  const Compare& = Compare(),
198
  const Allocator& = Allocator());
199
+ template <class InputIterator>
200
+ map(InputIterator first, InputIterator last, const Allocator& a)
201
+ : map(first, last, Compare(), a) { }
202
+ map(initializer_list<value_type> il, const Allocator& a)
203
+ : map(il, Compare(), a) { }
204
  ~map();
205
+ map& operator=(const map& x);
206
+ map& operator=(map&& x);
 
 
207
  map& operator=(initializer_list<value_type>);
208
  allocator_type get_allocator() const noexcept;
209
 
210
  // iterators:
211
  iterator begin() noexcept;
 
247
  void insert(initializer_list<value_type>);
248
 
249
  iterator erase(const_iterator position);
250
  size_type erase(const key_type& x);
251
  iterator erase(const_iterator first, const_iterator last);
252
+ void swap(map&);
253
  void clear() noexcept;
254
 
255
  // observers:
256
  key_compare key_comp() const;
257
  value_compare value_comp() const;
258
 
259
+ // map operations:
260
  iterator find(const key_type& x);
261
  const_iterator find(const key_type& x) const;
262
+ template <class K> iterator find(const K& x);
263
+ template <class K> const_iterator find(const K& x) const;
264
+
265
  size_type count(const key_type& x) const;
266
+ template <class K> size_type count(const K& x) const;
267
 
268
  iterator lower_bound(const key_type& x);
269
  const_iterator lower_bound(const key_type& x) const;
270
+ template <class K> iterator lower_bound(const K& x);
271
+ template <class K> const_iterator lower_bound(const K& x) const;
272
+
273
  iterator upper_bound(const key_type& x);
274
  const_iterator upper_bound(const key_type& x) const;
275
+ template <class K> iterator upper_bound(const K& x);
276
+ template <class K> const_iterator upper_bound(const K& x) const;
277
 
278
  pair<iterator,iterator>
279
  equal_range(const key_type& x);
280
  pair<const_iterator,const_iterator>
281
  equal_range(const key_type& x) const;
282
+ template <class K>
283
+ pair<iterator, iterator> equal_range(const K& x);
284
+ template <class K>
285
+ pair<const_iterator, const_iterator> equal_range(const K& x) const;
286
  };
287
 
288
  template <class Key, class T, class Compare, class Allocator>
289
  bool operator==(const map<Key,T,Compare,Allocator>& x,
290
  const map<Key,T,Compare,Allocator>& y);
 
312
  ```
313
 
314
  #### `map` constructors, copy, and assignment <a id="map.cons">[[map.cons]]</a>
315
 
316
  ``` cpp
317
+ explicit map(const Compare& comp,
318
  const Allocator& = Allocator());
319
  ```
320
 
321
  *Effects:* Constructs an empty `map` using the specified comparison
322
  object and allocator.
 
327
  template <class InputIterator>
328
  map(InputIterator first, InputIterator last,
329
  const Compare& comp = Compare(), const Allocator& = Allocator());
330
  ```
331
 
332
+ *Requires:* If the iterator’s indirection operator returns an lvalue or
333
  a const rvalue `pair<key_type, mapped_type>`, then both `key_type` and
334
+ `mapped_type` shall be `CopyInsertable` into `*this`.
335
 
336
  *Effects:* Constructs an empty `map` using the specified comparison
337
  object and allocator, and inserts elements from the range \[`first`,
338
  `last`).
339
 
 
347
  ```
348
 
349
  *Effects:* If there is no key equivalent to `x` in the map, inserts
350
  `value_type(x, T())` into the map.
351
 
352
+ *Requires:* `key_type` shall be `CopyInsertable` and `mapped_type` shall
353
+ be `DefaultInsertable` into `*this`.
354
 
355
  *Returns:* A reference to the `mapped_type` corresponding to `x` in
356
  `*this`.
357
 
358
+ *Complexity:* Logarithmic.
359
 
360
  ``` cpp
361
  T& operator[](key_type&& x);
362
  ```
363
 
364
  *Effects:* If there is no key equivalent to `x` in the map, inserts
365
  `value_type(std::move(x), T())` into the map.
366
 
367
+ *Requires:* `mapped_type` shall be `DefaultInsertable` into `*this`.
368
 
369
  *Returns:* A reference to the `mapped_type` corresponding to `x` in
370
  `*this`.
371
 
372
+ *Complexity:* Logarithmic.
373
 
374
  ``` cpp
375
  T& at(const key_type& x);
376
  const T& at(const key_type& x) const;
377
  ```
 
380
  `*this`.
381
 
382
  *Throws:* An exception object of type `out_of_range` if no such element
383
  is present.
384
 
385
+ *Complexity:* Logarithmic.
386
 
387
  #### `map` modifiers <a id="map.modifiers">[[map.modifiers]]</a>
388
 
389
  ``` cpp
390
  template <class P> pair<iterator, bool> insert(P&& x);
391
+ template <class P> iterator insert(const_iterator position, P&& x);
392
  template <class InputIterator>
393
  void insert(InputIterator first, InputIterator last);
394
  ```
395
 
396
+ *Effects:* The first form is equivalent to
397
+ `return emplace(std::forward<P>(x))`. The second form is equivalent to
398
+ `return emplace_hint(position, std::forward<P>(x))`.
399
 
400
+ *Remarks:* These signatures shall not participate in overload resolution
401
+ unless `std::is_constructible<value_type, P&&>::value` is `true`.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
402
 
403
  #### `map` specialized algorithms <a id="map.special">[[map.special]]</a>
404
 
405
  ``` cpp
406
  template <class Key, class T, class Compare, class Allocator>
 
471
  return comp(x.first, y.first);
472
  }
473
  };
474
 
475
  // construct/copy/destroy:
476
+ multimap() : multimap(Compare()) { }
477
+ explicit multimap(const Compare& comp,
478
  const Allocator& = Allocator());
479
  template <class InputIterator>
480
  multimap(InputIterator first, InputIterator last,
481
  const Compare& comp = Compare(),
482
  const Allocator& = Allocator());
483
+ multimap(const multimap& x);
484
+ multimap(multimap&& x);
485
  explicit multimap(const Allocator&);
486
  multimap(const multimap&, const Allocator&);
487
  multimap(multimap&&, const Allocator&);
488
  multimap(initializer_list<value_type>,
489
  const Compare& = Compare(),
490
  const Allocator& = Allocator());
491
+ template <class InputIterator>
492
+ multimap(InputIterator first, InputIterator last, const Allocator& a)
493
+ : multimap(first, last, Compare(), a) { }
494
+ multimap(initializer_list<value_type> il, const Allocator& a)
495
+ : multimap(il, Compare(), a) { }
496
  ~multimap();
497
+ multimap& operator=(const multimap& x);
498
+ multimap& operator=(multimap&& x);
 
 
499
  multimap& operator=(initializer_list<value_type>);
500
  allocator_type get_allocator() const noexcept;
501
 
502
  // iterators:
503
  iterator begin() noexcept;
 
532
  void insert(initializer_list<value_type>);
533
 
534
  iterator erase(const_iterator position);
535
  size_type erase(const key_type& x);
536
  iterator erase(const_iterator first, const_iterator last);
537
+ void swap(multimap&);
538
  void clear() noexcept;
539
 
540
  // observers:
541
  key_compare key_comp() const;
542
  value_compare value_comp() const;
543
 
544
  // map operations:
545
  iterator find(const key_type& x);
546
  const_iterator find(const key_type& x) const;
547
+ template <class K> iterator find(const K& x);
548
+ template <class K> const_iterator find(const K& x) const;
549
+
550
  size_type count(const key_type& x) const;
551
+ template <class K> size_type count(const K& x) const;
552
 
553
  iterator lower_bound(const key_type& x);
554
  const_iterator lower_bound(const key_type& x) const;
555
+ template <class K> iterator lower_bound(const K& x);
556
+ template <class K> const_iterator lower_bound(const K& x) const;
557
+
558
  iterator upper_bound(const key_type& x);
559
  const_iterator upper_bound(const key_type& x) const;
560
+ template <class K> iterator upper_bound(const K& x);
561
+ template <class K> const_iterator upper_bound(const K& x) const;
562
 
563
  pair<iterator,iterator>
564
  equal_range(const key_type& x);
565
  pair<const_iterator,const_iterator>
566
  equal_range(const key_type& x) const;
567
+ template <class K>
568
+ pair<iterator, iterator> equal_range(const K& x);
569
+ template <class K>
570
+ pair<const_iterator, const_iterator> equal_range(const K& x) const;
571
  };
572
 
573
  template <class Key, class T, class Compare, class Allocator>
574
  bool operator==(const multimap<Key,T,Compare,Allocator>& x,
575
  const multimap<Key,T,Compare,Allocator>& y);
 
597
  ```
598
 
599
  #### `multimap` constructors <a id="multimap.cons">[[multimap.cons]]</a>
600
 
601
  ``` cpp
602
+ explicit multimap(const Compare& comp,
603
  const Allocator& = Allocator());
604
  ```
605
 
606
  *Effects:* Constructs an empty `multimap` using the specified comparison
607
  object and allocator.
 
613
  multimap(InputIterator first, InputIterator last,
614
  const Compare& comp = Compare(),
615
  const Allocator& = Allocator());
616
  ```
617
 
618
+ *Requires:* If the iterator’s indirection operator returns an lvalue or
619
  a const rvalue `pair<key_type, mapped_type>`, then both `key_type` and
620
+ `mapped_type` shall be `CopyInsertable` into `*this`.
621
 
622
  *Effects:* Constructs an empty `multimap` using the specified comparison
623
  object and allocator, and inserts elements from the range \[`first`,
624
  `last`).
625
 
 
631
  ``` cpp
632
  template <class P> iterator insert(P&& x);
633
  template <class P> iterator insert(const_iterator position, P&& x);
634
  ```
635
 
636
+ *Effects:* The first form is equivalent to
637
+ `return emplace(std::forward<P>(x))`. The second form is equivalent to
638
+ `return emplace_hint(position, std::forward<P>(x))`.
639
 
640
+ *Remarks:* These signatures shall not participate in overload resolution
641
+ unless `std::is_constructible<value_type, P&&>::value` is `true`.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
642
 
643
  #### `multimap` specialized algorithms <a id="multimap.special">[[multimap.special]]</a>
644
 
645
  ``` cpp
646
  template <class Key, class T, class Compare, class Allocator>
 
696
  typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
697
  typedef std::reverse_iterator<iterator> reverse_iterator;
698
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
699
 
700
  // [set.cons], construct/copy/destroy:
701
+ set() : set(Compare()) { }
702
+ explicit set(const Compare& comp,
703
  const Allocator& = Allocator());
704
  template <class InputIterator>
705
  set(InputIterator first, InputIterator last,
706
  const Compare& comp = Compare(), const Allocator& = Allocator());
707
+ set(const set& x);
708
+ set(set&& x);
709
  explicit set(const Allocator&);
710
  set(const set&, const Allocator&);
711
  set(set&&, const Allocator&);
712
  set(initializer_list<value_type>,
713
  const Compare& = Compare(),
714
  const Allocator& = Allocator());
715
+ template <class InputIterator>
716
+ set(InputIterator first, InputIterator last, const Allocator& a)
717
+ : set(first, last, Compare(), a) { }
718
+ set(initializer_list<value_type> il, const Allocator& a)
719
+ : set(il, Compare(), a) { }
720
  ~set();
721
+ set& operator=(const set& x);
722
+ set& operator=(set&& x);
 
 
723
  set& operator=(initializer_list<value_type>);
724
  allocator_type get_allocator() const noexcept;
725
 
726
  // iterators:
727
  iterator begin() noexcept;
 
756
  void insert(initializer_list<value_type>);
757
 
758
  iterator erase(const_iterator position);
759
  size_type erase(const key_type& x);
760
  iterator erase(const_iterator first, const_iterator last);
761
+ void swap(set&);
762
  void clear() noexcept;
763
 
764
  // observers:
765
  key_compare key_comp() const;
766
  value_compare value_comp() const;
767
 
768
  // set operations:
769
  iterator find(const key_type& x);
770
  const_iterator find(const key_type& x) const;
771
+ template <class K> iterator find(const K& x);
772
+ template <class K> const_iterator find(const K& x) const;
773
 
774
  size_type count(const key_type& x) const;
775
+ template <class K> size_type count(const K& x) const;
776
 
777
  iterator lower_bound(const key_type& x);
778
  const_iterator lower_bound(const key_type& x) const;
779
+ template <class K> iterator lower_bound(const K& x);
780
+ template <class K> const_iterator lower_bound(const K& x) const;
781
 
782
  iterator upper_bound(const key_type& x);
783
  const_iterator upper_bound(const key_type& x) const;
784
+ template <class K> iterator upper_bound(const K& x);
785
+ template <class K> const_iterator upper_bound(const K& x) const;
786
 
787
  pair<iterator,iterator> equal_range(const key_type& x);
788
  pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
789
+ template <class K>
790
+ pair<iterator, iterator> equal_range(const K& x);
791
+ template <class K>
792
+ pair<const_iterator, const_iterator> equal_range(const K& x) const;
793
  };
794
 
795
  template <class Key, class Compare, class Allocator>
796
  bool operator==(const set<Key,Compare,Allocator>& x,
797
  const set<Key,Compare,Allocator>& y);
 
819
  ```
820
 
821
  #### `set` constructors, copy, and assignment <a id="set.cons">[[set.cons]]</a>
822
 
823
  ``` cpp
824
+ explicit set(const Compare& comp,
825
  const Allocator& = Allocator());
826
  ```
827
 
828
  *Effects:* Constructs an empty set using the specified comparison
829
  objects and allocator.
 
838
 
839
  *Effects:* Constructs an empty `set` using the specified comparison
840
  object and allocator, and inserts elements from the range \[`first`,
841
  `last`).
842
 
843
+ *Requires:* If the iterator’s indirection operator returns an lvalue or
844
+ a non-const rvalue, then `Key` shall be `CopyInsertable` into `*this`.
845
 
846
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
847
  sorted using `comp` and otherwise N log N, where N is `last - first`.
848
 
849
  #### `set` specialized algorithms <a id="set.special">[[set.special]]</a>
 
903
  typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
904
  typedef std::reverse_iterator<iterator> reverse_iterator;
905
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
906
 
907
  // construct/copy/destroy:
908
+ multiset() : multiset(Compare()) { }
909
+ explicit multiset(const Compare& comp,
910
  const Allocator& = Allocator());
911
  template <class InputIterator>
912
  multiset(InputIterator first, InputIterator last,
913
  const Compare& comp = Compare(),
914
  const Allocator& = Allocator());
915
+ multiset(const multiset& x);
916
+ multiset(multiset&& x);
917
  explicit multiset(const Allocator&);
918
  multiset(const multiset&, const Allocator&);
919
  multiset(multiset&&, const Allocator&);
920
  multiset(initializer_list<value_type>,
921
  const Compare& = Compare(),
922
  const Allocator& = Allocator());
923
+ template <class InputIterator>
924
+ multiset(InputIterator first, InputIterator last, const Allocator& a)
925
+ : multiset(first, last, Compare(), a) { }
926
+ multiset(initializer_list<value_type> il, const Allocator& a)
927
+ : multiset(il, Compare(), a) { }
928
  ~multiset();
929
+ multiset& operator=(const multiset& x);
930
+ multiset& operator=(multiset&& x);
 
 
931
  multiset& operator=(initializer_list<value_type>);
932
  allocator_type get_allocator() const noexcept;
933
 
934
  // iterators:
935
  iterator begin() noexcept;
 
964
  void insert(initializer_list<value_type>);
965
 
966
  iterator erase(const_iterator position);
967
  size_type erase(const key_type& x);
968
  iterator erase(const_iterator first, const_iterator last);
969
+ void swap(multiset&);
970
  void clear() noexcept;
971
 
972
  // observers:
973
  key_compare key_comp() const;
974
  value_compare value_comp() const;
975
 
976
  // set operations:
977
  iterator find(const key_type& x);
978
  const_iterator find(const key_type& x) const;
979
+ template <class K> iterator find(const K& x);
980
+ template <class K> const_iterator find(const K& x) const;
981
 
982
  size_type count(const key_type& x) const;
983
+ template <class K> size_type count(const K& x) const;
984
 
985
  iterator lower_bound(const key_type& x);
986
  const_iterator lower_bound(const key_type& x) const;
987
+ template <class K> iterator lower_bound(const K& x);
988
+ template <class K> const_iterator lower_bound(const K& x) const;
989
 
990
  iterator upper_bound(const key_type& x);
991
  const_iterator upper_bound(const key_type& x) const;
992
+ template <class K> iterator upper_bound(const K& x);
993
+ template <class K> const_iterator upper_bound(const K& x) const;
994
 
995
  pair<iterator,iterator> equal_range(const key_type& x);
996
  pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
997
+ template <class K>
998
+ pair<iterator, iterator> equal_range(const K& x);
999
+ template <class K>
1000
+ pair<const_iterator, const_iterator> equal_range(const K& x) const;
1001
  };
1002
 
1003
  template <class Key, class Compare, class Allocator>
1004
  bool operator==(const multiset<Key,Compare,Allocator>& x,
1005
  const multiset<Key,Compare,Allocator>& y);
 
1027
  ```
1028
 
1029
  #### `multiset` constructors <a id="multiset.cons">[[multiset.cons]]</a>
1030
 
1031
  ``` cpp
1032
+ explicit multiset(const Compare& comp,
1033
  const Allocator& = Allocator());
1034
  ```
1035
 
1036
  *Effects:* Constructs an empty set using the specified comparison object
1037
  and allocator.
1038
 
1039
  *Complexity:* Constant.
1040
 
1041
  ``` cpp
1042
  template <class InputIterator>
1043
+ multiset(InputIterator first, InputIterator last,
1044
  const Compare& comp = Compare(), const Allocator& = Allocator());
1045
  ```
1046
 
1047
+ *Requires:* If the iterator’s indirection operator returns an lvalue or
1048
+ a const rvalue, then `Key` shall be `CopyInsertable` into `*this`.
1049
 
1050
  *Effects:* Constructs an empty `multiset` using the specified comparison
1051
  object and allocator, and inserts elements from the range \[`first`,
1052
  `last`).
1053