← Back to branch summary

~ubuntu-branches/ubuntu/vivid/emscripten/vivid

« back to all changes in this revision

Viewing changes to system/include/libcxx/unordered_map

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-09-20 22:44:35 UTC
  • mfrom: (4.1.1 sid)
  • Revision ID: package-import@ubuntu.com-20130920224435-apuwj4fsl3fqv1a6
Tags: 1.5.6~20130920~6010666-1
http://bugs.debian.org/723129
* New snapshot release
* Update the list of supported architectures to the same as libv8
  (Closes: #723129)
* emlibtool has been removed from upstream.
* Fix warning syntax-error-in-dep5-copyright
* Refresh of the patches

Show diffs side-by-side

added added

removed removed

Lines of Context:
system/include/libcxx/unordered_map
325
325
 
326
326
_LIBCPP_BEGIN_NAMESPACE_STD
327
327
 
328
 
template <class _Key, class _Tp, class _Hash, bool = is_empty<_Hash>::value
 
328
template <class _Key, class _Cp, class _Hash, bool = is_empty<_Hash>::value
329
329
#if __has_feature(is_final)
330
330
                                         && !__is_final(_Hash)
331
331
#endif
333
333
class __unordered_map_hasher
334
334
    : private _Hash
335
335
{
336
 
    typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
337
 
    typedef pair<const _Key, _Tp> _Cp;
338
336
public:
339
337
    _LIBCPP_INLINE_VISIBILITY
340
338
    __unordered_map_hasher()
347
345
    _LIBCPP_INLINE_VISIBILITY
348
346
    const _Hash& hash_function() const _NOEXCEPT {return *this;}
349
347
    _LIBCPP_INLINE_VISIBILITY
350
 
    size_t operator()(const _Pp& __x) const
351
 
        {return static_cast<const _Hash&>(*this)(__x.first);}
352
 
    _LIBCPP_INLINE_VISIBILITY
353
348
    size_t operator()(const _Cp& __x) const
354
 
        {return static_cast<const _Hash&>(*this)(__x.first);}
 
349
        {return static_cast<const _Hash&>(*this)(__x.__cc.first);}
355
350
    _LIBCPP_INLINE_VISIBILITY
356
351
    size_t operator()(const _Key& __x) const
357
352
        {return static_cast<const _Hash&>(*this)(__x);}
358
353
};
359
354
 
360
 
template <class _Key, class _Tp, class _Hash>
361
 
class __unordered_map_hasher<_Key, _Tp, _Hash, false>
 
355
template <class _Key, class _Cp, class _Hash>
 
356
class __unordered_map_hasher<_Key, _Cp, _Hash, false>
362
357
{
363
358
    _Hash __hash_;
364
359
 
365
 
    typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
366
 
    typedef pair<const _Key, _Tp> _Cp;
367
360
public:
368
361
    _LIBCPP_INLINE_VISIBILITY
369
362
    __unordered_map_hasher()
376
369
    _LIBCPP_INLINE_VISIBILITY
377
370
    const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
378
371
    _LIBCPP_INLINE_VISIBILITY
379
 
    size_t operator()(const _Pp& __x) const
380
 
        {return __hash_(__x.first);}
381
 
    _LIBCPP_INLINE_VISIBILITY
382
372
    size_t operator()(const _Cp& __x) const
383
 
        {return __hash_(__x.first);}
 
373
        {return __hash_(__x.__cc.first);}
384
374
    _LIBCPP_INLINE_VISIBILITY
385
375
    size_t operator()(const _Key& __x) const
386
376
        {return __hash_(__x);}
387
377
};
388
378
 
389
 
template <class _Key, class _Tp, class _Pred, bool = is_empty<_Pred>::value
 
379
template <class _Key, class _Cp, class _Pred, bool = is_empty<_Pred>::value
390
380
#if __has_feature(is_final)
391
381
                                         && !__is_final(_Pred)
392
382
#endif
394
384
class __unordered_map_equal
395
385
    : private _Pred
396
386
{
397
 
    typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
398
 
    typedef pair<const _Key, _Tp> _Cp;
399
387
public:
400
388
    _LIBCPP_INLINE_VISIBILITY
401
389
    __unordered_map_equal()
408
396
    _LIBCPP_INLINE_VISIBILITY
409
397
    const _Pred& key_eq() const _NOEXCEPT {return *this;}
410
398
    _LIBCPP_INLINE_VISIBILITY
411
 
    bool operator()(const _Pp& __x, const _Pp& __y) const
412
 
        {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
413
 
    _LIBCPP_INLINE_VISIBILITY
414
 
    bool operator()(const _Pp& __x, const _Cp& __y) const
415
 
        {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
416
 
    _LIBCPP_INLINE_VISIBILITY
417
 
    bool operator()(const _Pp& __x, const _Key& __y) const
418
 
        {return static_cast<const _Pred&>(*this)(__x.first, __y);}
419
 
    _LIBCPP_INLINE_VISIBILITY
420
 
    bool operator()(const _Cp& __x, const _Pp& __y) const
421
 
        {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
422
 
    _LIBCPP_INLINE_VISIBILITY
423
399
    bool operator()(const _Cp& __x, const _Cp& __y) const
424
 
        {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
 
400
        {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);}
425
401
    _LIBCPP_INLINE_VISIBILITY
426
402
    bool operator()(const _Cp& __x, const _Key& __y) const
427
 
        {return static_cast<const _Pred&>(*this)(__x.first, __y);}
428
 
    _LIBCPP_INLINE_VISIBILITY
429
 
    bool operator()(const _Key& __x, const _Pp& __y) const
430
 
        {return static_cast<const _Pred&>(*this)(__x, __y.first);}
 
403
        {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);}
431
404
    _LIBCPP_INLINE_VISIBILITY
432
405
    bool operator()(const _Key& __x, const _Cp& __y) const
433
 
        {return static_cast<const _Pred&>(*this)(__x, __y.first);}
434
 
    _LIBCPP_INLINE_VISIBILITY
435
 
    bool operator()(const _Key& __x, const _Key& __y) const
436
 
        {return static_cast<const _Pred&>(*this)(__x, __y);}
 
406
        {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);}
437
407
};
438
408
 
439
 
template <class _Key, class _Tp, class _Pred>
440
 
class __unordered_map_equal<_Key, _Tp, _Pred, false>
 
409
template <class _Key, class _Cp, class _Pred>
 
410
class __unordered_map_equal<_Key, _Cp, _Pred, false>
441
411
{
442
412
    _Pred __pred_;
443
413
 
444
 
    typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
445
 
    typedef pair<const _Key, _Tp> _Cp;
446
414
public:
447
415
    _LIBCPP_INLINE_VISIBILITY
448
416
    __unordered_map_equal()
455
423
    _LIBCPP_INLINE_VISIBILITY
456
424
    const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
457
425
    _LIBCPP_INLINE_VISIBILITY
458
 
    bool operator()(const _Pp& __x, const _Pp& __y) const
459
 
        {return __pred_(__x.first, __y.first);}
460
 
    _LIBCPP_INLINE_VISIBILITY
461
 
    bool operator()(const _Pp& __x, const _Cp& __y) const
462
 
        {return __pred_(__x.first, __y.first);}
463
 
    _LIBCPP_INLINE_VISIBILITY
464
 
    bool operator()(const _Pp& __x, const _Key& __y) const
465
 
        {return __pred_(__x.first, __y);}
466
 
    _LIBCPP_INLINE_VISIBILITY
467
 
    bool operator()(const _Cp& __x, const _Pp& __y) const
468
 
        {return __pred_(__x.first, __y.first);}
469
 
    _LIBCPP_INLINE_VISIBILITY
470
426
    bool operator()(const _Cp& __x, const _Cp& __y) const
471
 
        {return __pred_(__x.first, __y.first);}
 
427
        {return __pred_(__x.__cc.first, __y.__cc.first);}
472
428
    _LIBCPP_INLINE_VISIBILITY
473
429
    bool operator()(const _Cp& __x, const _Key& __y) const
474
 
        {return __pred_(__x.first, __y);}
475
 
    _LIBCPP_INLINE_VISIBILITY
476
 
    bool operator()(const _Key& __x, const _Pp& __y) const
477
 
        {return __pred_(__x, __y.first);}
 
430
        {return __pred_(__x.__cc.first, __y);}
478
431
    _LIBCPP_INLINE_VISIBILITY
479
432
    bool operator()(const _Key& __x, const _Cp& __y) const
480
 
        {return __pred_(__x, __y.first);}
481
 
    _LIBCPP_INLINE_VISIBILITY
482
 
    bool operator()(const _Key& __x, const _Key& __y) const
483
 
        {return __pred_(__x, __y);}
 
433
        {return __pred_(__x, __y.__cc.first);}
484
434
};
485
435
 
486
436
template <class _Alloc>
492
442
public:
493
443
    typedef typename __alloc_traits::pointer    pointer;
494
444
private:
495
 
    typedef typename value_type::first_type     first_type;
496
 
    typedef typename value_type::second_type    second_type;
 
445
    typedef typename value_type::value_type::first_type     first_type;
 
446
    typedef typename value_type::value_type::second_type    second_type;
497
447
 
498
448
    allocator_type& __na_;
499
449
 
535
485
    void operator()(pointer __p) _NOEXCEPT
536
486
    {
537
487
        if (__second_constructed)
538
 
            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second));
 
488
            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
539
489
        if (__first_constructed)
540
 
            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first));
 
