451 |
|
typedef _Ctptr const_pointer; |
452 |
|
typedef typename _Alloc::reference _Reft; |
453 |
|
typedef _Reft reference; |
454 |
|
typedef typename _Alloc::const_reference const_reference; |
455 |
|
typedef typename _Alloc::value_type value_type; |
456 |
|
|
457 |
|
#define _VEC_ITER_BASE(it) (it)._Myptr |
458 |
|
|
459 |
|
typedef _Vector_iterator<_Ty, _Alloc> iterator; |
460 |
|
typedef _Vector_const_iterator<_Ty, _Alloc> const_iterator; |
461 |
|
|
462 |
|
// friend class _Vector_iterator<_Ty, _Alloc>; |
463 |
|
friend class _Vector_const_iterator<_Ty, _Alloc>; |
464 |
|
|
465 |
|
typedef std::reverse_iterator<iterator> reverse_iterator; |
466 |
|
typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
467 |
|
|
468 |
|
vector() |
469 |
|
: _Mybase() |
470 |
|
{ // construct empty vector |
471 |
|
_Buy(0); |
472 |
|
} |
473 |
|
|
474 |
|
explicit vector(const _Alloc& _Al) |
475 |
|
: _Mybase(_Al) |
476 |
|
{ // construct empty vector with allocator |
477 |
|
_Buy(0); |
478 |
|
} |
479 |
|
|
480 |
|
explicit vector(size_type _Count) |
481 |
|
: _Mybase() |
482 |
|
{ // construct from _Count * _Ty() |
483 |
|
_Construct_n(_Count, _Ty()); |
484 |
|
} |
485 |
|
|
486 |
|
vector(size_type _Count, const _Ty& _Val) |
487 |
|
: _Mybase() |
488 |
|
{ // construct from _Count * _Val |
489 |
|
_Construct_n(_Count, _Val); |
490 |
|
} |
491 |
|
|
492 |
|
vector(size_type _Count, const _Ty& _Val, const _Alloc& _Al) |
493 |
|
: _Mybase(_Al) |
494 |
|
{ // construct from _Count * _Val, with allocator |
495 |
|
_Construct_n(_Count, _Val); |
496 |
|
} |
497 |
|
|
498 |
|
vector(const _Myt& _Right) |
499 |
|
: _Mybase(_Right._Alval) |
500 |
|
{ // construct by copying _Right |
501 |
|
if (_Buy(_Right.size())) |
502 |
|
_TRY_BEGIN |
503 |
|
_Mylast = _Ucopy(_Right.begin(), _Right.end(), _Myfirst); |
504 |
|
_CATCH_ALL |
505 |
|
_Tidy(); |
506 |
|
_RERAISE; |
507 |
|
_CATCH_END |
508 |
|
} |
509 |
|
|
510 |
|
template<class _Iter> |
511 |
|
vector(_Iter _First, _Iter _Last) |
512 |
|
: _Mybase() |
513 |
|
{ // construct from [_First, _Last) |
514 |
|
_Construct(_First, _Last, _Iter_cat(_First)); |
515 |
|
} |
516 |
|
|
517 |
|
template<class _Iter> |
518 |
|
vector(_Iter _First, _Iter _Last, const _Alloc& _Al) |
519 |
|
: _Mybase(_Al) |
520 |
|
{ // construct from [_First, _Last), with allocator |
521 |
|
_Construct(_First, _Last, _Iter_cat(_First)); |
522 |
|
} |
523 |
|
|
524 |
|
template<class _Iter> |
525 |
|
void _Construct(_Iter _Count, _Iter _Val, _Int_iterator_tag) |
526 |
|
{ // initialize with _Count * _Val |
527 |
|
size_type _Size = (size_type)_Count; |
528 |
|
_Construct_n(_Size, (_Ty)_Val); |
529 |
|
} |
530 |
|
|
531 |
|
template<class _Iter> |
532 |
|
void _Construct(_Iter _First, |
533 |
|
_Iter _Last, input_iterator_tag) |
534 |
|
{ // initialize with [_First, _Last), input iterators |
535 |
|
_Buy(0); |
536 |
|
_TRY_BEGIN |
537 |
|
insert(begin(), _First, _Last); |
538 |
|
_CATCH_ALL |
539 |
|
_Tidy(); |
540 |
|
_RERAISE; |
541 |
|
_CATCH_END |
542 |
|
} |
543 |
|
|
544 |
|
void _Construct_n(size_type _Count, const _Ty& _Val) |
545 |
|
{ // construct from _Count * _Val |
546 |
|
if (_Buy(_Count)) |
547 |
|
{ // nonzero, fill it |
548 |
|
_TRY_BEGIN |
549 |
|
_Mylast = _Ufill(_Myfirst, _Count, _Val); |
550 |
|
_CATCH_ALL |
551 |
|
_Tidy(); |
552 |
|
_RERAISE; |
553 |
|
_CATCH_END |
554 |
|
} |
555 |
|
} |
556 |
|
|
557 |
|
~vector() |
558 |
|
{ // destroy the object |
559 |
|
_Tidy(); |
560 |
|
} |
561 |
|
|
562 |
|
_Myt& operator=(const _Myt& _Right) |
563 |
|
{ // assign _Right |
564 |
|
if (this != &_Right) |
565 |
|
{ // worth doing |
566 |
|
|
567 |
|
#if _HAS_ITERATOR_DEBUGGING |
568 |
|
this->_Orphan_all(); |
569 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
570 |
|
|
571 |
|
if (_Right.size() == 0) |
572 |
|
clear(); // new sequence empty, erase existing sequence |
573 |
|
else if (_Right.size() <= size()) |
574 |
|
{ // enough elements, copy new and destroy old |
575 |
|
pointer _Ptr = _STDEXT unchecked_copy(_Right._Myfirst, _Right._Mylast, |
576 |
|
_Myfirst); // copy new |
577 |
|
_Destroy(_Ptr, _Mylast); // destroy old |
578 |
|
_Mylast = _Myfirst + _Right.size(); |
579 |
|
} |
580 |
|
else if (_Right.size() <= capacity()) |
581 |
|
{ // enough room, copy and construct new |
582 |
|
pointer _Ptr = _Right._Myfirst + size(); |
583 |
|
_STDEXT unchecked_copy(_Right._Myfirst, _Ptr, _Myfirst); |
584 |
|
_Mylast = _Ucopy(_Ptr, _Right._Mylast, _Mylast); |
585 |
|
} |
586 |
|
else |
587 |
|
{ // not enough room, allocate new array and construct new |
588 |
|
if (_Myfirst != 0) |
589 |
|
{ // discard old array |
590 |
|
_Destroy(_Myfirst, _Mylast); |
591 |
|
this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst); |
592 |
|
} |
593 |
|
if (_Buy(_Right.size())) |
594 |
|
_Mylast = _Ucopy(_Right._Myfirst, _Right._Mylast, |
595 |
|
_Myfirst); |
596 |
|
} |
597 |
|
} |
598 |
|
return (*this); |
599 |
|
} |
600 |
|
|
601 |
|
void reserve(size_type _Count) |
602 |
|
{ // determine new minimum length of allocated storage |
603 |
|
if (max_size() < _Count) |
604 |
|
_Xlen(); // result too long |
605 |
|
else if (capacity() < _Count) |
606 |
|
{ // not enough room, reallocate |
607 |
|
pointer _Ptr = this->_Alval.allocate(_Count); |
608 |
|
|
609 |
|
_TRY_BEGIN |
610 |
|
_Umove(begin(), end(), _Ptr); |
611 |
|
_CATCH_ALL |
612 |
|
this->_Alval.deallocate(_Ptr, _Count); |
613 |
|
_RERAISE; |
614 |
|
_CATCH_END |
615 |
|
|
616 |
|
size_type _Size = size(); |
617 |
|
if (_Myfirst != 0) |
618 |
|
{ // destroy and deallocate old array |
619 |
|
_Destroy(_Myfirst, _Mylast); |
620 |
|
this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst); |
621 |
|
} |
622 |
|
|
623 |
|
#if _HAS_ITERATOR_DEBUGGING |
624 |
|
this->_Orphan_all(); |
625 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
626 |
|
|
627 |
|
_Myend = _Ptr + _Count; |
628 |
|
_Mylast = _Ptr + _Size; |
629 |
|
_Myfirst = _Ptr; |
630 |
|
} |
631 |
|
} |
632 |
|
|
633 |
|
size_type capacity() const |
634 |
|
{ // return current length of allocated storage |
635 |
|
return (_Myfirst == 0 ? 0 : _Myend - _Myfirst); |
636 |
|
} |
637 |
|
|
638 |
|
#if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL |
639 |
|
iterator begin() |
640 |
|
{ // return iterator for beginning of mutable sequence |
641 |
|
return (iterator(_Myfirst, this)); |
642 |
|
} |
643 |
|
|
644 |
|
const_iterator begin() const |
645 |
|
{ // return iterator for beginning of nonmutable sequence |
646 |
|
return (const_iterator(_Myfirst, this)); |
647 |
|
} |
648 |
|
|
649 |
|
iterator end() |
650 |
|
{ // return iterator for end of mutable sequence |
651 |
|
return (iterator(_Mylast, this)); |
652 |
|
} |
653 |
|
|
654 |
|
const_iterator end() const |
655 |
|
{ // return iterator for end of nonmutable sequence |
656 |
|
return (const_iterator(_Mylast, this)); |
657 |
|
} |
658 |
|
|
659 |
|
iterator _Make_iter(const_iterator _Where) const |
660 |
|
{ // make iterator from const_iterator |
661 |
|
return (iterator(_Where._Myptr, this)); |
662 |
|
} |
663 |
|
|
664 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
665 |
|
iterator begin() |
666 |
|
{ // return iterator for beginning of mutable sequence |
667 |
|
return (iterator(_Myfirst)); |
668 |
|
} |
669 |
|
|
670 |
|
const_iterator begin() const |
671 |
|
{ // return iterator for beginning of nonmutable sequence |
672 |
|
return (const_iterator(_Myfirst)); |
673 |
|
} |
674 |
|
|
675 |
|
iterator end() |
676 |
|
{ // return iterator for end of mutable sequence |
677 |
|
return (iterator(_Mylast)); |
678 |
|
} |
679 |
|
|
680 |
|
const_iterator end() const |
681 |
|
{ // return iterator for end of nonmutable sequence |
682 |
|
return (const_iterator(_Mylast)); |
683 |
|
} |
684 |
|
|
685 |
|
iterator _Make_iter(const_iterator _Where) const |
686 |
|
{ // make iterator from const_iterator |
687 |
|
return (iterator(_Where._Myptr)); |
688 |
|
} |
689 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
690 |
|
|
691 |
|
reverse_iterator rbegin() |
692 |
|
{ // return iterator for beginning of reversed mutable sequence |
693 |
|
return (reverse_iterator(end())); |
694 |
|
} |
695 |
|
|
696 |
|
const_reverse_iterator rbegin() const |
697 |
|
{ // return iterator for beginning of reversed nonmutable sequence |
698 |
|
return (const_reverse_iterator(end())); |
699 |
|
} |
700 |
|
|
701 |
|
reverse_iterator rend() |
702 |
|
{ // return iterator for end of reversed mutable sequence |
703 |
|
return (reverse_iterator(begin())); |
704 |
|
} |
705 |
|
|
706 |
|
const_reverse_iterator rend() const |
707 |
|
{ // return iterator for end of reversed nonmutable sequence |
708 |
|
return (const_reverse_iterator(begin())); |
709 |
|
} |
710 |
|
|
711 |
|
void resize(size_type _Newsize) |
712 |
|
{ // determine new length, padding with _Ty() elements as needed |
713 |
|
resize(_Newsize, _Ty()); |
714 |
|
} |
715 |
|
|
716 |
|
void resize(size_type _Newsize, _Ty _Val) |
717 |
|
{ // determine new length, padding with _Val elements as needed |
718 |
|
if (size() < _Newsize) |
719 |
|
_Insert_n(end(), _Newsize - size(), _Val); |
720 |
|
else if (_Newsize < size()) |
721 |
|
erase(begin() + _Newsize, end()); |
722 |
|
} |
723 |
|
|
724 |
|
size_type size() const |
725 |
|
{ // return length of sequence |
726 |
|
return (_Mylast - _Myfirst); |
727 |
|
} |
728 |
|
|
729 |
|
size_type max_size() const |
730 |
|
{ // return maximum possible length of sequence |
731 |
|
return (this->_Alval.max_size()); |
732 |
|
} |
733 |
|
|
734 |
|
bool empty() const |
735 |
|
{ // test if sequence is empty |
736 |
|
return (size() == 0); |
737 |
|
} |
738 |
|
|
739 |
|
_Alloc get_allocator() const |
740 |
|
{ // return allocator object for values |
741 |
|
return (this->_Alval); |
742 |
|
} |
743 |
|
|
744 |
|
const_reference at(size_type _Pos) const |
745 |
|
{ // subscript nonmutable sequence with checking |
746 |
|
if (size() <= _Pos) |
747 |
|
_Xran(); |
748 |
|
return (*(begin() + _Pos)); |
749 |
|
} |
750 |
|
|
751 |
|
reference at(size_type _Pos) |
752 |
|
{ // subscript mutable sequence with checking |
753 |
|
if (size() <= _Pos) |
754 |
|
_Xran(); |
755 |
|
return (*(begin() + _Pos)); |
756 |
|
} |
757 |
|
|
758 |
|
const_reference operator[](size_type _Pos) const |
759 |
|
{ // subscript nonmutable sequence |
760 |
|
|
761 |
|
#if _HAS_ITERATOR_DEBUGGING |
762 |
|
if (size() <= _Pos) |
763 |
|
{ |
764 |
|
_DEBUG_ERROR("vector subscript out of range"); |
765 |
|
_SCL_SECURE_OUT_OF_RANGE; |
766 |
|
} |
767 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
768 |
|
_SCL_SECURE_VALIDATE_RANGE(_Pos < size()); |
769 |
|
|
770 |
|
return (*(_Myfirst + _Pos)); |
771 |
|
} |
772 |
|
|
773 |
|
reference operator[](size_type _Pos) |
774 |
|
{ // subscript mutable sequence |
775 |
|
|
776 |
|
#if _HAS_ITERATOR_DEBUGGING |
777 |
|
if (size() <= _Pos) |
778 |
|
{ |
779 |
|
_DEBUG_ERROR("vector subscript out of range"); |
780 |
|
_SCL_SECURE_OUT_OF_RANGE; |
781 |
|
} |
782 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
783 |
|
_SCL_SECURE_VALIDATE_RANGE(_Pos < size()); |
784 |
|
|
785 |
|
return (*(_Myfirst + _Pos)); |
786 |
|
} |
787 |
|
|
788 |
|
reference front() |
789 |
|
{ // return first element of mutable sequence |
790 |
|
return (*begin()); |
791 |
|
} |
792 |
|
|
793 |
|
const_reference front() const |
794 |
|
{ // return first element of nonmutable sequence |
795 |
|
return (*begin()); |
796 |
|
} |
797 |
|
|
798 |
|
reference back() |
799 |
|
{ // return last element of mutable sequence |
800 |
|
return (*(end() - 1)); |
801 |
|
} |
802 |
|
|
803 |
|
const_reference back() const |
804 |
|
{ // return last element of nonmutable sequence |
805 |
|
return (*(end() - 1)); |
806 |
|
} |
807 |
|
|
808 |
|
void push_back(const _Ty& _Val) |
809 |
|
{ // insert element at end |
810 |
|
if (size() < capacity()) |
811 |
|
|
812 |
|
#if _HAS_ITERATOR_DEBUGGING |
813 |
|
{ // room at end, construct it there |
814 |
|
_Orphan_range(_Mylast, _Mylast); |
815 |
|
_Mylast = _Ufill(_Mylast, 1, _Val); |
816 |
|
} |
817 |
|
|
818 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
819 |
|
_Mylast = _Ufill(_Mylast, 1, _Val); |
820 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
821 |
|
|
822 |
|
else |
823 |
|
insert(end(), _Val); |
824 |
|
} |
825 |
|
|
826 |
|
#if _HAS_ITERATOR_DEBUGGING |
827 |
|
void pop_back() |
828 |
|
{ // erase element at end |
829 |
|
if (empty()) |
830 |
|
_DEBUG_ERROR("vector empty before pop"); |
831 |
|
else |
832 |
|
{ // erase last element |
833 |
|
_Orphan_range(_Mylast - 1, _Mylast); |
834 |
|
_Destroy(_Mylast - 1, _Mylast); |
835 |
|
--_Mylast; |
836 |
|
} |
837 |
|
} |
838 |
|
|
839 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
840 |
|
void pop_back() |
841 |
|
{ // erase element at end |
842 |
|
if (!empty()) |
843 |
|
{ // erase last element |
844 |
|
_Destroy(_Mylast - 1, _Mylast); |
845 |
|
--_Mylast; |
846 |
|
} |
847 |
|
} |
848 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
849 |
|
|
850 |
|
template<class _Iter> |
851 |
|
void assign(_Iter _First, _Iter _Last) |
852 |
|
{ // assign [_First, _Last) |
853 |
|
_Assign(_First, _Last, _Iter_cat(_First)); |
854 |
|
} |
855 |
|
|
856 |
|
template<class _Iter> |
857 |
|
void _Assign(_Iter _Count, _Iter _Val, _Int_iterator_tag) |
858 |
|
{ // assign _Count * _Val |
859 |
|
_Assign_n((size_type)_Count, (_Ty)_Val); |
860 |
|
} |
861 |
|
|
862 |
|
template<class _Iter> |
863 |
|
void _Assign(_Iter _First, _Iter _Last, input_iterator_tag) |
864 |
|
{ // assign [_First, _Last), input iterators |
865 |
|
erase(begin(), end()); |
866 |
|
insert(begin(), _First, _Last); |
867 |
|
} |
868 |
|
|
869 |
|
void assign(size_type _Count, const _Ty& _Val) |
870 |
|
{ // assign _Count * _Val |
871 |
|
_Assign_n(_Count, _Val); |
872 |
|
} |
873 |
|
|
874 |
|
iterator insert(const_iterator _Where, const _Ty& _Val) |
875 |
|
{ // insert _Val at _Where |
876 |
|
size_type _Off = size() == 0 ? 0 : _Where - begin(); |
877 |
|
_Insert_n(_Where, (size_type)1, _Val); |
878 |
|
return (begin() + _Off); |
879 |
|
} |
880 |
|
|
881 |
|
void insert(const_iterator _Where, size_type _Count, const _Ty& _Val) |
882 |
|
{ // insert _Count * _Val at _Where |
883 |
|
_Insert_n(_Where, _Count, _Val); |
884 |
|
} |
885 |
|
|
886 |
|
template<class _Iter> |
887 |
|
void insert(const_iterator _Where, _Iter _First, _Iter _Last) |
888 |
|
{ // insert [_First, _Last) at _Where |
889 |
|
_Insert(_Where, _First, _Last, _Iter_cat(_First)); |
890 |
|
} |
891 |
|
|
892 |
|
template<class _Iter> |
893 |
|
void _Insert(const_iterator _Where, _Iter _First, _Iter _Last, |
894 |
|
_Int_iterator_tag) |
895 |
|
{ // insert _Count * _Val at _Where |
896 |
|
_Insert_n(_Where, (size_type)_First, (_Ty)_Last); |
897 |
|
} |
898 |
|
|
899 |
|
template<class _Iter> |
900 |
|
void _Insert(const_iterator _Where, _Iter _First, _Iter _Last, |
901 |
|
input_iterator_tag) |
902 |
|
{ // insert [_First, _Last) at _Where, input iterators |
903 |
|
|
904 |
|
#if _HAS_ITERATOR_DEBUGGING |
905 |
|
if (_Where._Mycont != this |
906 |
|
|| _Where._Myptr < _Myfirst || _Mylast < _Where._Myptr) |
907 |
|
_DEBUG_ERROR("vector insert iterator outside range"); |
908 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
909 |
|
|
910 |
|
if (_First != _Last) |
911 |
|
{ // worth doing, gather at end and rotate into place |
912 |
|
size_type _Oldsize = size(); |
913 |
|
size_type _Whereoff = _Where._Myptr - _Myfirst; |
914 |
|
|
915 |
|
for (; _First != _Last; ++_First) |
916 |
|
_Insert_n(end(), (size_type)1, (value_type)*_First); |
917 |
|
|
918 |
|
_Reverse(_Myfirst + _Whereoff, _Myfirst + _Oldsize); |
919 |
|
_Reverse(_Myfirst + _Oldsize, _Mylast); |
920 |
|
_Reverse(_Myfirst + _Whereoff, _Mylast); |
921 |
|
} |
922 |
|
} |
923 |
|
|
924 |
|
template<class _Iter> |
925 |
|
void _Insert(const_iterator _Where, |
926 |
|
_Iter _First, _Iter _Last, forward_iterator_tag) |
927 |
|
{ // insert [_First, _Last) at _Where, forward iterators |
928 |
|
|
929 |
|
#if _HAS_ITERATOR_DEBUGGING |
930 |
|
if (_Where._Mycont != this |
931 |
|
|| _Where._Myptr < _Myfirst || _Mylast < _Where._Myptr) |
932 |
|
_DEBUG_ERROR("vector insert iterator outside range"); |
933 |
|
_DEBUG_RANGE(_First, _Last); |
934 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
935 |
|
|
936 |
|
size_type _Count = 0; |
937 |
|
_Distance(_First, _Last, _Count); |
938 |
|
size_type _Capacity = capacity(); |
939 |
|
|
940 |
|
if (_Count == 0) |
941 |
|
; |
942 |
|
else if (max_size() - size() < _Count) |
943 |
|
_Xlen(); // result too long |
944 |
|
else if (_Capacity < size() + _Count) |
945 |
|
{ // not enough room, reallocate |
946 |
|
_Capacity = max_size() - _Capacity / 2 < _Capacity |
947 |
|
? 0 : _Capacity + _Capacity / 2; // try to grow by 50% |
948 |
|
if (_Capacity < size() + _Count) |
949 |
|
_Capacity = size() + _Count; |
950 |
|
pointer _Newvec = this->_Alval.allocate(_Capacity); |
951 |
|
pointer _Ptr = _Newvec; |
952 |
|
|
953 |
|
_TRY_BEGIN |
954 |
|
_Ptr = _Umove(_Myfirst, _VEC_ITER_BASE(_Where), |
955 |
|
_Newvec); // copy prefix |
956 |
|
_Ptr = _Ucopy(_First, _Last, _Ptr); // add new stuff |
957 |
|
_Umove(_VEC_ITER_BASE(_Where), _Mylast, _Ptr); // copy suffix |
958 |
|
_CATCH_ALL |
959 |
|
_Destroy(_Newvec, _Ptr); |
960 |
|
this->_Alval.deallocate(_Newvec, _Capacity); |
961 |
|
_RERAISE; |
962 |
|
_CATCH_END |
963 |
|
|
964 |
|
_Count += size(); |
965 |
|
if (_Myfirst != 0) |
966 |
|
{ // destroy and deallocate old array |
967 |
|
_Destroy(_Myfirst, _Mylast); |
968 |
|
this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst); |
969 |
|
} |
970 |
|
|
971 |
|
#if _HAS_ITERATOR_DEBUGGING |
972 |
|
this->_Orphan_all(); |
973 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
974 |
|
|
975 |
|
_Myend = _Newvec + _Capacity; |
976 |
|
_Mylast = _Newvec + _Count; |
977 |
|
_Myfirst = _Newvec; |
978 |
|
} |
979 |
|
else |
980 |
|
{ // new stuff fits, append and rotate into place |
981 |
|
_Ucopy(_First, _Last, _Mylast); |
982 |
|
|
983 |
|
_Reverse(_Where._Myptr, _Mylast); |
984 |
|
_Reverse(_Mylast, _Mylast + _Count); |
985 |
|
_Reverse(_Where._Myptr, _Mylast + _Count); |
986 |
|
|
987 |
|
_Mylast += _Count; |
988 |
|
|
989 |
|
#if _HAS_ITERATOR_DEBUGGING |
990 |
|
_Orphan_range(_Where._Myptr, _Mylast); |
991 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
992 |
|
|
993 |
|
} |
994 |
|
} |
995 |
|
|
996 |
|
void _Reverse(pointer _First, pointer _Last) |
997 |
|
{ // reverse a subrange |
998 |
|
for (; _First != _Last && _First != --_Last; ++_First) |
999 |
|
_STD _Swap_adl(*_First, *_Last); |
1000 |
|
} |
1001 |
|
|
1002 |
|
#if _HAS_ITERATOR_DEBUGGING |
1003 |
|
iterator erase(const_iterator _Where) |
1004 |
|
{ // erase element at where |
1005 |
|
if (_Where._Mycont != this |
1006 |
|
|| _Where._Myptr < _Myfirst || _Mylast <= _Where._Myptr) |
1007 |
|
_DEBUG_ERROR("vector erase iterator outside range"); |
1008 |
|
_STDEXT unchecked_copy(_Where._Myptr + 1, _Mylast, _Where._Myptr); |
1009 |
|
_Destroy(_Mylast - 1, _Mylast); |
1010 |
|
_Orphan_range(_Where._Myptr, _Mylast); |
1011 |
|
--_Mylast; |
1012 |
|
return (iterator(_Where._Myptr, this)); |
1013 |
|
} |
1014 |
|
|
1015 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
1016 |
|
iterator erase(const_iterator _Where) |
1017 |
|
{ // erase element at where |
1018 |
|
_STDEXT unchecked_copy(_VEC_ITER_BASE(_Where) + 1, _Mylast, |
1019 |
|
_VEC_ITER_BASE(_Where)); |
1020 |
|
_Destroy(_Mylast - 1, _Mylast); |
1021 |
|
--_Mylast; |
1022 |
|
return (_Make_iter(_Where)); |
1023 |
|
} |
1024 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1025 |
|
|
1026 |
|
iterator erase(const_iterator _First_arg, |
1027 |
|
const_iterator _Last_arg) |
1028 |
|
{ // erase [_First, _Last) |
1029 |
|
iterator _First = _Make_iter(_First_arg); |
1030 |
|
iterator _Last = _Make_iter(_Last_arg); |
1031 |
|
|
1032 |
|
if (_First != _Last) |
1033 |
|
{ // worth doing, copy down over hole |
1034 |
|
|
1035 |
|
#if _HAS_ITERATOR_DEBUGGING |
1036 |
|
if (_Last < _First || _First._Mycont != this |
1037 |
|
|| _First._Myptr < _Myfirst || _Mylast < _Last._Myptr) |
1038 |
|
_DEBUG_ERROR("vector erase iterator outside range"); |
1039 |
|
pointer _Ptr = _STDEXT unchecked_copy(_VEC_ITER_BASE(_Last), _Mylast, |
1040 |
|
_VEC_ITER_BASE(_First)); |
1041 |
|
_Orphan_range(_First._Myptr, _Mylast); |
1042 |
|
|
1043 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
1044 |
|
pointer _Ptr = _STDEXT unchecked_copy(_VEC_ITER_BASE(_Last), _Mylast, |
1045 |
|
_VEC_ITER_BASE(_First)); |
1046 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1047 |
|
|
1048 |
|
_Destroy(_Ptr, _Mylast); |
1049 |
|
_Mylast = _Ptr; |
1050 |
|
} |
1051 |
|
#if _HAS_ITERATOR_DEBUGGING |
1052 |
|
return (iterator(_First._Myptr, this)); |
1053 |
|
#else |
1054 |
|
return (_First); |
1055 |
|
#endif |
1056 |
|
} |
1057 |
|
|
1058 |
|
void clear() |
1059 |
|
{ // erase all |
1060 |
|
erase(begin(), end()); |
1061 |
|
} |
1062 |
|
|
1063 |
|
void swap(_Myt& _Right) |
1064 |
|
{ // exchange contents with _Right |
1065 |
|
if (this == &_Right) |
1066 |
|
; // same object, do nothing |
1067 |
|
else if (this->_Alval == _Right._Alval) |
1068 |
|
{ // same allocator, swap control information |
1069 |
|
|
1070 |
|
#if _HAS_ITERATOR_DEBUGGING |
1071 |
|
this->_Swap_all(_Right); |
1072 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1073 |
|
|
1074 |
|
this->_Swap_aux(_Right); |
1075 |
|
|
1076 |
|
_STD swap(_Myfirst, _Right._Myfirst); |
1077 |
|
_STD swap(_Mylast, _Right._Mylast); |
1078 |
|
_STD swap(_Myend, _Right._Myend); |
1079 |
|
} |
1080 |
|
else |
1081 |
|
{ // different allocator, do multiple assigns |
1082 |
|
this->_Swap_aux(_Right); |
1083 |
|
|
1084 |
|
_Myt _Ts = *this; |
1085 |
|
|
1086 |
|
*this = _Right; |
1087 |
|
_Right = _Ts; |
1088 |
|
} |
1089 |
|
} |
1090 |
|
|
1091 |
|
|
1092 |
|
|
1093 |
|
protected: |
1094 |
|
void _Assign_n(size_type _Count, const _Ty& _Val) |
1095 |
|
{ // assign _Count * _Val |
1096 |
|
_Ty _Tmp = _Val; // in case _Val is in sequence |
1097 |
|
erase(begin(), end()); |
1098 |
|
insert(begin(), _Count, _Tmp); |
1099 |
|
} |
1100 |
|
|
1101 |
|
bool _Buy(size_type _Capacity) |
1102 |
|
{ // allocate array with _Capacity elements |
1103 |
|
_Myfirst = 0, _Mylast = 0, _Myend = 0; |
1104 |
|
if (_Capacity == 0) |
1105 |
|
return (false); |
1106 |
|
else if (max_size() < _Capacity) |
1107 |
|
_Xlen(); // result too long |
1108 |
|
else |
1109 |
|
{ // nonempty array, allocate storage |
1110 |
|
_Myfirst = this->_Alval.allocate(_Capacity); |
1111 |
|
_Mylast = _Myfirst; |
1112 |
|
_Myend = _Myfirst + _Capacity; |
1113 |
|
} |
1114 |
|
return (true); |
1115 |
|
} |
1116 |
|
|
1117 |
|
void _Destroy(pointer _First, pointer _Last) |
1118 |
|
{ // destroy [_First, _Last) using allocator |
1119 |
|
_Destroy_range(_First, _Last, this->_Alval); |
1120 |
|
} |
1121 |
|
|
1122 |
|
void _Tidy() |
1123 |
|
{ // free all storage |
1124 |
|
if (_Myfirst != 0) |
1125 |
|
{ // something to free, destroy and deallocate it |
1126 |
|
|
1127 |
|
#if _HAS_ITERATOR_DEBUGGING |
1128 |
|
this->_Orphan_all(); |
1129 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1130 |
|
|
1131 |
|
_Destroy(_Myfirst, _Mylast); |
1132 |
|
this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst); |
1133 |
|
} |
1134 |
|
_Myfirst = 0, _Mylast = 0, _Myend = 0; |
1135 |
|
} |
1136 |
|
|
1137 |
|
template<class _Iter> |
1138 |
|
pointer _Ucopy(_Iter _First, _Iter _Last, pointer _Ptr) |
1139 |
|
{ // copy initializing [_First, _Last), using allocator |
1140 |
|
return (_STDEXT unchecked_uninitialized_copy(_First, _Last, |
1141 |
|
_Ptr, this->_Alval)); |
1142 |
|
} |
1143 |
|
|
1144 |
|
template<class _Iter> |
1145 |
|
pointer _Umove(_Iter _First, _Iter _Last, pointer _Ptr) |
1146 |
|
{ // move initializing [_First, _Last), using allocator |
1147 |
|
return (_STDEXT _Unchecked_uninitialized_move(_First, _Last, |
1148 |
|
_Ptr, this->_Alval)); |
1149 |
|
} |
1150 |
|
|
1151 |
|
void _Insert_n(const_iterator _Where, |
1152 |
|
size_type _Count, const _Ty& _Val) |
1153 |
|
{ // insert _Count * _Val at _Where |
1154 |
|
|
1155 |
|
#if _HAS_ITERATOR_DEBUGGING |
1156 |
|
if (_Where._Mycont != this |
1157 |
|
|| _Where._Myptr < _Myfirst || _Mylast < _Where._Myptr) |
1158 |
|
_DEBUG_ERROR("vector insert iterator outside range"); |
1159 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1160 |
|
|
1161 |
|
size_type _Capacity = capacity(); |
1162 |
|
|
1163 |
|
if (_Count == 0) |
1164 |
|
; |
1165 |
|
else if (max_size() - size() < _Count) |
1166 |
|
_Xlen(); // result too long |
1167 |
|
else if (_Capacity < size() + _Count) |
1168 |
|
{ // not enough room, reallocate |
1169 |
|
_Capacity = max_size() - _Capacity / 2 < _Capacity |
1170 |
|
? 0 : _Capacity + _Capacity / 2; // try to grow by 50% |
1171 |
|
if (_Capacity < size() + _Count) |
1172 |
|
_Capacity = size() + _Count; |
1173 |
|
pointer _Newvec = this->_Alval.allocate(_Capacity); |
1174 |
|
size_type _Whereoff = _VEC_ITER_BASE(_Where) - _Myfirst; |
1175 |
|
int _Ncopied = 0; |
1176 |
|
|
1177 |
|
_TRY_BEGIN |
1178 |
|
_Ufill(_Newvec + _Whereoff, _Count, _Val); // add new stuff |
1179 |
|
++_Ncopied; |
1180 |
|
_Umove(this->_Myfirst, _VEC_ITER_BASE(_Where), |
1181 |
|
_Newvec); // move prefix |
1182 |
|
++_Ncopied; |
1183 |
|
_Umove(_VEC_ITER_BASE(_Where), this->_Mylast, |
1184 |
|
_Newvec + (_Whereoff + _Count)); // move suffix |
1185 |
|
_CATCH_ALL |
1186 |
|
if (1 < _Ncopied) |
1187 |
|
_Destroy(_Newvec, _Newvec + _Whereoff); |
1188 |
|
if (0 < _Ncopied) |
1189 |
|
_Destroy(_Newvec + _Whereoff, _Newvec + _Whereoff + _Count); |
1190 |
|
this->_Alval.deallocate(_Newvec, _Capacity); |
1191 |
|
_RERAISE; |
1192 |
|
_CATCH_END |
1193 |
|
|
1194 |
|
_Count += size(); |
1195 |
|
if (_Myfirst != 0) |
1196 |
|
{ // destroy and deallocate old array |
1197 |
|
_Destroy(_Myfirst, _Mylast); |
1198 |
|
this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst); |
1199 |
|
} |
1200 |
|
|
1201 |
|
#if _HAS_ITERATOR_DEBUGGING |
1202 |
|
this->_Orphan_all(); |
1203 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1204 |
|
|
1205 |
|
_Myend = _Newvec + _Capacity; |
1206 |
|
_Mylast = _Newvec + _Count; |
1207 |
|
_Myfirst = _Newvec; |
1208 |
|
} |
1209 |
|
else if ((size_type)(_Mylast - _VEC_ITER_BASE(_Where)) < _Count) |
1210 |
|
{ // new stuff spills off end |
1211 |
|
_Ty _Tmp = _Val; // in case _Val is in sequence |
1212 |
|
|
1213 |
|
_Umove(_VEC_ITER_BASE(_Where), _Mylast, |
1214 |
|
_VEC_ITER_BASE(_Where) + _Count); // copy suffix |
1215 |
|
|
1216 |
|
_TRY_BEGIN |
1217 |
|
_Ufill(_Mylast, _Count - (_Mylast - _VEC_ITER_BASE(_Where)), |
1218 |
|
_Tmp); // insert new stuff off end |
1219 |
|
_CATCH_ALL |
1220 |
|
_Destroy(_VEC_ITER_BASE(_Where) + _Count, _Mylast + _Count); |
1221 |
|
_RERAISE; |
1222 |
|
_CATCH_END |
1223 |
|
|
1224 |
|
_Mylast += _Count; |
1225 |
|
|
1226 |
|
#if _HAS_ITERATOR_DEBUGGING |
1227 |
|
_Orphan_range(_Where._Myptr, _Mylast); |
1228 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1229 |
|
|
1230 |
|
std::fill(_VEC_ITER_BASE(_Where), _Mylast - _Count, |
1231 |
|
_Tmp); // insert up to old end |
1232 |
|
} |
1233 |
|
else |
1234 |
|
{ // new stuff can all be assigned |
1235 |
|
_Ty _Tmp = _Val; // in case _Val is in sequence |
1236 |
|
|
1237 |
|
pointer _Oldend = _Mylast; |
1238 |
|
_Mylast = _Umove(_Oldend - _Count, _Oldend, |
1239 |
|
_Mylast); // copy suffix |
1240 |
|
|
1241 |
|
#if _HAS_ITERATOR_DEBUGGING |
1242 |
|
_Orphan_range(_Where._Myptr, _Mylast); |
1243 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1244 |
|
|
1245 |
|
_STDEXT _Unchecked_move_backward(_VEC_ITER_BASE(_Where), _Oldend - _Count, |
1246 |
|
_Oldend); // copy hole |
1247 |
|
std::fill(_VEC_ITER_BASE(_Where), _VEC_ITER_BASE(_Where) + _Count, |
1248 |
|
_Tmp); // insert into hole |
1249 |
|
} |
1250 |
|
} |
1251 |
|
|
1252 |
|
pointer _Ufill(pointer _Ptr, size_type _Count, const _Ty &_Val) |
1253 |
|
{ // copy initializing _Count * _Val, using allocator |
1254 |
|
_STDEXT unchecked_uninitialized_fill_n(_Ptr, _Count, _Val, this->_Alval); |
1255 |
|
return (_Ptr + _Count); |
1256 |
|
} |
1257 |
|
|
1258 |
|
static void _Xlen() |
1259 |
|
{ // report a length_error |
1260 |
|
_THROW(length_error, "vector<T> too long"); |
1261 |
|
} |
1262 |
|
|
1263 |
|
static void _Xran() |
1264 |
|
{ // report an out_of_range error |
1265 |
|
_THROW(out_of_range, "invalid vector<T> subscript"); |
1266 |
|
} |
1267 |
|
|
1268 |
|
static void _Xinvarg() |
1269 |
|
{ // report an invalid_argument error |
1270 |
|
_THROW(invalid_argument, "invalid vector<T> argument"); |
1271 |
|
} |
1272 |
|
|
1273 |
|
#if _HAS_ITERATOR_DEBUGGING |
1274 |
|
void _Orphan_range(pointer _First, pointer _Last) const |
1275 |
|
{ // orphan iterators within specified (inclusive) range |
1276 |
|
_Lockit _Lock(_LOCK_DEBUG); |
1277 |
|
const_iterator **_Pnext = (const_iterator **)&this->_Myfirstiter; |
1278 |
|
while (*_Pnext != 0) |
1279 |
|
if ((*_Pnext)->_Myptr < _First || _Last < (*_Pnext)->_Myptr) |
1280 |
|
_Pnext = (const_iterator **)&(*_Pnext)->_Mynextiter; |
1281 |
|
else |
1282 |
|
{ // orphan the iterator |
1283 |
|
(*_Pnext)->_Mycont = 0; |
1284 |
|
*_Pnext = (const_iterator *)(*_Pnext)->_Mynextiter; |
1285 |
|
} |
1286 |
|
} |
1287 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1288 |
|
|
1289 |
|
pointer _Myfirst; // pointer to beginning of array |
1290 |
|
pointer _Mylast; // pointer to current end of sequence |
1291 |
|
pointer _Myend; // pointer to end of array |
1292 |
|
}; |
1293 |
|
|
1294 |
|
// vector implements a performant swap |
1295 |
|
template <class _Ty, class _Ax> |
1296 |
|
class _Move_operation_category<vector<_Ty, _Ax> > |
1297 |
|
{ |
1298 |
|
public: |
1299 |
|
typedef _Swap_move_tag _Move_cat; |
1300 |
|
}; |
1301 |
|
|
1302 |
|
// vector TEMPLATE FUNCTIONS |
1303 |
|
template<class _Ty, |
1304 |
|
class _Alloc> inline |
1305 |
|
bool operator==(const vector<_Ty, _Alloc>& _Left, |
1306 |
|
const vector<_Ty, _Alloc>& _Right) |
1307 |
|
{ // test for vector equality |
1308 |
|
return (_Left.size() == _Right.size() |
1309 |
|
&& equal(_Left.begin(), _Left.end(), _Right.begin())); |
1310 |
|
} |
1311 |
|
|
1312 |
|
template<class _Ty, |
1313 |
|
class _Alloc> inline |
1314 |
|
bool operator!=(const vector<_Ty, _Alloc>& _Left, |
1315 |
|
const vector<_Ty, _Alloc>& _Right) |
1316 |
|
{ // test for vector inequality |
1317 |
|
return (!(_Left == _Right)); |
1318 |
|
} |
1319 |
|
|
1320 |
|
template<class _Ty, |
1321 |
|
class _Alloc> inline |
1322 |
|
bool operator<(const vector<_Ty, _Alloc>& _Left, |
1323 |
|
const vector<_Ty, _Alloc>& _Right) |
1324 |
|
{ // test if _Left < _Right for vectors |
1325 |
|
return (lexicographical_compare(_Left.begin(), _Left.end(), |
1326 |
|
_Right.begin(), _Right.end())); |
1327 |
|
} |
1328 |
|
|
1329 |
|
template<class _Ty, |
1330 |
|
class _Alloc> inline |
1331 |
|
bool operator>(const vector<_Ty, _Alloc>& _Left, |
1332 |
|
const vector<_Ty, _Alloc>& _Right) |
1333 |
|
{ // test if _Left > _Right for vectors |
1334 |
|
return (_Right < _Left); |
1335 |
|
} |
1336 |
|
|
1337 |
|
template<class _Ty, |
1338 |
|
class _Alloc> inline |
1339 |
|
bool operator<=(const vector<_Ty, _Alloc>& _Left, |
1340 |
|
const vector<_Ty, _Alloc>& _Right) |
1341 |
|
{ // test if _Left <= _Right for vectors |
1342 |
|
return (!(_Right < _Left)); |
1343 |
|
} |
1344 |
|
|
1345 |
|
template<class _Ty, |
1346 |
|
class _Alloc> inline |
1347 |
|
bool operator>=(const vector<_Ty, _Alloc>& _Left, |
1348 |
|
const vector<_Ty, _Alloc>& _Right) |
1349 |
|
{ // test if _Left >= _Right for vectors |
1350 |
|
return (!(_Left < _Right)); |
1351 |
|
} |
1352 |
|
|
1353 |
|
template<class _Ty, |
1354 |
|
class _Alloc> inline |
1355 |
|
void swap(vector<_Ty, _Alloc>& _Left, vector<_Ty, _Alloc>& _Right) |
1356 |
|
{ // swap _Left and _Right vectors |
1357 |
|
_Left.swap(_Right); |
1358 |
|
} |
1359 |
|
|
1360 |
|
// |
1361 |
|
// TEMPLATE CLASS vector<bool, Alloc> AND FRIENDS |
1362 |
|
// |
1363 |
|
typedef unsigned _Vbase; // word type for vector<bool> representation |
1364 |
|
const int _VBITS = 8 * sizeof (_Vbase); // at least CHAR_BITS bits per word |
1365 |
|
|
1366 |
|
// CLASS _Vb_iter_base |
1367 |
|
template<class _Sizet, |
1368 |
|
class _Difft, |
1369 |
|
class _MycontTy> |
1370 |
|
class _Vb_iter_base |
1371 |
|
: public _Ranit<_Bool, _Difft, bool *, bool> |
1372 |
|
{ // store information common to reference and iterators |
1373 |
|
public: |
1374 |
|
#if _SECURE_SCL |
1375 |
|
typedef _Range_checked_iterator_tag _Checked_iterator_category; |
1376 |
|
#endif |
1377 |
|
|
1378 |
|
_Vb_iter_base() |
1379 |
|
: _Myptr(0), _Myoff(0) |
1380 |
|
{ // construct with null pointer |
1381 |
|
} |
1382 |
|
|
1383 |
|
#if _HAS_ITERATOR_DEBUGGING |
1384 |
|
_Vb_iter_base(_Vbase *_Ptr, _Sizet _Off, |
1385 |
|
const _Container_base *_Mypvbool) |
1386 |
|
: _Myptr(_Ptr), _Myoff(_Off) |
1387 |
|
{ // construct with offset and pointer |
1388 |
|
_SCL_SECURE_VALIDATE(_Mypvbool != NULL); |
1389 |
|
this->_Adopt(_Mypvbool); |
1390 |
|
} |
1391 |
|
|
1392 |
|
#elif _SECURE_SCL |
1393 |
|
_Vb_iter_base(_Vbase *_Ptr, _Sizet _Off, |
1394 |
|
const _Container_base *_Mypvbool) |
1395 |
|
: _Myptr(_Ptr), _Myoff(_Off) |
1396 |
|
{ // construct with offset and pointer |
1397 |
|
_SCL_SECURE_VALIDATE(_Mypvbool != NULL); |
1398 |
|
this->_Set_container(_Mypvbool); |
1399 |
|
} |
1400 |
|
#else |
1401 |
|
_Vb_iter_base(_Vbase *_Ptr, _Sizet _Off) |
1402 |
|
: _Myptr(_Ptr), _Myoff(_Off) |
1403 |
|
{ // construct with offset and pointer |
1404 |
|
} |
1405 |
|
#endif |
1406 |
|
|
1407 |
|
_Vbase *_Myptr; |
1408 |
|
_Sizet _Myoff; |
1409 |
|
|
1410 |
|
static void _Xlen() |
1411 |
|
{ // report a length_error |
1412 |
|
_THROW(length_error, "vector<bool> too long"); |
1413 |
|
} |
1414 |
|
|
1415 |
|
static void _Xran() |
1416 |
|
{ // report an out_of_range error |
1417 |
|
_THROW(out_of_range, "invalid vector<bool> subscript"); |
1418 |
|
} |
1419 |
|
|
1420 |
|
static void _Xinvarg() |
1421 |
|
{ // report an invalid_argument error |
1422 |
|
_THROW(invalid_argument, "invalid vector<bool> argument"); |
1423 |
|
} |
1424 |
|
|
1425 |
|
#if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL |
1426 |
|
_Vbase * _My_cont_begin() const |
1427 |
|
{ |
1428 |
|
return (_VEC_ITER_BASE(((_MycontTy *)this-> |
1429 |
|
_Getmycont())->_Myvec.begin())); |
1430 |
|
} |
1431 |
|
|
1432 |
|
_Sizet _My_actual_offset() const |
1433 |
|
{ |
1434 |
|
_Sizet _Off = this->_Myoff; |
1435 |
|
_Off += _VBITS * (this->_Myptr - _My_cont_begin()); |
1436 |
|
return (_Off); |
1437 |
|
} |
1438 |
|
#endif |
1439 |
|
}; |
1440 |
|
|
1441 |
|
// CLASS _Vb_reference |
1442 |
|
template<class _Sizet, |
1443 |
|
class _Difft, |
1444 |
|
class _MycontTy> |
1445 |
|
class _Vb_reference |
1446 |
|
: public _Vb_iter_base<_Sizet, _Difft, _MycontTy> |
1447 |
|
{ // reference to a bit within a base word |
1448 |
|
public: |
1449 |
|
typedef _Vb_iter_base<_Sizet, _Difft, _MycontTy> _Mybase; |
1450 |
|
typedef _Vb_reference<_Sizet, _Difft, _MycontTy> _Mytype; |
1451 |
|
|
1452 |
|
_Vb_reference() |
1453 |
|
{ // construct with null pointer |
1454 |
|
} |
1455 |
|
|
1456 |
|
#if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL |
1457 |
|
_Vb_reference(const _Mybase& _Right) |
1458 |
|
: _Mybase(_Right._Myptr, _Right._Myoff, _Right._Getmycont()) |
1459 |
|
{ // construct with base |
1460 |
|
} |
1461 |
|
|
1462 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
1463 |
|
_Vb_reference(const _Mybase& _Right) |
1464 |
|
: _Mybase(_Right._Myptr, _Right._Myoff) |
1465 |
|
{ // construct with base |
1466 |
|
} |
1467 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1468 |
|
|
1469 |
|
_Mytype& operator=(const _Mytype& _Right) |
1470 |
|
{ // assign _Vb_reference _Right to bit |
1471 |
|
return (*this = bool(_Right)); |
1472 |
|
} |
1473 |
|
|
1474 |
|
_Mytype& operator=(bool _Val) |
1475 |
|
{ // assign _Val to bit |
1476 |
|
if (_Val) |
1477 |
|
*_Getptr() |= _Mask(); |
1478 |
|
else |
1479 |
|
*_Getptr() &= ~_Mask(); |
1480 |
|
return (*this); |
1481 |
|
} |
1482 |
|
|
1483 |
|
void flip() |
1484 |
|
{ // toggle the bit |
1485 |
|
*_Getptr() ^= _Mask(); |
1486 |
|
} |
1487 |
|
|
1488 |
|
bool operator~() const |
1489 |
|
{ // test if bit is reset |
1490 |
|
return (!bool(*this)); |
1491 |
|
} |
1492 |
|
|
1493 |
|
operator bool() const |
1494 |
|
{ // test if bit is set |
1495 |
|
return ((*_Getptr() & _Mask()) != 0); |
1496 |
|
} |
1497 |
|
|
1498 |
|
_Vbase *_Getptr() const |
1499 |
|
{ // get pointer to base word |
1500 |
|
|
1501 |
|
#if _HAS_ITERATOR_DEBUGGING |
1502 |
|
if (this->_Mycont == 0 || this->_Myptr == 0) |
1503 |
|
{ |
1504 |
|
_DEBUG_ERROR("vector<bool> iterator not dereferencable"); |
1505 |
|
_SCL_SECURE_OUT_OF_RANGE; |
1506 |
|
} |
1507 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
1508 |
|
_SCL_SECURE_VALIDATE(this->_Has_container() && this->_Myptr != NULL); |
1509 |
|
_SCL_SECURE_VALIDATE_RANGE(this->_My_actual_offset() < ((_MycontTy *)this->_Getmycont())->_Mysize); |
1510 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1511 |
|
|
1512 |
|
return (this->_Myptr); |
1513 |
|
} |
1514 |
|
|
1515 |
|
protected: |
1516 |
|
_Vbase _Mask() const |
1517 |
|
{ // convert offset to mask |
1518 |
|
return ((_Vbase)(1 << this->_Myoff)); |
1519 |
|
} |
1520 |
|
}; |
1521 |
|
|
1522 |
|
template<class _Sizet, |
1523 |
|
class _Difft, |
1524 |
|
class _MycontTy> |
1525 |
|
void swap(_Vb_reference<_Sizet, _Difft, _MycontTy> _Left, |
1526 |
|
_Vb_reference<_Sizet, _Difft, _MycontTy> _Right) |
1527 |
|
{ // swap _Left and _Right vector<bool> elements |
1528 |
|
bool _Val = _Left; |
1529 |
|
_Left = _Right; |
1530 |
|
_Right = _Val; |
1531 |
|
} |
1532 |
|
|
1533 |
|
// CLASS _Vb_const_iterator |
1534 |
|
template<class _Sizet, |
1535 |
|
class _Difft, |
1536 |
|
class _MycontTy> |
1537 |
|
class _Vb_const_iterator |
1538 |
|
: public _Vb_iter_base<_Sizet, _Difft, _MycontTy> |
1539 |
|
{ // iterator for nonmutable vector<bool> |
1540 |
|
public: |
1541 |
|
typedef _Vb_iter_base<_Sizet, _Difft, _MycontTy> _Mybase; |
1542 |
|
typedef _Vb_const_iterator<_Sizet, _Difft, _MycontTy> _Mytype; |
1543 |
|
|
1544 |
|
typedef _Vb_reference<_Sizet, _Difft, _MycontTy> _Reft; |
1545 |
|
typedef bool const_reference; |
1546 |
|
|
1547 |
|
typedef random_access_iterator_tag iterator_category; |
1548 |
|
typedef _Bool value_type; |
1549 |
|
typedef _Sizet size_type; |
1550 |
|
typedef _Difft difference_type; |
1551 |
|
typedef const_reference *pointer; |
1552 |
|
typedef const_reference reference; |
1553 |
|
|
1554 |
|
_Vb_const_iterator() |
1555 |
|
{ // construct with null reference |
1556 |
|
} |
1557 |
|
|
1558 |
|
#if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL |
1559 |
|
_Vb_const_iterator(const _Vbase *_Ptr, const _Container_base *_Mypvbool) |
1560 |
|
: _Mybase((_Vbase *)_Ptr, 0, (_Container_base *)_Mypvbool) |
1561 |
|
|
1562 |
|
#else |
1563 |
|
_Vb_const_iterator(const _Vbase *_Ptr) |
1564 |
|
: _Mybase((_Vbase *)_Ptr, 0) |
1565 |
|
|
1566 |
|
#endif |
1567 |
|
{ // construct with offset and pointer |
1568 |
|
} |
1569 |
|
|
1570 |
|
const_reference operator*() const |
1571 |
|
{ // return (reference to) designated object |
1572 |
|
return (_Reft(*this)); |
1573 |
|
} |
1574 |
|
|
1575 |
|
_Mytype& operator++() |
1576 |
|
{ // preincrement |
1577 |
|
_Inc(); |
1578 |
|
return (*this); |
1579 |
|
} |
1580 |
|
|
1581 |
|
_Mytype operator++(int) |
1582 |
|
{ // postincrement |
1583 |
|
_Mytype _Tmp = *this; |
1584 |
|
++*this; |
1585 |
|
return (_Tmp); |
1586 |
|
} |
1587 |
|
|
1588 |
|
_Mytype& operator--() |
1589 |
|
{ // predecrement |
1590 |
|
_Dec(); |
1591 |
|
return (*this); |
1592 |
|
} |
1593 |
|
|
1594 |
|
_Mytype operator--(int) |
1595 |
|
{ // postdecrement |
1596 |
|
_Mytype _Tmp = *this; |
1597 |
|
--*this; |
1598 |
|
return (_Tmp); |
1599 |
|
} |
1600 |
|
|
1601 |
|
_Mytype& operator+=(difference_type _Off) |
1602 |
|
{ // increment by integer |
1603 |
|
if (_Off == 0) |
1604 |
|
return (*this); // early out |
1605 |
|
_SCL_SECURE_VALIDATE(this->_Has_container() && this->_Myptr != NULL); |
1606 |
|
if (_Off < 0) |
1607 |
|
{ |
1608 |
|
_SCL_SECURE_VALIDATE_RANGE(this->_My_actual_offset() >= ((size_type)-_Off)); |
1609 |
|
} |
1610 |
|
else |
1611 |
|
{ |
1612 |
|
_SCL_SECURE_VALIDATE_RANGE((this->_My_actual_offset() + _Off) <= ((_MycontTy *)this->_Getmycont())->_Mysize); |
1613 |
|
} |
1614 |
|
if (_Off < 0 && this->_Myoff < 0 - (size_type)_Off) |
1615 |
|
{ /* add negative increment */ |
1616 |
|
this->_Myoff += _Off; |
1617 |
|
this->_Myptr -= 1 + ((size_type)(-1) - this->_Myoff) / _VBITS; |
1618 |
|
this->_Myoff %= _VBITS; |
1619 |
|
} |
1620 |
|
else |
1621 |
|
{ /* add non-negative increment */ |
1622 |
|
this->_Myoff += _Off; |
1623 |
|
this->_Myptr += this->_Myoff / _VBITS; |
1624 |
|
this->_Myoff %= _VBITS; |
1625 |
|
} |
1626 |
|
return (*this); |
1627 |
|
} |
1628 |
|
|
1629 |
|
_Mytype operator+(difference_type _Off) const |
1630 |
|
{ // return this + integer |
1631 |
|
_Mytype _Tmp = *this; |
1632 |
|
return (_Tmp += _Off); |
1633 |
|
} |
1634 |
|
|
1635 |
|
_Mytype& operator-=(difference_type _Off) |
1636 |
|
{ // decrement by integer |
1637 |
|
return (*this += -_Off); |
1638 |
|
} |
1639 |
|
|
1640 |
|
_Mytype operator-(difference_type _Off) const |
1641 |
|
{ // return this - integer |
1642 |
|
_Mytype _Tmp = *this; |
1643 |
|
return (_Tmp -= _Off); |
1644 |
|
} |
1645 |
|
|
1646 |
|
difference_type operator-( |
1647 |
|
const _Mytype& _Right) const |
1648 |
|
{ // return difference of iterators |
1649 |
|
|
1650 |
|
#if _HAS_ITERATOR_DEBUGGING |
1651 |
|
_Compat(_Right); |
1652 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1653 |
|
|
1654 |
|
return (_VBITS * (this->_Myptr - _Right._Myptr) |
1655 |
|
+ (difference_type)this->_Myoff |
1656 |
|
- (difference_type)_Right._Myoff); |
1657 |
|
} |
1658 |
|
|
1659 |
|
const_reference operator[](difference_type _Off) const |
1660 |
|
{ // subscript |
1661 |
|
return (*(*this + _Off)); |
1662 |
|
} |
1663 |
|
|
1664 |
|
bool operator==(const _Mytype& _Right) const |
1665 |
|
{ // test for iterator equality |
1666 |
|
|
1667 |
|
#if _HAS_ITERATOR_DEBUGGING |
1668 |
|
_Compat(_Right); |
1669 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1670 |
|
|
1671 |
|
return (this->_Myptr == _Right._Myptr |
1672 |
|
&& this->_Myoff == _Right._Myoff); |
1673 |
|
} |
1674 |
|
|
1675 |
|
bool operator!=(const _Mytype& _Right) const |
1676 |
|
{ // test for iterator inequality |
1677 |
|
return (!(*this == _Right)); |
1678 |
|
} |
1679 |
|
|
1680 |
|
bool operator<(const _Mytype& _Right) const |
1681 |
|
{ // test if this < _Right |
1682 |
|
|
1683 |
|
#if _HAS_ITERATOR_DEBUGGING |
1684 |
|
_Compat(_Right); |
1685 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1686 |
|
|
1687 |
|
return (this->_Myptr < _Right._Myptr |
1688 |
|
|| this->_Myptr == _Right._Myptr |
1689 |
|
&& this->_Myoff < _Right._Myoff); |
1690 |
|
} |
1691 |
|
|
1692 |
|
bool operator>(const _Mytype& _Right) const |
1693 |
|
{ // test if this > _Right |
1694 |
|
return (_Right < *this); |
1695 |
|
} |
1696 |
|
|
1697 |
|
bool operator<=(const _Mytype& _Right) const |
1698 |
|
{ // test if this <= _Right |
1699 |
|
return (!(_Right < *this)); |
1700 |
|
} |
1701 |
|
|
1702 |
|
bool operator>=(const _Mytype& _Right) const |
1703 |
|
{ // test if this >= _Right |
1704 |
|
return (!(*this < _Right)); |
1705 |
|
} |
1706 |
|
|
1707 |
|
protected: |
1708 |
|
|
1709 |
|
#if _HAS_ITERATOR_DEBUGGING |
1710 |
|
void _Compat(const _Mytype& _Right) const |
1711 |
|
{ // test for compatible iterator pair |
1712 |
|
if (this->_Mycont == 0 || this->_Mycont != _Right._Mycont) |
1713 |
|
_DEBUG_ERROR("vector<bool> iterators incompatible"); |
1714 |
|
} |
1715 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1716 |
|
|
1717 |
|
void _Dec() |
1718 |
|
{ // decrement bit position |
1719 |
|
if (this->_Myoff != 0) |
1720 |
|
{ |
1721 |
|
--this->_Myoff; |
1722 |
|
} |
1723 |
|
else |
1724 |
|
{ |
1725 |
|
_SCL_SECURE_VALIDATE(this->_Has_container() && this->_Myptr != NULL); |
1726 |
|
_SCL_SECURE_VALIDATE_RANGE(this->_Myptr > this->_My_cont_begin()); |
1727 |
|
--this->_Myptr; |
1728 |
|
this->_Myoff = _VBITS - 1; |
1729 |
|
} |
1730 |
|
} |
1731 |
|
|
1732 |
|
void _Inc() |
1733 |
|
{ // increment bit position |
1734 |
|
_SCL_SECURE_VALIDATE(this->_Has_container() && this->_Myptr != NULL); |
1735 |
|
_SCL_SECURE_VALIDATE_RANGE((this->_My_actual_offset() + 1) <= ((_MycontTy *)this->_Getmycont())->_Mysize); |
1736 |
|
if (this->_Myoff < _VBITS - 1) |
1737 |
|
++this->_Myoff; |
1738 |
|
else |
1739 |
|
this->_Myoff = 0, ++this->_Myptr; |
1740 |
|
} |
1741 |
|
}; |
1742 |
|
|
1743 |
|
template<class _Sizet, |
1744 |
|
class _Difft, |
1745 |
|
class _MycontTy> |
1746 |
|
_Vb_const_iterator<_Sizet, _Difft, _MycontTy> operator+(_Difft _Off, |
1747 |
|
_Vb_const_iterator<_Sizet, _Difft, _MycontTy> _Right) |
1748 |
|
{ // return _Right + integer |
1749 |
|
return (_Right += _Off); |
1750 |
|
} |
1751 |
|
|
1752 |
|
// CLASS _Vb_iterator |
1753 |
|
template<class _Sizet, |
1754 |
|
class _Difft, |
1755 |
|
class _MycontTy> |
1756 |
|
class _Vb_iterator |
1757 |
|
: public _Vb_const_iterator<_Sizet, _Difft, _MycontTy> |
1758 |
|
{ // iterator for mutable vector<bool> |
1759 |
|
public: |
1760 |
|
typedef _Vb_const_iterator<_Sizet, _Difft, _MycontTy> _Mybase; |
1761 |
|
typedef _Vb_iterator<_Sizet, _Difft, _MycontTy> _Mytype; |
1762 |
|
|
1763 |
|
typedef _Vb_reference<_Sizet, _Difft, _MycontTy> _Reft; |
1764 |
|
typedef bool const_reference; |
1765 |
|
|
1766 |
|
typedef random_access_iterator_tag iterator_category; |
1767 |
|
typedef _Bool value_type; |
1768 |
|
typedef _Sizet size_type; |
1769 |
|
typedef _Difft difference_type; |
1770 |
|
typedef _Reft *pointer; |
1771 |
|
typedef _Reft reference; |
1772 |
|
|
1773 |
|
_Vb_iterator() |
1774 |
|
{ // construct with null reference |
1775 |
|
} |
1776 |
|
|
1777 |
|
#if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL |
1778 |
|
_Vb_iterator(_Vbase *_Ptr, _Container_base *_Mypvbool) |
1779 |
|
: _Mybase(_Ptr, _Mypvbool) |
1780 |
|
|
1781 |
|
#else |
1782 |
|
_Vb_iterator( _Vbase *_Ptr) |
1783 |
|
: _Mybase(_Ptr) |
1784 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
1785 |
|
|
1786 |
|
{ // construct with offset and pointer |
1787 |
|
} |
1788 |
|
|
1789 |
|
reference operator*() const |
1790 |
|
{ // return (reference to) designated object |
1791 |
|
return (_Reft(*this)); |
1792 |
|
} |
1793 |
|
|
1794 |
|
_Mytype& operator++() |
1795 |
|
{ // preincrement |
1796 |
|
++*(_Mybase *)this; |
1797 |
|
return (*this); |
1798 |
|
} |
1799 |
|
|
1800 |
|
_Mytype operator++(int) |
1801 |
|
{ // postincrement |
1802 |
|
_Mytype _Tmp = *this; |
1803 |
|
++*this; |
1804 |
|
return (_Tmp); |
1805 |
|
} |
1806 |
|
|
1807 |
|
_Mytype& operator--() |
1808 |
|
{ // predecrement |
1809 |
|
--*(_Mybase *)this; |
1810 |
|
return (*this); |
1811 |
|
} |
1812 |
|
|
1813 |
|
_Mytype operator--(int) |
1814 |
|
{ // postdecrement |
1815 |
|
_Mytype _Tmp = *this; |
1816 |
|
--*this; |
1817 |
|
return (_Tmp); |
1818 |
|
} |
1819 |
|
|
1820 |
|
_Mytype& operator+=(difference_type _Off) |
1821 |
|
{ // increment by integer |
1822 |
|
*(_Mybase *)this += _Off; |
1823 |
|
return (*this); |
1824 |
|
} |
1825 |
|
|
1826 |
|
_Mytype operator+(difference_type _Off) const |
1827 |
|
{ // return this + integer |
1828 |
|
_Mytype _Tmp = *this; |
1829 |
|
return (_Tmp += _Off); |
1830 |
|
} |
1831 |
|
|
1832 |
|
_Mytype& operator-=(difference_type _Off) |
1833 |
|
{ // decrement by integer |
1834 |
|
return (*this += -_Off); |
1835 |
|
} |
1836 |
|
|
1837 |
|
_Mytype operator-(difference_type _Off) const |
1838 |
|
{ // return this - integer |
1839 |
|
_Mytype _Tmp = *this; |
1840 |
|
return (_Tmp -= _Off); |
1841 |
|
} |
1842 |
|
|
1843 |
|
difference_type operator-(const _Mybase& _Right) const |
1844 |
|
{ // return difference of iterators |
1845 |
|
return (*(_Mybase *)this - _Right); |
1846 |
|
} |
1847 |
|
|
1848 |
|
reference operator[](difference_type _Off) const |
1849 |
|
{ // subscript |
1850 |
|
return (*(*this + _Off)); |
1851 |
|
} |
1852 |
|
}; |
1853 |
|
|
1854 |
|
template<class _Sizet, |
1855 |
|
class _Difft, |
1856 |
|
class _MycontTy> |
1857 |
|
_Vb_iterator<_Sizet, _Difft, _MycontTy> operator+(_Difft _Off, |
1858 |
|
_Vb_iterator<_Sizet, _Difft, _MycontTy> _Right) |
1859 |
|
{ // return _Right + integer |
1860 |
|
return (_Right += _Off); |
1861 |
|
} |
1862 |
|
|
1863 |
|
// CLASS vector_bool |
1864 |
|
template<class _Alloc> |
1865 |
|
class vector<_Bool, _Alloc> |
1866 |
|
: public _CONTAINER_BASE_AUX_ALLOC<_Alloc> |
1867 |
|
{ // varying size array of bits |
1868 |
|
public: |
1869 |
|
typedef typename _Alloc::size_type size_type; |
1870 |
|
typedef typename _Alloc::difference_type _Dift; |
1871 |
|
typedef std::vector<_Vbase, |
1872 |
|
typename _Alloc::template rebind<_Vbase>::other> |
1873 |
|
_Vbtype; |
1874 |
|
typedef std::vector<_Bool, _Alloc> _Myt; |
1875 |
|
|
1876 |
|
|
1877 |
|
typedef _Dift difference_type; |
1878 |
|
typedef _Bool _Ty; |
1879 |
|
typedef _Alloc allocator_type; |
1880 |
|
|
1881 |
|
typedef _Vb_reference<size_type, _Dift, _Myt> reference; |
1882 |
|
typedef bool const_reference; |
1883 |
|
typedef bool value_type; |
1884 |
|
|
1885 |
|
typedef reference _Reft; |
1886 |
|
typedef _Vb_const_iterator<size_type, difference_type, _Myt> const_iterator; |
1887 |
|
typedef _Vb_iterator<size_type, difference_type, _Myt> iterator; |
1888 |
|
|
1889 |
|
friend class _Vb_iter_base<size_type, difference_type, _Myt>; |
1890 |
|
friend class _Vb_reference<size_type, difference_type, _Myt>; |
1891 |
|
friend class _Vb_const_iterator<size_type, difference_type, _Myt>; |
1892 |
|
friend class _Vb_iterator<size_type, difference_type, _Myt>; |
1893 |
|
|
1894 |
|
typedef iterator pointer; |
1895 |
|
typedef const_iterator const_pointer; |
1896 |
|
typedef std::reverse_iterator<iterator> reverse_iterator; |
1897 |
|
typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
1898 |
|
|
1899 |
|
static const int _VBITS = std::_VBITS; |
1900 |
|
|
1901 |
|
vector() |
1902 |
|
: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Alloc()), _Mysize(0), _Myvec() |
1903 |
|
{ // construct empty vector |
1904 |
|
} |
1905 |
|
|
1906 |
|
vector(const _Myt& _Right) |
1907 |
|
: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Right.get_allocator()), _Mysize(_Right._Mysize), _Myvec(_Right._Myvec) |
1908 |
|
{ // copy construct vector; an implicitly defined copy constructor would not create an aux object. |
1909 |
|
} |
1910 |
|
|
1911 |
|
explicit vector(const _Alloc& _Al) |
1912 |
|
: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Mysize(0), _Myvec(_Al) |
1913 |
|
{ // construct empty vector, with allocator |
1914 |
|
} |
1915 |
|
|
1916 |
|
explicit vector(size_type _Count, bool _Val = false) |
1917 |
|
: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Alloc()), _Mysize(0), _Myvec(_Nw(_Count), (_Vbase)(_Val ? -1 : 0)) |
1918 |
|
{ // construct from _Count * _Val |
1919 |
|
_Trim(_Count); |
1920 |
|
} |
1921 |
|
|
1922 |
|
vector(size_type _Count, bool _Val, const _Alloc& _Al) |
1923 |
|
: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Mysize(0), _Myvec(_Nw(_Count), (_Vbase)(_Val ? -1 : 0), _Al) |
1924 |
|
{ // construct from _Count * _Val, with allocator |
1925 |
|
_Trim(_Count); |
1926 |
|
} |
1927 |
|
|
1928 |
|
template<class _Iter> |
1929 |
|
vector(_Iter _First, _Iter _Last) |
1930 |
|
: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Alloc()), _Mysize(0), _Myvec() |
1931 |
|
{ // construct from [_First, _Last) |
1932 |
|
_BConstruct(_First, _Last, _Iter_cat(_First)); |
1933 |
|
} |
1934 |
|
|
1935 |
|
template<class _Iter> |
1936 |
|
vector(_Iter _First, _Iter _Last, const _Alloc& _Al) |
1937 |
|
: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Mysize(0), _Myvec(_Al) |
1938 |
|
{ // construct from [_First, _Last), with allocator |
1939 |
|
_BConstruct(_First, _Last, _Iter_cat(_First)); |
1940 |
|
} |
1941 |
|
|
1942 |
|
template<class _Iter> |
1943 |
|
void _BConstruct(_Iter _Count, _Iter _Val, _Int_iterator_tag) |
1944 |
|
{ // initialize from _Count * _Val |
1945 |
|
size_type _Num = (size_type)_Count; |
1946 |
|
_Myvec.assign(_Num, (_Ty)_Val ? -1 : 0); |
1947 |
|
_Trim(_Num); |
1948 |
|
} |
1949 |
|
|
1950 |
|
template<class _Iter> |
1951 |
|
void _BConstruct(_Iter _First, _Iter _Last, input_iterator_tag) |
1952 |
|
{ // initialize from [_First, _Last), input iterators |
1953 |
|
insert(begin(), _First, _Last); |
1954 |
|
} |
1955 |
|
|
1956 |
|
~vector() |
1957 |
|
{ // destroy the object |
1958 |
|
_Mysize = 0; |
1959 |
|
} |
1960 |
|
|
1961 |
|
void reserve(size_type _Count) |
1962 |
|
{ // determine new minimum length of allocated storage |
1963 |
|
_Myvec.reserve(_Nw(_Count)); |
1964 |
|
} |
1965 |
|
|
1966 |
|
size_type capacity() const |
1967 |
|
{ // return current length of allocated storage |
1968 |
|
return (_Myvec.capacity() * _VBITS); |
1969 |
|
} |
1970 |
|
|
1971 |
|
#if _HAS_ITERATOR_DEBUGGING || _SECURE_SCL |
1972 |
|
iterator begin() |
1973 |
|
{ // return iterator for beginning of mutable sequence |
1974 |
|
return (iterator(_VEC_ITER_BASE(_Myvec.begin()), this)); |
1975 |
|
} |
1976 |
|
|
1977 |
|
const_iterator begin() const |
1978 |
|
{ // return iterator for beginning of nonmutable sequence |
1979 |
|
return (const_iterator(_VEC_ITER_BASE(_Myvec.begin()), this)); |
1980 |
|
} |
1981 |
|
|
1982 |
|
#else |
1983 |
|
iterator begin() |
1984 |
|
{ // return iterator for beginning of mutable sequence |
1985 |
|
return (iterator(_VEC_ITER_BASE(_Myvec.begin()))); |
1986 |
|
} |
1987 |
|
|
1988 |
|
const_iterator begin() const |
1989 |
|
{ // return iterator for beginning of nonmutable sequence |
1990 |
|
return (const_iterator(_VEC_ITER_BASE(_Myvec.begin()))); |
1991 |
|
} |
1992 |
|
#endif |
1993 |
|
|
1994 |
|
iterator end() |
1995 |
|
{ // return iterator for end of mutable sequence |
1996 |
|
iterator _Tmp = begin(); |
1997 |
|
if (0 < _Mysize) |
1998 |
|
_Tmp += _Mysize; |
1999 |
|
return (_Tmp); |
2000 |
|
} |
2001 |
|
|
2002 |
|
const_iterator end() const |
2003 |
|
{ // return iterator for end of nonmutable sequence |
2004 |
|
const_iterator _Tmp = begin(); |
2005 |
|
if (0 < _Mysize) |
2006 |
|
_Tmp += _Mysize; |
2007 |
|
return (_Tmp); |
2008 |
|
} |
2009 |
|
|
2010 |
|
iterator _Make_iter(const_iterator _Where) |
2011 |
|
{ // make iterator from const_iterator |
2012 |
|
iterator _Tmp = begin(); |
2013 |
|
if (0 < _Mysize) |
2014 |
|
_Tmp += _Where - begin(); |
2015 |
|
return (_Tmp); |
2016 |
|
} |
2017 |
|
|
2018 |
|
reverse_iterator rbegin() |
2019 |
|
{ // return iterator for beginning of reversed mutable sequence |
2020 |
|
return (reverse_iterator(end())); |
2021 |
|
} |
2022 |
|
|
2023 |
|
const_reverse_iterator rbegin() const |
2024 |
|
{ // return iterator for beginning of reversed nonmutable sequence |
2025 |
|
return (const_reverse_iterator(end())); |
2026 |
|
} |
2027 |
|
|
2028 |
|
reverse_iterator rend() |
2029 |
|
{ // return iterator for end of reversed mutable sequence |
2030 |
|
return (reverse_iterator(begin())); |
2031 |
|
} |
2032 |
|
|
2033 |
|
const_reverse_iterator rend() const |
2034 |
|
{ // return iterator for end of reversed nonmutable sequence |
2035 |
|
return (const_reverse_iterator(begin())); |
2036 |
|
} |
2037 |
|
|
2038 |
|
void resize(size_type _Newsize, bool _Val = false) |
2039 |
|
{ // determine new length, padding with _Val elements as needed |
2040 |
|
if (size() < _Newsize) |
2041 |
|
_Insert_n(end(), _Newsize - size(), _Val); |
2042 |
|
else if (_Newsize < size()) |
2043 |
|
erase(begin() + _Newsize, end()); |
2044 |
|
} |
2045 |
|
|
2046 |
|
size_type size() const |
2047 |
|
{ // return length of sequence |
2048 |
|
return (_Mysize); |
2049 |
|
} |
2050 |
|
|
2051 |
|
size_type max_size() const |
2052 |
|
{ // return maximum possible length of sequence |
2053 |
|
const size_type _Maxsize = _Myvec.max_size(); |
2054 |
|
return (_Maxsize < (size_type)(-1) / _VBITS |
2055 |
|
? _Maxsize * _VBITS : (size_type)(-1)); |
2056 |
|
} |
2057 |
|
|
2058 |
|
bool empty() const |
2059 |
|
{ // test if sequence is empty |
2060 |
|
return (size() == 0); |
2061 |
|
} |
2062 |
|
|
2063 |
|
_Alloc get_allocator() const |
2064 |
|
{ // return allocator object for values |
2065 |
|
// Work around a BE problem. |
2066 |
|
_Alloc _Alret = _Myvec.get_allocator(); |
2067 |
|
return (_Alret); |
2068 |
|
} |
2069 |
|
|
2070 |
|
const_reference at(size_type _Off) const |
2071 |
|
{ // subscript nonmutable sequence with checking |
2072 |
|
if (size() <= _Off) |
2073 |
|
_Xran(); |
2074 |
|
return (*(begin() + _Off)); |
2075 |
|
} |
2076 |
|
|
2077 |
|
reference at(size_type _Off) |
2078 |
|
{ // subscript mutable sequence with checking |
2079 |
|
if (size() <= _Off) |
2080 |
|
_Xran(); |
2081 |
|
return (*(begin() + _Off)); |
2082 |
|
} |
2083 |
|
|
2084 |
|
const_reference operator[](size_type _Off) const |
2085 |
|
{ // subscript nonmutable sequence |
2086 |
|
return (*(begin() + _Off)); |
2087 |
|
} |
2088 |
|
|
2089 |
|
reference operator[](size_type _Off) |
2090 |
|
{ // subscript mutable sequence |
2091 |
|
return (*(begin() + _Off)); |
2092 |
|
} |
2093 |
|
|
2094 |
|
reference front() |
2095 |
|
{ // return first element of mutable sequence |
2096 |
|
return (*begin()); |
2097 |
|
} |
2098 |
|
|
2099 |
|
const_reference front() const |
2100 |
|
{ // return first element of nonmutable sequence |
2101 |
|
return (*begin()); |
2102 |
|
} |
2103 |
|
|
2104 |
|
reference back() |
2105 |
|
{ // return last element of mutable sequence |
2106 |
|
return (*(end() - 1)); |
2107 |
|
} |
2108 |
|
|
2109 |
|
const_reference back() const |
2110 |
|
{ // return last element of nonmutable sequence |
2111 |
|
return (*(end() - 1)); |
2112 |
|
} |
2113 |
|
|
2114 |
|
void push_back(bool _Val) |
2115 |
|
{ // insert element at end |
2116 |
|
insert(end(), _Val); |
2117 |
|
} |
2118 |
|
|
2119 |
|
void pop_back() |
2120 |
|
{ // erase element at end |
2121 |
|
if (!empty()) |
2122 |
|
erase(end() - 1); |
2123 |
|
} |
2124 |
|
|
2125 |
|
template<class _Iter> |
2126 |
|
void assign(_Iter _First, _Iter _Last) |
2127 |
|
{ // assign [_First, _Last) |
2128 |
|
_Assign(_First, _Last, _Iter_cat(_First)); |
2129 |
|
} |
2130 |
|
|
2131 |
|
template<class _Iter> |
2132 |
|
void _Assign(_Iter _Count, _Iter _Val, _Int_iterator_tag) |
2133 |
|
{ // assign _Count * _Val |
2134 |
|
_Assign_n((size_type)_Count, (bool)_Val); |
2135 |
|
} |
2136 |
|
|
2137 |
|
template<class _Iter> |
2138 |
|
void _Assign(_Iter _First, _Iter _Last, input_iterator_tag) |
2139 |
|
{ // assign [_First, _Last), input iterators |
2140 |
|
erase(begin(), end()); |
2141 |
|
insert(begin(), _First, _Last); |
2142 |
|
} |
2143 |
|
|
2144 |
|
void assign(size_type _Count, bool _Val) |
2145 |
|
{ // assign _Count * _Val |
2146 |
|
_Assign_n(_Count, _Val); |
2147 |
|
} |
2148 |
|
|
2149 |
|
iterator insert(const_iterator _Where, bool _Val) |
2150 |
|
{ // insert _Val at _Where |
2151 |
|
size_type _Off = _Where - begin(); |
2152 |
|
_Insert_n(_Where, (size_type)1, _Val); |
2153 |
|
return (begin() + _Off); |
2154 |
|
} |
2155 |
|
|
2156 |
|
void insert(const_iterator _Where, size_type _Count, bool _Val) |
2157 |
|
{ // insert _Count * _Val at _Where |
2158 |
|
_Insert_n(_Where, _Count, _Val); |
2159 |
|
} |
2160 |
|
|
2161 |
|
template<class _Iter> |
2162 |
|
void insert(const_iterator _Where, _Iter _First, _Iter _Last) |
2163 |
|
{ // insert [_First, _Last) at _Where |
2164 |
|
_Insert(_Where, _First, _Last, _Iter_cat(_First)); |
2165 |
|
} |
2166 |
|
|
2167 |
|
template<class _Iter> |
2168 |
|
void _Insert(const_iterator _Where, _Iter _Count, _Iter _Val, |
2169 |
|
_Int_iterator_tag) |
2170 |
|
{ // insert _Count * _Val at _Where |
2171 |
|
_Insert_n(_Where, (size_type)_Count, (bool)_Val); |
2172 |
|
} |
2173 |
|
|
2174 |
|
template<class _Iter> |
2175 |
|
void _Insert(const_iterator _Where, _Iter _First, _Iter _Last, |
2176 |
|
input_iterator_tag) |
2177 |
|
{ // insert [_First, _Last) at _Where, input iterators |
2178 |
|
size_type _Off = _Where - begin(); |
2179 |
|
|
2180 |
|
for (; _First != _Last; ++_First, ++_Off) |
2181 |
|
insert(begin() + _Off, *_First); |
2182 |
|
} |
2183 |
|
|
2184 |
|
template<class _Iter> |
2185 |
|
void _Insert(const_iterator _Where, |
2186 |
|
_Iter _First, _Iter _Last, |
2187 |
|
forward_iterator_tag) |
2188 |
|
{ // insert [_First, _Last) at _Where, forward iterators |
2189 |
|
|
2190 |
|
#if _HAS_ITERATOR_DEBUGGING |
2191 |
|
_DEBUG_RANGE(_First, _Last); |
2192 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
2193 |
|
|
2194 |
|
size_type _Count = 0; |
2195 |
|
_Distance(_First, _Last, _Count); |
2196 |
|
|
2197 |
|
size_type _Off = _Insert_x(_Where, _Count); |
2198 |
|
std::copy(_First, _Last, begin() + _Off); |
2199 |
|
} |
2200 |
|
|
2201 |
|
iterator erase(const_iterator _Where_arg) |
2202 |
|
{ // erase element at _Where |
2203 |
|
iterator _Where = _Make_iter(_Where_arg); |
2204 |
|
size_type _Off = _Where - begin(); |
2205 |
|
|
2206 |
|
#if _HAS_ITERATOR_DEBUGGING |
2207 |
|
if (end() <= _Where) |
2208 |
|
_DEBUG_ERROR("vector<bool> erase iterator outside range"); |
2209 |
|
std::copy(_Where + 1, end(), _Where); |
2210 |
|
_Orphan_range(_Off, _Mysize); |
2211 |
|
|
2212 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
2213 |
|
std::copy(_Where + 1, end(), _Where); |
2214 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
2215 |
|
|
2216 |
|
_Trim(_Mysize - 1); |
2217 |
|
return (begin() + _Off); |
2218 |
|
} |
2219 |
|
|
2220 |
|
iterator erase(const_iterator _First_arg, const_iterator _Last_arg) |
2221 |
|
{ // erase [_First, _Last) |
2222 |
|
iterator _First = _Make_iter(_First_arg); |
2223 |
|
iterator _Last = _Make_iter(_Last_arg); |
2224 |
|
size_type _Off = _First - begin(); |
2225 |
|
|
2226 |
|
#if _HAS_ITERATOR_DEBUGGING |
2227 |
|
if (_Last < _First || end() < _Last) |
2228 |
|
_DEBUG_ERROR("vector<bool> erase iterator outside range"); |
2229 |
|
iterator _Next = std::copy(_Last, end(), _First); |
2230 |
|
size_type _Newsize = _Next - begin(); |
2231 |
|
_Orphan_range(_Newsize, _Mysize); |
2232 |
|
_Trim(_Newsize); |
2233 |
|
|
2234 |
|
#else /* _HAS_ITERATOR_DEBUGGING */ |
2235 |
|
iterator _Next = std::copy(_Last, end(), _First); |
2236 |
|
_Trim(_Next - begin()); |
2237 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
2238 |
|
|
2239 |
|
return (begin() + _Off); |
2240 |
|
} |
2241 |
|
|
2242 |
|
void clear() |
2243 |
|
{ // erase all elements |
2244 |
|
erase(begin(), end()); |
2245 |
|
} |
2246 |
|
|
2247 |
|
void flip() |
2248 |
|
{ // toggle all elements |
2249 |
|
for (_Vbtype::iterator _Next = _Myvec.begin(); |
2250 |
|
_Next != _Myvec.end(); ++_Next) |
2251 |
|
*_Next = (_Vbase)~*_Next; |
2252 |
|
_Trim(_Mysize); |
2253 |
|
} |
2254 |
|
|
2255 |
|
void swap(_Myt& _Right) |
2256 |
|
{ // exchange contents with right |
2257 |
|
if (this != &_Right) |
2258 |
|
{ // different, worth swapping |
2259 |
|
|
2260 |
|
#if _HAS_ITERATOR_DEBUGGING |
2261 |
|
this->_Swap_all(_Right); |
2262 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
2263 |
|
|
2264 |
|
this->_Swap_aux(_Right); |
2265 |
|
_STD swap(_Mysize, _Right._Mysize); |
2266 |
|
_Myvec.swap(_Right._Myvec); |
2267 |
|
} |
2268 |
|
} |
2269 |
|
|
2270 |
|
|
2271 |
|
|
2272 |
|
static void swap(reference _Left, reference _Right) |
2273 |
|
{ // swap _Left and _Right vector<bool> elements |
2274 |
|
bool _Val = _Left; |
2275 |
|
|
2276 |
|
_Left = _Right; |
2277 |
|
_Right = _Val; |
2278 |
|
} |
2279 |
|
|
2280 |
|
|
2281 |
|
protected: |
2282 |
|
void _Assign_n(size_type _Count, bool _Val) |
2283 |
|
{ // assign _Count * _Val |
2284 |
|
erase(begin(), end()); |
2285 |
|
_Insert_n(begin(), _Count, _Val); |
2286 |
|
} |
2287 |
|
|
2288 |
|
void _Insert_n(const_iterator _Where, |
2289 |
|
size_type _Count, bool _Val) |
2290 |
|
{ // insert _Count * _Val at _Where |
2291 |
|
size_type _Off = _Insert_x(_Where, _Count); |
2292 |
|
std::fill(begin() + _Off, begin() + (_Off + _Count), _Val); |
2293 |
|
} |
2294 |
|
|
2295 |
|
size_type _Insert_x(const_iterator _Where, size_type _Count) |
2296 |
|
{ // make room to insert _Count elements at _Where |
2297 |
|
size_type _Off = _Where - begin(); |
2298 |
|
|
2299 |
|
#if _HAS_ITERATOR_DEBUGGING |
2300 |
|
if (end() < _Where) |
2301 |
|
_DEBUG_ERROR("vector<bool> insert iterator outside range"); |
2302 |
|
bool _Realloc = capacity() - size() < _Count; |
2303 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
2304 |
|
|
2305 |
|
if (_Count == 0) |
2306 |
|
; |
2307 |
|
else if (max_size() - size() < _Count) |
2308 |
|
_Xlen(); // result too long |
2309 |
|
else |
2310 |
|
{ // worth doing |
2311 |
|
_Myvec.resize(_Nw(size() + _Count), 0); |
2312 |
|
if (size() == 0) |
2313 |
|
_Mysize += _Count; |
2314 |
|
else |
2315 |
|
{ // make room and copy down suffix |
2316 |
|
iterator _Oldend = end(); |
2317 |
|
_Mysize += _Count; |
2318 |
|
std::copy_backward(begin() + _Off, _Oldend, end()); |
2319 |
|
} |
2320 |
|
|
2321 |
|
#if _HAS_ITERATOR_DEBUGGING |
2322 |
|
_Orphan_range(_Realloc ? 0 : _Off, _Mysize); |
2323 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
2324 |
|
|
2325 |
|
} |
2326 |
|
return (_Off); |
2327 |
|
} |
2328 |
|
|
2329 |
|
static size_type _Nw(size_type _Count) |
2330 |
|
{ // return number of base words from number of bits |
2331 |
|
return ((_Count + _VBITS - 1) / _VBITS); |
2332 |
|
} |
2333 |
|
|
2334 |
|
#if _HAS_ITERATOR_DEBUGGING |
2335 |
|
void _Orphan_range(size_type _Offlo, size_type _Offhi) const |
2336 |
|
{ // orphan iterators within specified (inclusive) range |
2337 |
|
typedef _Vb_iter_base<size_type, difference_type, _Myt> _Myiterbase; |
2338 |
|
|
2339 |
|
_Lockit _Lock(_LOCK_DEBUG); |
2340 |
|
_Vbase *_Base = (_Vbase *)_VEC_ITER_BASE(_Myvec.begin()); |
2341 |
|
|
2342 |
|
_Myiterbase **_Pnext = |
2343 |
|
(_Myiterbase **)&this->_Myfirstiter; |
2344 |
|
while (*_Pnext != 0) |
2345 |
|
{ // test offset from beginning of vector |
2346 |
|
size_type _Off = _VBITS * ((*_Pnext)->_Myptr - _Base) |
2347 |
|
+ (*_Pnext)->_Myoff; |
2348 |
|
if (_Off < _Offlo || _Offhi < _Off) |
2349 |
|
_Pnext = (_Myiterbase **)&(*_Pnext)->_Mynextiter; |
2350 |
|
else |
2351 |
|
{ // orphan the iterator |
2352 |
|
(*_Pnext)->_Mycont = 0; |
2353 |
|
*_Pnext = (_Myiterbase *)(*_Pnext)->_Mynextiter; |
2354 |
|
} |
2355 |
|
} |
2356 |
|
} |
2357 |
|
#endif /* _HAS_ITERATOR_DEBUGGING */ |
2358 |
|
|
2359 |
|
void _Trim(size_type _Size) |
2360 |
|
{ // trim base vector to exact length in bits |
2361 |
|
if (max_size() < _Size) |
2362 |
|
_Xlen(); // result too long |
2363 |
|
size_type _Words = _Nw(_Size); |
2364 |
|
|
2365 |
|
if (_Words < _Myvec.size()) |
2366 |
|
_Myvec.erase(_Myvec.begin() + _Words, _Myvec.end()); |
2367 |
|
_Mysize = _Size; |
2368 |
|
_Size %= _VBITS; |
2369 |
|
if (0 < _Size) |
2370 |
|
_Myvec[_Words - 1] &= (_Vbase)((1 << _Size) - 1); |
2371 |
|
} |
2372 |
|
|
2373 |
|
void _Xlen() const |
2374 |
|
{ // report a length_error |
2375 |
|
_THROW(length_error, "vector<bool> too long"); |
2376 |
|
} |
2377 |
|
|
2378 |
|
void _Xran() const |
2379 |
|
{ // throw an out_of_range error |
2380 |
|
_THROW(out_of_range, "invalid vector<bool> subscript"); |
2381 |
|
} |
2382 |
|
|
2383 |
|
size_type _Mysize; // current length of sequence |
2384 |
|
_Vbtype _Myvec; // base vector of words |
2385 |
|
}; |
2386 |
|
|
2387 |
|
typedef vector<bool, allocator<bool> > _Bvector; |
2388 |
|
|
2389 |
|
#if _HAS_TRADITIONAL_STL |
2390 |
|
typedef _Bvector bit_vector; |
2391 |
|
#define __vector__ vector |
2392 |
|
#endif /* _HAS_TRADITIONAL_STL */ |
2393 |
|
|
2394 |
|
_STD_END |
2395 |
|
|
2396 |
|
#ifdef _MSC_VER |
2397 |
|
#pragma warning(default: 4244) |
2398 |
|
#pragma warning(pop) |
2399 |
|
#pragma pack(pop) |
2400 |
|
#endif /* _MSC_VER */ |
2401 |
|
|
2402 |
|
#endif /* RC_INVOKED */ |
2403 |
|
#endif /* _VECTOR_ */ |
2404 |
|
|
2405 |
|
/* |
2406 |
|
* This file is derived from software bearing the following |
2407 |
|
* restrictions: |
2408 |
|
* |
2409 |
|
* Copyright (c) 1994 |
2410 |
|
* Hewlett-Packard Company |
2411 |
|
* |
2412 |
|
* Permission to use, copy, modify, distribute and sell this |
2413 |
|
* software and its documentation for any purpose is hereby |
2414 |
|
* granted without fee, provided that the above copyright notice |
2415 |
|
* appear in all copies and that both that copyright notice and |
2416 |
|
* this permission notice appear in supporting documentation. |
2417 |
|
* Hewlett-Packard Company makes no representations about the |
2418 |
|
* suitability of this software for any purpose. It is provided |
2419 |
|
* "as is" without express or implied warranty. |
2420 |
|
*/ |
2421 |
|
|
2422 |
|
/* |
2423 |
|
* Copyright (c) 1992-2008 by P.J. Plauger. ALL RIGHTS RESERVED. |
2424 |
|
* Consult your license regarding permissions and restrictions. |
2425 |
|
V5.05:0009 */ |
2426 |
|
|
2427 |
|
|
2428 |
|
|
|
|
|