490
            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
541
491
        if (__p)
542
492
            __alloc_traits::deallocate(__na_, __p, 1);
543
493
    }
549
499
    _HashIterator __i_;
550
500
 
551
501
    typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;
552
 
    typedef const typename _HashIterator::value_type::first_type key_type;
553
 
    typedef typename _HashIterator::value_type::second_type      mapped_type;
 
502
    typedef const typename _HashIterator::value_type::value_type::first_type key_type;
 
503
    typedef typename _HashIterator::value_type::value_type::second_type      mapped_type;
554
504
public:
555
505
    typedef forward_iterator_tag                                 iterator_category;
556
506
    typedef pair<key_type, mapped_type>                          value_type;
571
521
    __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
572
522
 
573
523
    _LIBCPP_INLINE_VISIBILITY
574
 
    reference operator*() const {return *operator->();}
 
524
    reference operator*() const {return __i_->__cc;}
575
525
    _LIBCPP_INLINE_VISIBILITY
576
 
    pointer operator->() const {return (pointer)__i_.operator->();}
 
526
    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
577
527
 
578
528
    _LIBCPP_INLINE_VISIBILITY
579
529
    __hash_map_iterator& operator++() {++__i_; return *this;}
605
555
    _HashIterator __i_;
606
556
 
607
557
    typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;
608
 
    typedef const typename _HashIterator::value_type::first_type key_type;
609
 
    typedef typename _HashIterator::value_type::second_type      mapped_type;
 
558
    typedef const typename _HashIterator::value_type::value_type::first_type key_type;
 
559
    typedef typename _HashIterator::value_type::value_type::second_type      mapped_type;
610
560
public:
611
561
    typedef forward_iterator_tag                                 iterator_category;
612
562
    typedef pair<key_type, mapped_type>                          value_type;
632
582
                : __i_(__i.__i_) {}
633
583
 
634
584
    _LIBCPP_INLINE_VISIBILITY
635
 
    reference operator*() const {return *operator->();}
 
585
    reference operator*() const {return __i_->__cc;}
636
586
    _LIBCPP_INLINE_VISIBILITY
637
 
    pointer operator->() const {return (pointer)__i_.operator->();}
 
587
    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
638
588
 
639
589
    _LIBCPP_INLINE_VISIBILITY
640
590
    __hash_map_const_iterator& operator++() {++__i_; return *this;}
671
621
    typedef _Pred                                          key_equal;
672
622
    typedef _Alloc                                         allocator_type;
673
623
    typedef pair<const key_type, mapped_type>              value_type;
 
624
    typedef pair<key_type, mapped_type>                    __nc_value_type;
674
625
    typedef value_type&                                    reference;
675
626
    typedef const value_type&                              const_reference;
 
627
    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
 
628
                  "Invalid allocator::value_type");
676
629
 
677
630
private:
678
 
    typedef pair<key_type, mapped_type>                    __value_type;
679
 
    typedef __unordered_map_hasher<key_type, mapped_type, hasher>   __hasher;
680
 
    typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal;
 
631
#if __cplusplus >= 201103L
 
632
    union __value_type
 
633
    {
 
634
        typedef typename unordered_map::value_type value_type;
 
635
        typedef typename unordered_map::__nc_value_type __nc_value_type;
 
636
        value_type __cc;
 
637
        __nc_value_type __nc;
 
638
 
 
639
        template <class ..._Args>
 
640
        __value_type(_Args&& ...__args)
 
641
            : __cc(std::forward<_Args>(__args)...) {}
 
642
 
 
643
        __value_type(const __value_type& __v)
 
644
            : __cc(std::move(__v.__cc)) {}
 
645
 
 
646
        __value_type(__value_type&& __v)
 
647
            : __nc(std::move(__v.__nc)) {}
 
648
 
 
649
        __value_type& operator=(const __value_type& __v)
 
650
            {__nc = __v.__cc; return *this;}
 
651
 
 
652
        __value_type& operator=(__value_type&& __v)
 
653
            {__nc = std::move(__v.__nc); return *this;}
 
654
 
 
655
        ~__value_type() {__cc.~value_type();}
 
656
    };
 
657
#else
 
658
    struct __value_type
 
659
    {
 
660
        typedef typename unordered_map::value_type value_type;
 
661
        value_type __cc;
 
662
 
 
663
        __value_type() {}
 
664
 
 
665
        template <class _A0>
 
666
        __value_type(const _A0& __a0)
 
667
            : __cc(__a0) {}
 
668
 
 
669
        template <class _A0, class _A1>
 
670
        __value_type(const _A0& __a0, const _A1& __a1)
 
671
            : __cc(__a0, __a1) {}
 
672
    };
 
673
#endif
 
674
    typedef __unordered_map_hasher<key_type, __value_type, hasher>   __hasher;
 
675
    typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
681
676
    typedef typename allocator_traits<allocator_type>::template
682
677
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
683
678
            rebind_alloc<__value_type>
713
708
    _LIBCPP_INLINE_VISIBILITY
714
709
    unordered_map()
715
710
        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
716
 
        {} // = default;
 
711
        {
 
712
#if _LIBCPP_DEBUG_LEVEL >= 2
 
713
            __get_db()->__insert_c(this);
 
714
#endif
 
715
        }
717
716
    explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
718
717
                           const key_equal& __eql = key_equal());
719
718
    unordered_map(size_type __n, const hasher& __hf,
750
749
    _LIBCPP_INLINE_VISIBILITY
751
750
    unordered_map& operator=(const unordered_map& __u)
752
751
    {
 
752
#if __cplusplus >= 201103L
753
753
        __table_ = __u.__table_;
 
754
#else
 
755
        __table_.clear();
 
756
        __table_.hash_function() = __u.__table_.hash_function();
 
757
        __table_.key_eq() = __u.__table_.key_eq();
 
758
        __table_.max_load_factor() = __u.__table_.max_load_factor();
 
759
        __table_.__copy_assign_alloc(__u.__table_);
 
760
        insert(__u.begin(), __u.end());
 
761
#endif
754
762
        return *this;
755
763
    }
756
764
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
793
801
 
794
802
    template <class... _Args>
795
803
        _LIBCPP_INLINE_VISIBILITY
 
804
#if _LIBCPP_DEBUG_LEVEL >= 2
 
805
        iterator emplace_hint(const_iterator __p, _Args&&... __args)
 
806
        {
 
807
            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 
808
                "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"
 
809
                " referring to this unordered_map");
 
810
            return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
 
811
        }
 
812
#else
796
813
        iterator emplace_hint(const_iterator, _Args&&... __args)
797
814
            {return emplace(_VSTD::forward<_Args>(__args)...).first;}
 
815
#endif
798
816
#endif  // _LIBCPP_HAS_NO_VARIADICS
799
817
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
800
818
    _LIBCPP_INLINE_VISIBILITY
808
826
            {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
809
827
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
810
828
    _LIBCPP_INLINE_VISIBILITY
 
829
#if _LIBCPP_DEBUG_LEVEL >= 2
 
830
    iterator insert(const_iterator __p, const value_type& __x)
 
831
        {
 
832
            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 
833
                "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
 
834
                " referring to this unordered_map");
 
835
            return insert(__x).first;
 
836
        }
 
837
#else
811
838
    iterator insert(const_iterator, const value_type& __x)
812
839
        {return insert(__x).first;}
 
840
#endif
813
841
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
814
842
    template <class _Pp,
815
843
              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
816
844
        _LIBCPP_INLINE_VISIBILITY
 
845
#if _LIBCPP_DEBUG_LEVEL >= 2
 
846
        iterator insert(const_iterator __p, _Pp&& __x)
 
847
        {
 
848
            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 
849
                "unordered_map::insert(const_iterator, value_type&&) called with an iterator not"
 
850
                " referring to this unordered_map");
 
851
            return insert(_VSTD::forward<_Pp>(__x)).first;
 
852
        }
 
853
#else
817
854
        iterator insert(const_iterator, _Pp&& __x)
818
855
            {return insert(_VSTD::forward<_Pp>(__x)).first;}
 
856
#endif
819
857
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
820
858
    template <class _InputIterator>
821
859
        void insert(_InputIterator __first, _InputIterator __last);
903
941
    _LIBCPP_INLINE_VISIBILITY
904
942
    void reserve(size_type __n) {__table_.reserve(__n);}
905
943
 
 
944
#if _LIBCPP_DEBUG_LEVEL >= 2
 
945
 
 
946
    bool __dereferenceable(const const_iterator* __i) const
 
947
        {return __table_.__dereferenceable(&__i->__i_);}
 
948
    bool __decrementable(const const_iterator* __i) const
 
949
        {return __table_.__decrementable(&__i->__i_);}
 
950
    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
 
951
        {return __table_.__addable(&__i->__i_, __n);}
 
952
    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
 
953
        {return __table_.__addable(&__i->__i_, __n);}
 
954
 
 
955
#endif  // _LIBCPP_DEBUG_LEVEL >= 2
 
956
 
906
957
private:
907
958
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
908
959
    __node_holder __construct_node();
909
960
    template <class _A0>
910
 
        typename enable_if
911
 
        <
912
 
            is_constructible<value_type, _A0>::value,
913
 
            __node_holder
914
 
        >::type
915
 
         __construct_node(_A0&& __a0);
916
 
    template <class _A0>
917
 
        typename enable_if
918
 
        <
919
 
            is_constructible<key_type, _A0>::value,
920
 
            __node_holder
921
 
        >::type
922
 
         __construct_node(_A0&& __a0);
 
961
        __node_holder
 
962
         __construct_node(_A0&& __a0);
 
963
    __node_holder __construct_node_with_key(key_type&& __k);
923
964
#ifndef _LIBCPP_HAS_NO_VARIADICS
924
965
    template <class _A0, class _A1, class ..._Args>
925
966
        __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
926
967
#endif  // _LIBCPP_HAS_NO_VARIADICS
927
 
#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
928
 
    __node_holder __construct_node(const key_type& __k);
929
 
#endif
 
968
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
969
    __node_holder __construct_node_with_key(const key_type& __k);
930
970
};
931
971
 
932
972
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
934
974
        size_type __n, const hasher& __hf, const key_equal& __eql)
935
975
    : __table_(__hf, __eql)
936
976
{
 
977
#if _LIBCPP_DEBUG_LEVEL >= 2
 
978
    __get_db()->__insert_c(this);
 
979
#endif
937
980
    __table_.rehash(__n);
938
981
}
939
982
 
943
986
        const allocator_type& __a)
944
987
    : __table_(__hf, __eql, __a)
945
988
{
 
989
#if _LIBCPP_DEBUG_LEVEL >= 2
 
990
    __get_db()->__insert_c(this);
 
991
#endif
946
992
    __table_.rehash(__n);
947
993
}
948
994
 
952
998
        const allocator_type& __a)
953
999
    : __table_(__a)
954
1000
{
 
1001
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1002
    __get_db()->__insert_c(this);
 
1003
#endif
955
1004
}
956
1005
 
957
1006
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
959
1008
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
960
1009
        _InputIterator __first, _InputIterator __last)
961
1010
{
 
1011
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1012
    __get_db()->__insert_c(this);
 
1013
#endif
962
1014
    insert(__first, __last);
963
1015
}
964
1016
 
969
1021
        const hasher& __hf, const key_equal& __eql)
970
1022
    : __table_(__hf, __eql)
971
1023
{
 
1024
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1025
    __get_db()->__insert_c(this);
 
1026
#endif
972
1027
    __table_.rehash(__n);
973
1028
    insert(__first, __last);
974
1029
}
980
1035
        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
981
1036
    : __table_(__hf, __eql, __a)
982
1037
{
 
1038
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1039
    __get_db()->__insert_c(this);
 
1040
#endif
983
1041
    __table_.rehash(__n);
984
1042
    insert(__first, __last);
985
1043
}
989
1047
        const unordered_map& __u)
990
1048
    : __table_(__u.__table_)
991
1049
{
 
1050
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1051
    __get_db()->__insert_c(this);
 
1052
#endif
992
1053
    __table_.rehash(__u.bucket_count());
993
1054
    insert(__u.begin(), __u.end());
994
1055
}
998
1059
        const unordered_map& __u, const allocator_type& __a)
999
1060
    : __table_(__u.__table_, __a)
1000
1061
{
 
1062
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1063
    __get_db()->__insert_c(this);
 
1064
#endif
1001
1065
    __table_.rehash(__u.bucket_count());
1002
1066
    insert(__u.begin(), __u.end());
1003
1067
}
1011
1075
    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1012
1076
    : __table_(_VSTD::move(__u.__table_))
1013
1077
{
 
1078
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1079
    __get_db()->__insert_c(this);
 
1080
    __get_db()->swap(this, &__u);
 
1081
#endif
1014
1082
}
1015
1083
 
1016
1084
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1018
1086
        unordered_map&& __u, const allocator_type& __a)
1019
1087
    : __table_(_VSTD::move(__u.__table_), __a)
1020
1088
{
 
1089
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1090
    __get_db()->__insert_c(this);
 
1091
#endif
1021
1092
    if (__a != __u.get_allocator())
1022
1093
    {
1023
1094
        iterator __i = __u.begin();
1026
1097
                _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
1027
1098
                                    );
1028
1099
    }
 
1100
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1101
    else
 
1102
        __get_db()->swap(this, &__u);
 
1103
#endif
1029
1104
}
1030
1105
 
1031
1106
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1036
1111
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1037
1112
        initializer_list<value_type> __il)
1038
1113
{
 
1114
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1115
    __get_db()->__insert_c(this);
 
1116
#endif
1039
1117
    insert(__il.begin(), __il.end());
1040
1118
}
1041
1119
 
1045
1123
        const key_equal& __eql)
1046
1124
    : __table_(__hf, __eql)
1047
1125
{
 
1126
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1127
    __get_db()->__insert_c(this);
 
1128
#endif
1048
1129
    __table_.rehash(__n);
1049
1130
    insert(__il.begin(), __il.end());
1050
1131
}
1055
1136
        const key_equal& __eql, const allocator_type& __a)
1056
1137
    : __table_(__hf, __eql, __a)
1057
1138
{
 
1139
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1140
    __get_db()->__insert_c(this);
 
1141
#endif
1058
1142
    __table_.rehash(__n);
1059
1143
    insert(__il.begin(), __il.end());
1060
1144
}
1105
1189
 
1106
1190
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1107
1191
template <class _A0>
1108
 
typename enable_if
1109
 
<
1110
 
    is_constructible<pair<const _Key, _Tp>, _A0>::value,
1111
 
    typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1112
 
>::type
 
1192
typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1113
1193
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1114
1194
{
1115
1195
    __node_allocator& __na = __table_.__node_alloc();
1122
1202
}
1123
1203
 
1124
1204
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1125
 
template <class _A0>
1126
 
typename enable_if
1127
 
<
1128
 
    is_constructible<_Key, _A0>::value,
1129
 
    typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1130
 
>::type
1131
 
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
 
1205
typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 
1206
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k)
1132
1207
{
1133
1208
    __node_allocator& __na = __table_.__node_alloc();
1134
1209
    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1135
 
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
1136
 
                             _VSTD::forward<_A0>(__a0));
 
1210
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
1137
1211
    __h.get_deleter().__first_constructed = true;
1138
 
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
 
1212
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1139
1213
    __h.get_deleter().__second_constructed = true;
1140
 
    return __h;
 
1214
    return _VSTD::move(__h);
1141
1215
}
1142
1216
 
1143
1217
#ifndef _LIBCPP_HAS_NO_VARIADICS
1172
1246
}
1173
1247
 
1174
1248
#endif  // _LIBCPP_HAS_NO_VARIADICS
1175
 
#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1249
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1176
1250
 
1177
1251
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1178
1252
typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1179
 
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
 
1253
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
1180
1254
{
1181
1255
    __node_allocator& __na = __table_.__node_alloc();
1182
1256
    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1183
 
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
 
1257
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1184
1258
    __h.get_deleter().__first_constructed = true;
1185
 
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
 
1259
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1186
1260
    __h.get_deleter().__second_constructed = true;
1187
1261
    return _VSTD::move(__h);
1188
1262
}
1189
1263
 
1190
 
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1191
 
 
1192
1264
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1193
1265
template <class _InputIterator>
1194
1266
inline _LIBCPP_INLINE_VISIBILITY
1207
1279
    iterator __i = find(__k);
1208
1280
    if (__i != end())
1209
1281
        return __i->second;
1210
 
    __node_holder __h = __construct_node(__k);
 
1282
    __node_holder __h = __construct_node_with_key(__k);
1211
1283
    pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1212
1284
    __h.release();
1213
1285
    return __r.first->second;
1222
1294
    iterator __i = find(__k);
1223
1295
    if (__i != end())
1224
1296
        return __i->second;
1225
 
    __node_holder __h = __construct_node(_VSTD::move(__k));
 
1297
    __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
1226
1298
    pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1227
1299
    __h.release();
1228
1300
    return __r.first->second;
1304
1376
    typedef _Pred                                          key_equal;
1305
1377
    typedef _Alloc                                         allocator_type;
1306
1378
    typedef pair<const key_type, mapped_type>              value_type;
 
1379
    typedef pair<key_type, mapped_type>                    __nc_value_type;
1307
1380
    typedef value_type&                                    reference;
1308
1381
    typedef const value_type&                              const_reference;
 
1382
    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
 
1383
                  "Invalid allocator::value_type");
1309
1384
 
1310
1385
private:
1311
 
    typedef pair<key_type, mapped_type>                    __value_type;
1312
 
    typedef __unordered_map_hasher<key_type, mapped_type, hasher>   __hasher;
1313
 
    typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal;
 
1386
#if __cplusplus >= 201103L
 
1387
    union __value_type
 
1388
    {
 
1389
        typedef typename unordered_multimap::value_type value_type;
 
1390
        typedef typename unordered_multimap::__nc_value_type __nc_value_type;
 
1391
        value_type __cc;
 
1392
        __nc_value_type __nc;
 
1393
 
 
1394
        template <class ..._Args>
 
1395
        __value_type(_Args&& ...__args)
 
1396
            : __cc(std::forward<_Args>(__args)...) {}
 
1397
 
 
1398
        __value_type(const __value_type& __v)
 
1399
            : __cc(std::move(__v.__cc)) {}
 
1400
 
 
1401
        __value_type(__value_type&& __v)
 
1402
            : __nc(std::move(__v.__nc)) {}
 
1403
 
 
1404
        __value_type& operator=(const __value_type& __v)
 
1405
            {__nc = __v.__cc; return *this;}
 
1406
 
 
1407
        __value_type& operator=(__value_type&& __v)
 
1408
            {__nc = std::move(__v.__nc); return *this;}
 
1409
 
 
1410
        ~__value_type() {__cc.~value_type();}
 
1411
    };
 
1412
#else
 
1413
    struct __value_type
 
1414
    {
 
1415
        typedef typename unordered_multimap::value_type value_type;
 
1416
        value_type __cc;
 
1417
 
 
1418
        __value_type() {}
 
1419
 
 
1420
        template <class _A0>
 
1421
        __value_type(const _A0& __a0)
 
1422
            : __cc(__a0) {}
 
1423
 
 
1424
        template <class _A0, class _A1>
 
1425
        __value_type(const _A0& __a0, const _A1& __a1)
 
1426
            : __cc(__a0, __a1) {}
 
1427
    };
 
1428
#endif
 
1429
    typedef __unordered_map_hasher<key_type, __value_type, hasher>   __hasher;
 
1430
    typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
1314
1431
    typedef typename allocator_traits<allocator_type>::template
1315
1432
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1316
1433
            rebind_alloc<__value_type>
1344
1461
    _LIBCPP_INLINE_VISIBILITY
1345
1462
    unordered_multimap()
1346
1463
        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1347
 
        {} // = default;
 
1464
        {
 
1465
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1466
            __get_db()->__insert_c(this);
 
1467
#endif
 
1468
        }
1348
1469
    explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1349
1470
                                const key_equal& __eql = key_equal());
1350
1471
    unordered_multimap(size_type __n, const hasher& __hf,
1382
1503
    _LIBCPP_INLINE_VISIBILITY
1383
1504
    unordered_multimap& operator=(const unordered_multimap& __u)
1384
1505
    {
 
1506
#if __cplusplus >= 201103L
1385
1507
        __table_ = __u.__table_;
 
1508
#else
 
1509
        __table_.clear();
 
1510
        __table_.hash_function() = __u.__table_.hash_function();
 
1511
        __table_.key_eq() = __u.__table_.key_eq();
 
1512
        __table_.max_load_factor() = __u.__table_.max_load_factor();
 
1513
        __table_.__copy_assign_alloc(__u.__table_);
 
1514
        insert(__u.begin(), __u.end());
 
1515
#endif
1386
1516
        return *this;
1387
1517
    }
1388
1518
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1525
1655
    _LIBCPP_INLINE_VISIBILITY
1526
1656
    void reserve(size_type __n) {__table_.reserve(__n);}
1527
1657
 
 
1658
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1659
 
 
1660
    bool __dereferenceable(const const_iterator* __i) const
 
1661
        {return __table_.__dereferenceable(&__i->__i_);}
 
1662
    bool __decrementable(const const_iterator* __i) const
 
1663
        {return __table_.__decrementable(&__i->__i_);}
 
1664
    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
 
1665
        {return __table_.__addable(&__i->__i_, __n);}
 
1666
    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
 
1667
        {return __table_.__addable(&__i->__i_, __n);}
 
1668
 
 
1669
#endif  // _LIBCPP_DEBUG_LEVEL >= 2
 
1670
 
1528
1671
private:
1529
1672
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1530
1673
    __node_holder __construct_node();
1531
1674
    template <class _A0>
1532
 
        typename enable_if
1533
 
        <
1534
 
            is_constructible<value_type, _A0>::value,
1535
 
            __node_holder
1536
 
        >::type
1537
 
         __construct_node(_A0&& __a0);
1538
 
    template <class _A0>
1539
 
        typename enable_if
1540
 
        <
1541
 
            is_constructible<key_type, _A0>::value,
1542
 
            __node_holder
1543
 
        >::type
 
1675
        __node_holder
1544
1676
         __construct_node(_A0&& __a0);
1545
1677
#ifndef _LIBCPP_HAS_NO_VARIADICS
1546
1678
    template <class _A0, class _A1, class ..._Args>
1554
1686
        size_type __n, const hasher& __hf, const key_equal& __eql)
1555
1687
    : __table_(__hf, __eql)
1556
1688
{
 
1689
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1690
    __get_db()->__insert_c(this);
 
1691
#endif
1557
1692
    __table_.rehash(__n);
1558
1693
}
1559
1694
 
1563
1698
        const allocator_type& __a)
1564
1699
    : __table_(__hf, __eql, __a)
1565
1700
{
 
1701
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1702
    __get_db()->__insert_c(this);
 
1703
#endif
1566
1704
    __table_.rehash(__n);
1567
1705
}
1568
1706
 
1571
1709
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1572
1710
        _InputIterator __first, _InputIterator __last)
1573
1711
{
 
1712
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1713
    __get_db()->__insert_c(this);
 
1714
#endif
1574
1715
    insert(__first, __last);
1575
1716
}
1576
1717
 
1581
1722
        const hasher& __hf, const key_equal& __eql)
1582
1723
    : __table_(__hf, __eql)
1583
1724
{
 
1725
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1726
    __get_db()->__insert_c(this);
 
1727
#endif
1584
1728
    __table_.rehash(__n);
1585
1729
    insert(__first, __last);
1586
1730
}
1592
1736
        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1593
1737
    : __table_(__hf, __eql, __a)
1594
1738
{
 
1739
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1740
    __get_db()->__insert_c(this);
 
1741
#endif
1595
1742
    __table_.rehash(__n);
1596
1743
    insert(__first, __last);
1597
1744
}
1602
1749
        const allocator_type& __a)
1603
1750
    : __table_(__a)
1604
1751
{
 
1752
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1753
    __get_db()->__insert_c(this);
 
1754
#endif
1605
1755
}
1606
1756
 
1607
1757
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1609
1759
        const unordered_multimap& __u)
1610
1760
    : __table_(__u.__table_)
1611
1761
{
 
1762
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1763
    __get_db()->__insert_c(this);
 
1764
#endif
1612
1765
    __table_.rehash(__u.bucket_count());
1613
1766
    insert(__u.begin(), __u.end());
1614
1767
}
1618
1771
        const unordered_multimap& __u, const allocator_type& __a)
1619
1772
    : __table_(__u.__table_, __a)
1620
1773
{
 
1774
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1775
    __get_db()->__insert_c(this);
 
1776
#endif
1621
1777
    __table_.rehash(__u.bucket_count());
1622
1778
    insert(__u.begin(), __u.end());
1623
1779
}
1631
1787
    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1632
1788
    : __table_(_VSTD::move(__u.__table_))
1633
1789
{
 
1790
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1791
    __get_db()->__insert_c(this);
 
1792
    __get_db()->swap(this, &__u);
 
1793
#endif
1634
1794
}
1635
1795
 
1636
1796
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1638
1798
        unordered_multimap&& __u, const allocator_type& __a)
1639
1799
    : __table_(_VSTD::move(__u.__table_), __a)
1640
1800
{
 
1801
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1802
    __get_db()->__insert_c(this);
 
1803
#endif
1641
1804
    if (__a != __u.get_allocator())
1642
1805
    {
1643
1806
        iterator __i = __u.begin();
1644
1807
        while (__u.size() != 0)
1645
 
{
 
1808
        {
1646
1809
            __table_.__insert_multi(
1647
1810
                _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
1648
1811
                                   );
1649
 
}
 
1812
        }
1650
1813
    }
 
1814
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1815
    else
 
1816
        __get_db()->swap(this, &__u);
 
1817
#endif
1651
1818
}
1652
1819
 
1653
1820
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1658
1825
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1659
1826
        initializer_list<value_type> __il)
1660
1827
{
 
1828
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1829
    __get_db()->__insert_c(this);
 
1830
#endif
1661
1831
    insert(__il.begin(), __il.end());
1662
1832
}
1663
1833
 
1667
1837
        const key_equal& __eql)
1668
1838
    : __table_(__hf, __eql)
1669
1839
{
 
1840
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1841
    __get_db()->__insert_c(this);
 
1842
#endif
1670
1843
    __table_.rehash(__n);
1671
1844
    insert(__il.begin(), __il.end());
1672
1845
}
1677
1850
        const key_equal& __eql, const allocator_type& __a)
1678
1851
    : __table_(__hf, __eql, __a)
1679
1852
{
 
1853
#if _LIBCPP_DEBUG_LEVEL >= 2
 
1854
    __get_db()->__insert_c(this);
 
1855
#endif
1680
1856
    __table_.rehash(__n);
1681
1857
    insert(__il.begin(), __il.end());
1682
1858
}
1727
1903
 
1728
1904
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1729
1905
template <class _A0>
1730
 
typename enable_if
1731
 
<
1732
 
    is_constructible<pair<const _Key, _Tp>, _A0>::value,
1733
 
    typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1734
 
>::type
 
1906
typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1735
1907
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1736
1908
{
1737
1909
    __node_allocator& __na = __table_.__node_alloc();
1743
1915
    return __h;
1744
1916
}
1745
1917
 
1746
 
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1747
 
template <class _A0>
1748
 
typename enable_if
1749
 
<
1750
 
    is_constructible<_Key, _A0>::value,
1751
 
    typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1752
 
>::type
1753
 
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1754
 
{
1755
 
    __node_allocator& __na = __table_.__node_alloc();
1756
 
    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1757
 
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
1758
 
                             _VSTD::forward<_A0>(__a0));
1759
 
    __h.get_deleter().__first_constructed = true;
1760
 
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
1761
 
    __h.get_deleter().__second_constructed = true;
1762
 
    return __h;
1763
 
}
1764
 
 
1765
1918
#ifndef _LIBCPP_HAS_NO_VARIADICS
1766
1919
 
1767
1920
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>