16 #ifndef EASTL_BITVECTOR_H
17 #define EASTL_BITVECTOR_H
20 #include <EASTL/internal/config.h>
21 #include <EASTL/vector.h>
22 #include <EASTL/algorithm.h>
23 #include <EASTL/bitset.h>
25 EA_DISABLE_VC_WARNING(4480);
27 #if defined(EA_PRAGMA_ONCE_SUPPORTED)
40 #ifndef EASTL_BITVECTOR_DEFAULT_NAME
41 #define EASTL_BITVECTOR_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " bitvector"
46 #ifndef EASTL_BITVECTOR_DEFAULT_ALLOCATOR
47 #define EASTL_BITVECTOR_DEFAULT_ALLOCATOR allocator_type(EASTL_BITVECTOR_DEFAULT_NAME)
57 template <
typename Element>
61 template <
typename Element>
65 typedef eastl_size_t size_type;
72 {
return (*mpBitWord & (Element(1) << mnBitIndex)) != 0; }
86 template <
typename Element>
90 typedef EASTL_ITC_NS::random_access_iterator_tag iterator_category;
92 typedef bool value_type;
94 typedef ptrdiff_t difference_type;
95 typedef Element element_type;
96 typedef element_type* pointer;
97 typedef element_type& reference;
98 typedef eastl_size_t size_type;
105 kBitCount = (8 *
sizeof(Element))
109 bool operator*()
const;
110 bool operator[](difference_type n)
const;
126 difference_type operator-(
const this_type& rhs)
const;
130 bool operator==(
const this_type& rhs)
const;
131 bool operator!=(
const this_type& rhs)
const;
133 bool operator< (
const this_type& rhs)
const;
134 bool operator<=(
const this_type& rhs)
const;
135 bool operator> (
const this_type& rhs)
const;
136 bool operator>=(
const this_type& rhs)
const;
138 int validate(
const element_type* pStart,
const element_type* pEnd, eastl_size_t nExtraBits)
const;
141 template <
typename,
typename,
typename>
149 template <
typename Element>
153 typedef EASTL_ITC_NS::random_access_iterator_tag iterator_category;
156 typedef bool value_type;
158 typedef ptrdiff_t difference_type;
159 typedef Element element_type;
160 typedef element_type* pointer;
161 typedef element_type& reference;
176 bitvector_iterator& operator+=(difference_type dist) { base_type::operator+=(dist);
return *
this; }
177 bitvector_iterator& operator-=(difference_type dist) { base_type::operator-=(dist);
return *
this; }
183 difference_type operator-(
const base_type& rhs)
const {
return base_type::operator-(rhs); }
199 template <
typename Allocator = EASTLAllocatorType,
206 typedef bool value_type;
208 typedef bool const_reference;
213 typedef Allocator allocator_type;
214 typedef Element element_type;
215 typedef Container container_type;
216 typedef eastl_size_t size_type;
217 typedef ptrdiff_t difference_type;
219 #if defined(_MSC_VER) && (_MSC_VER >= 1400) && (_MSC_VER <= 1600) && !EASTL_STD_CPP_ONLY
221 npos = container_type::npos,
225 static const size_type npos = container_type::npos;
226 static const size_type
kMaxSize = container_type::kMaxSize;
231 kBitCount = 8 *
sizeof(Element)
235 container_type mContainer;
236 size_type mFreeBitCount;
241 explicit bitvector(size_type n,
const allocator_type&
allocator = EASTL_BITVECTOR_DEFAULT_ALLOCATOR);
242 bitvector(size_type n, value_type value,
const allocator_type&
allocator = EASTL_BITVECTOR_DEFAULT_ALLOCATOR);
245 template <
typename InputIterator>
246 bitvector(InputIterator first, InputIterator last);
249 void swap(this_type& x);
251 template <
typename InputIterator>
252 void assign(InputIterator first, InputIterator last);
255 const_iterator begin() const EA_NOEXCEPT;
256 const_iterator cbegin() const EA_NOEXCEPT;
259 const_iterator end() const EA_NOEXCEPT;
260 const_iterator cend() const EA_NOEXCEPT;
263 const_reverse_iterator rbegin() const EA_NOEXCEPT;
264 const_reverse_iterator crbegin() const EA_NOEXCEPT;
267 const_reverse_iterator rend() const EA_NOEXCEPT;
268 const_reverse_iterator crend() const EA_NOEXCEPT;
270 bool empty() const EA_NOEXCEPT;
271 size_type size() const EA_NOEXCEPT;
272 size_type capacity() const EA_NOEXCEPT;
274 void resize(size_type n, value_type value);
275 void resize(size_type n);
276 void reserve(size_type n);
277 void set_capacity(size_type n = npos);
280 void push_back(value_type value);
284 const_reference front() const;
286 const_reference back() const;
288 bool test(size_type n,
bool defaultValue) const;
289 void set(size_type n,
bool value);
291 reference at(size_type n);
292 const_reference at(size_type n) const;
294 reference operator[](size_type n);
295 const_reference operator[](size_type n) const;
310 element_type* data() EA_NOEXCEPT;
311 const element_type* data() const EA_NOEXCEPT;
313 iterator insert(const_iterator position, value_type value);
314 void insert(const_iterator position, size_type n, value_type value);
319 iterator erase(const_iterator position);
320 iterator erase(const_iterator first, const_iterator last);
323 reverse_iterator erase(const_reverse_iterator first, const_reverse_iterator last);
326 void reset_lose_memory();
328 container_type& get_container();
329 const container_type& get_container() const;
331 bool validate() const;
332 int validate_iterator(const_iterator i) const;
342 template <typename Element>
350 template <
typename Element>
351 bitvector_reference<Element>&
352 bitvector_reference<Element>::operator=(
bool value)
354 const Element mask = (Element)(Element(1) << mnBitIndex);
365 template <
typename Element>
366 bitvector_reference<Element>&
367 bitvector_reference<Element>::operator=(
const bitvector_reference& rhs)
369 return (*
this = (
bool)rhs);
373 template <
typename Element>
374 void bitvector_reference<Element>::CopyFrom(
const bitvector_reference& rhs)
376 mpBitWord = rhs.mpBitWord;
377 mnBitIndex = rhs.mnBitIndex;
387 template <
typename Element>
388 bitvector_const_iterator<Element>::bitvector_const_iterator()
394 template <
typename Element>
395 bitvector_const_iterator<Element>::bitvector_const_iterator(
const Element* p, eastl_size_t i)
396 : mReference(const_cast<Element*>(p), i)
401 template <
typename Element>
402 bitvector_const_iterator<Element>::bitvector_const_iterator(
const reference_type& reference)
403 : mReference(reference)
408 template <
typename Element>
409 bitvector_const_iterator<Element>&
410 bitvector_const_iterator<Element>::operator++()
412 ++mReference.mnBitIndex;
414 if(mReference.mnBitIndex == kBitCount)
416 ++mReference.mpBitWord;
417 mReference.mnBitIndex = 0;
424 template <
typename Element>
425 bitvector_const_iterator<Element>&
426 bitvector_const_iterator<Element>::operator--()
428 if(mReference.mnBitIndex == 0)
430 --mReference.mpBitWord;
431 mReference.mnBitIndex = kBitCount;
434 --mReference.mnBitIndex;
439 template <
typename Element>
440 bitvector_const_iterator<Element>
441 bitvector_const_iterator<Element>::operator++(
int)
443 bitvector_const_iterator
copy(*
this);
449 template <
typename Element>
450 bitvector_const_iterator<Element>
451 bitvector_const_iterator<Element>::operator--(
int)
453 bitvector_const_iterator
copy(*
this);
459 template <
typename Element>
460 bitvector_const_iterator<Element>&
461 bitvector_const_iterator<Element>::operator+=(difference_type n)
463 n += mReference.mnBitIndex;
465 if(n >= difference_type(0))
467 mReference.mpBitWord += n / kBitCount;
468 mReference.mnBitIndex = (size_type)(n % kBitCount);
476 const size_type backwards = (size_type)(-n + kBitCount - 1);
477 mReference.mpBitWord -= backwards / kBitCount;
485 mReference.mnBitIndex = (kBitCount - 1) - (backwards % kBitCount);
492 template <
typename Element>
493 bitvector_const_iterator<Element>&
494 bitvector_const_iterator<Element>::operator-=(difference_type n)
496 return (*
this += -n);
500 template <
typename Element>
501 bitvector_const_iterator<Element>
502 bitvector_const_iterator<Element>::operator+(difference_type n)
const
504 bitvector_const_iterator
copy(*
this);
510 template <
typename Element>
511 bitvector_const_iterator<Element>
512 bitvector_const_iterator<Element>::operator-(difference_type n)
const
514 bitvector_const_iterator
copy(*
this);
520 template <
typename Element>
521 typename bitvector_const_iterator<Element>::difference_type
522 bitvector_const_iterator<Element>::operator-(
const this_type& rhs)
const
524 return ((mReference.mpBitWord - rhs.mReference.mpBitWord) * kBitCount) + mReference.mnBitIndex - rhs.mReference.mnBitIndex;
528 template <
typename Element>
529 bool bitvector_const_iterator<Element>::operator==(
const this_type& rhs)
const
531 return (mReference.mpBitWord == rhs.mReference.mpBitWord) && (mReference.mnBitIndex == rhs.mReference.mnBitIndex);
535 template <
typename Element>
536 bool bitvector_const_iterator<Element>::operator!=(
const this_type& rhs)
const
538 return !(*
this == rhs);
542 template <
typename Element>
543 bool bitvector_const_iterator<Element>::operator<(
const this_type& rhs)
const
545 return (mReference.mpBitWord < rhs.mReference.mpBitWord) ||
546 ((mReference.mpBitWord == rhs.mReference.mpBitWord) && (mReference.mnBitIndex < rhs.mReference.mnBitIndex));
550 template <
typename Element>
551 bool bitvector_const_iterator<Element>::operator<=(
const this_type& rhs)
const
553 return (mReference.mpBitWord < rhs.mReference.mpBitWord) ||
554 ((mReference.mpBitWord == rhs.mReference.mpBitWord) && (mReference.mnBitIndex <= rhs.mReference.mnBitIndex));
558 template <
typename Element>
559 bool bitvector_const_iterator<Element>::operator>(
const this_type& rhs)
const
561 return !(*
this <= rhs);
565 template <
typename Element>
566 bool bitvector_const_iterator<Element>::operator>=(
const this_type& rhs)
const
568 return !(*
this < rhs);
572 template <
typename Element>
573 bool bitvector_const_iterator<Element>::operator*()
const
579 template <
typename Element>
580 bool bitvector_const_iterator<Element>::operator[](difference_type n)
const
586 template <
typename Element>
587 bitvector_const_iterator<Element>& bitvector_const_iterator<Element>::operator= (
const this_type& rhs)
589 mReference.CopyFrom(rhs.mReference);
594 template <
typename Element>
595 int bitvector_const_iterator<Element>::validate(
const Element* pStart,
const Element* pEnd, eastl_size_t nExtraBits)
const
597 const Element*
const pCurrent = mReference.mpBitWord;
599 if(pCurrent >= pStart)
603 if(pCurrent == pEnd && mReference)
605 else if(pCurrent < pEnd)
608 else if(pCurrent == (pEnd - 1))
610 const size_type bit = mReference.mnBitIndex;
611 const size_type lastbit = kBitCount - nExtraBits;
615 else if(bit < lastbit)
618 else if(pCurrent < pEnd)
624 return eastl::isf_none;
633 template <
typename Element>
634 bitvector_iterator<Element>::bitvector_iterator()
639 template <
typename Element>
640 bitvector_iterator<Element>::bitvector_iterator(Element* p, eastl_size_t i)
646 template <
typename Element>
647 bitvector_iterator<Element>::bitvector_iterator(reference_type& reference)
648 : base_type(reference)
653 template <
typename Element>
654 typename bitvector_iterator<Element>::reference_type
655 bitvector_iterator<Element>::operator*()
const
657 return base_type::mReference;
661 template <
typename Element>
662 typename bitvector_iterator<Element>::reference_type
663 bitvector_iterator<Element>::operator[](difference_type n)
const
669 template <
typename Element>
670 void MoveBits(bitvector_iterator<Element> start,
671 bitvector_iterator<Element> end,
672 bitvector_iterator<Element> dest)
687 dest += (end - start);
699 template <
typename Element>
700 bitvector_iterator<Element>
701 bitvector_iterator<Element>::operator++(
int)
703 bitvector_iterator
copy(*
this);
709 template <
typename Element>
710 bitvector_iterator<Element>
711 bitvector_iterator<Element>::operator--(
int)
713 bitvector_iterator
copy(*
this);
719 template <
typename Element>
720 bitvector_iterator<Element>
721 bitvector_iterator<Element>::operator+(difference_type n)
const
723 bitvector_iterator
copy(*
this);
729 template <
typename Element>
730 bitvector_iterator<Element>
731 bitvector_iterator<Element>::operator-(difference_type n)
const
733 bitvector_iterator
copy(*
this);
745 template <
typename Allocator,
typename Element,
typename Container>
746 template <
typename InputIterator>
747 void bitvector<Allocator, Element, Container>::assign(InputIterator first, InputIterator last)
762 template <
typename Allocator,
typename Element,
typename Container>
763 typename bitvector<Allocator, Element, Container>::iterator
764 bitvector<Allocator, Element, Container>::begin() EA_NOEXCEPT
766 return iterator(mContainer.begin(), 0);
770 template <
typename Allocator,
typename Element,
typename Container>
771 typename bitvector<Allocator, Element, Container>::const_iterator
772 bitvector<Allocator, Element, Container>::begin() const EA_NOEXCEPT
774 return const_iterator(mContainer.begin(), 0);
778 template <
typename Allocator,
typename Element,
typename Container>
779 typename bitvector<Allocator, Element, Container>::const_iterator
780 bitvector<Allocator, Element, Container>::cbegin() const EA_NOEXCEPT
782 return const_iterator(mContainer.begin(), 0);
786 template <
typename Allocator,
typename Element,
typename Container>
787 typename bitvector<Allocator, Element, Container>::iterator
788 bitvector<Allocator, Element, Container>::end() EA_NOEXCEPT
790 return iterator(mContainer.end(), 0) - mFreeBitCount;
794 template <
typename Allocator,
typename Element,
typename Container>
795 typename bitvector<Allocator, Element, Container>::const_iterator
796 bitvector<Allocator, Element, Container>::end() const EA_NOEXCEPT
798 return const_iterator(mContainer.end(), 0) - mFreeBitCount;
802 template <
typename Allocator,
typename Element,
typename Container>
803 typename bitvector<Allocator, Element, Container>::const_iterator
804 bitvector<Allocator, Element, Container>::cend() const EA_NOEXCEPT
806 return const_iterator(mContainer.end(), 0) - mFreeBitCount;
810 template <
typename Allocator,
typename Element,
typename Container>
811 bool bitvector<Allocator, Element, Container>::empty() const EA_NOEXCEPT
813 return mContainer.empty();
817 template <
typename Allocator,
typename Element,
typename Container>
818 typename bitvector<Allocator, Element, Container>::size_type
819 bitvector<Allocator, Element, Container>::size() const EA_NOEXCEPT
821 return (mContainer.size() * kBitCount) - mFreeBitCount;
825 template <
typename Allocator,
typename Element,
typename Container>
826 typename bitvector<Allocator, Element, Container>::size_type
827 bitvector<Allocator, Element, Container>::capacity() const EA_NOEXCEPT
829 return mContainer.capacity() * kBitCount;
833 template <
typename Allocator,
typename Element,
typename Container>
834 void bitvector<Allocator, Element, Container>::set_capacity(size_type n)
837 mContainer.set_capacity(npos);
839 mContainer.set_capacity((n + kBitCount - 1) / kBitCount);
843 template <
typename Allocator,
typename Element,
typename Container>
844 typename bitvector<Allocator, Element, Container>::reverse_iterator
845 bitvector<Allocator, Element, Container>::rbegin() EA_NOEXCEPT
847 return reverse_iterator(end());
851 template <
typename Allocator,
typename Element,
typename Container>
852 typename bitvector<Allocator, Element, Container>::const_reverse_iterator
853 bitvector<Allocator, Element, Container>::rbegin() const EA_NOEXCEPT
855 return const_reverse_iterator(end());
859 template <
typename Allocator,
typename Element,
typename Container>
860 typename bitvector<Allocator, Element, Container>::const_reverse_iterator
861 bitvector<Allocator, Element, Container>::crbegin() const EA_NOEXCEPT
863 return const_reverse_iterator(end());
867 template <
typename Allocator,
typename Element,
typename Container>
868 typename bitvector<Allocator, Element, Container>::reverse_iterator
869 bitvector<Allocator, Element, Container>::rend() EA_NOEXCEPT
871 return reverse_iterator(begin());
875 template <
typename Allocator,
typename Element,
typename Container>
876 typename bitvector<Allocator, Element, Container>::const_reverse_iterator
877 bitvector<Allocator, Element, Container>::rend() const EA_NOEXCEPT
879 return const_reverse_iterator(begin());
883 template <
typename Allocator,
typename Element,
typename Container>
884 typename bitvector<Allocator, Element, Container>::const_reverse_iterator
885 bitvector<Allocator, Element, Container>::crend() const EA_NOEXCEPT
887 return const_reverse_iterator(begin());
891 template <
typename Allocator,
typename Element,
typename Container>
892 typename bitvector<Allocator, Element, Container>::reference
893 bitvector<Allocator, Element, Container>::front()
895 EASTL_ASSERT(!empty());
896 return reference(&mContainer[0], 0);
900 template <
typename Allocator,
typename Element,
typename Container>
901 typename bitvector<Allocator, Element, Container>::const_reference
902 bitvector<Allocator, Element, Container>::front()
const
904 EASTL_ASSERT(!empty());
907 return reference(
const_cast<Element*
>(&mContainer[0]), 0);
911 template <
typename Allocator,
typename Element,
typename Container>
912 typename bitvector<Allocator, Element, Container>::reference
913 bitvector<Allocator, Element, Container>::back()
915 EASTL_ASSERT(!empty());
920 template <
typename Allocator,
typename Element,
typename Container>
921 typename bitvector<Allocator, Element, Container>::const_reference
922 bitvector<Allocator, Element, Container>::back()
const
924 EASTL_ASSERT(!empty());
929 template <
typename Allocator,
typename Element,
typename Container>
930 void bitvector<Allocator, Element, Container>::push_back()
934 mContainer.push_back();
935 mFreeBitCount = kBitCount;
942 template <
typename Allocator,
typename Element,
typename Container>
943 void bitvector<Allocator, Element, Container>::push_back(value_type value)
950 template <
typename Allocator,
typename Element,
typename Container>
951 void bitvector<Allocator, Element, Container>::pop_back()
953 EASTL_ASSERT(!empty());
955 if(++mFreeBitCount == kBitCount)
957 mContainer.pop_back();
963 template <
typename Allocator,
typename Element,
typename Container>
964 void bitvector<Allocator, Element, Container>::reserve(size_type n)
966 const size_type wordCount = (n + kBitCount - 1) / kBitCount;
967 mContainer.reserve(wordCount);
971 template <
typename Allocator,
typename Element,
typename Container>
972 void bitvector<Allocator, Element, Container>::resize(size_type n)
974 const size_type wordCount = (n + kBitCount - 1) / kBitCount;
975 const size_type extra = (wordCount * kBitCount) - n;
977 mContainer.resize(wordCount);
978 mFreeBitCount = extra;
982 template <
typename Allocator,
typename Element,
typename Container>
983 void bitvector<Allocator, Element, Container>::resize(size_type n, value_type value)
985 const size_type s = size();
990 size_type newbits = n - s;
992 while(mFreeBitCount && newbits)
1001 element_type element(0);
1005 const size_type words = (n + kBitCount - 1) / kBitCount;
1006 const size_type extra = words * kBitCount - n;
1007 mContainer.resize(words, element);
1008 mFreeBitCount = extra;
1013 template <
typename Allocator,
typename Element,
typename Container>
1014 bool bitvector<Allocator, Element, Container>::test(size_type n,
bool defaultValue)
const
1017 return *(begin() + (difference_type)n);
1019 return defaultValue;
1023 template <
typename Allocator,
typename Element,
typename Container>
1024 void bitvector<Allocator, Element, Container>::set(size_type n,
bool value)
1026 if(EASTL_UNLIKELY(n >= size()))
1029 *(begin() + (difference_type)n) = value;
1033 template <
typename Allocator,
typename Element,
typename Container>
1034 typename bitvector<Allocator, Element, Container>::reference
1035 bitvector<Allocator, Element, Container>::at(size_type n)
1041 #if EASTL_EXCEPTIONS_ENABLED
1042 if(EASTL_UNLIKELY(n >= size()))
1043 throw std::out_of_range(
"bitvector::at -- out of range");
1044 #elif EASTL_ASSERT_ENABLED
1045 if(EASTL_UNLIKELY(n >= size()))
1046 EASTL_FAIL_MSG(
"bitvector::at -- out of range");
1049 return *(begin() + (difference_type)n);
1053 template <
typename Allocator,
typename Element,
typename Container>
1054 typename bitvector<Allocator, Element, Container>::const_reference
1055 bitvector<Allocator, Element, Container>::at(size_type n)
const
1057 #if EASTL_EXCEPTIONS_ENABLED
1058 if(EASTL_UNLIKELY(n >= size()))
1059 throw std::out_of_range(
"bitvector::at -- out of range");
1060 #elif EASTL_ASSERT_ENABLED
1061 if(EASTL_UNLIKELY(n >= size()))
1062 EASTL_FAIL_MSG(
"bitvector::at -- out of range");
1065 return *(begin() + (difference_type)n);
1069 template <
typename Allocator,
typename Element,
typename Container>
1070 typename bitvector<Allocator, Element, Container>::reference
1071 bitvector<Allocator, Element, Container>::operator[](size_type n)
1073 return *(begin() + (difference_type)n);
1077 template <
typename Allocator,
typename Element,
typename Container>
1078 typename bitvector<Allocator, Element, Container>::const_reference
1079 bitvector<Allocator, Element, Container>::operator[](size_type n)
const
1081 return *(begin() + (difference_type)n);
1107 template <
typename Allocator,
typename Element,
typename Container>
1108 inline typename bitvector<Allocator, Element, Container>::container_type&
1109 bitvector<Allocator, Element, Container>::get_container()
1115 template <
typename Allocator,
typename Element,
typename Container>
1116 inline const typename bitvector<Allocator, Element, Container>::container_type&
1117 bitvector<Allocator, Element, Container>::get_container()
const
1123 template <
typename Allocator,
typename Element,
typename Container>
1124 bool bitvector<Allocator, Element, Container>::validate()
const
1126 if(!mContainer.validate())
1129 if((
unsigned)mFreeBitCount >= kBitCount)
1136 template <
typename Allocator,
typename Element,
typename Container>
1137 int bitvector<Allocator, Element, Container>::validate_iterator(const_iterator i)
const
1139 return i.validate(mContainer.begin(), mContainer.end(), mFreeBitCount);
1143 template <
typename Allocator,
typename Element,
typename Container>
1144 typename bitvector<Allocator, Element, Container>::element_type*
1145 bitvector<Allocator, Element, Container>::data() EA_NOEXCEPT
1147 return mContainer.data();
1151 template <
typename Allocator,
typename Element,
typename Container>
1152 const typename bitvector<Allocator, Element, Container>::element_type*
1153 bitvector<Allocator, Element, Container>::data() const EA_NOEXCEPT
1155 return mContainer.data();
1159 template <
typename Allocator,
typename Element,
typename Container>
1160 typename bitvector<Allocator, Element, Container>::iterator
1161 bitvector<Allocator, Element, Container>::insert(const_iterator position, value_type value)
1163 iterator iPosition(position.get_reference_type());
1165 #if EASTL_ASSERT_ENABLED
1167 EASTL_FAIL_MSG(
"bitvector::insert -- invalid iterator");
1171 const typename iterator::difference_type n = iPosition - begin();
1173 iPosition = begin() + n;
1175 MoveBits(iPosition, --end(), ++iterator(iPosition));
1182 template <
typename Allocator,
typename Element,
typename Container>
1183 void bitvector<Allocator, Element, Container>::insert(const_iterator position, size_type n, value_type value)
1185 iterator iPosition(position.get_reference_type());
1187 #if EASTL_ASSERT_ENABLED
1189 EASTL_FAIL_MSG(
"bitvector::insert -- invalid iterator");
1193 const typename iterator::difference_type p = iPosition - begin();
1195 iPosition = begin() + p;
1197 iterator insert_end = iPosition + n;
1198 MoveBits(iPosition, end() - n, insert_end);
1201 while(iPosition != insert_end)
1238 template <
typename Allocator,
typename Element,
typename Container>
1239 typename bitvector<Allocator, Element, Container>::iterator
1240 bitvector<Allocator, Element, Container>::erase(const_iterator position)
1242 iterator iPosition(position.get_reference_type());
1244 #if EASTL_ASSERT_ENABLED
1246 EASTL_FAIL_MSG(
"bitvector::erase -- invalid iterator");
1249 MoveBits(++iterator(iPosition), end(), iPosition);
1258 template <
typename Allocator,
typename Element,
typename Container>
1259 typename bitvector<Allocator, Element, Container>::iterator
1260 bitvector<Allocator, Element, Container>::erase(const_iterator first, const_iterator last)
1262 iterator iFirst(first.get_reference_type());
1263 iterator iLast(last.get_reference_type());
1265 #if EASTL_ASSERT_ENABLED
1267 EASTL_FAIL_MSG(
"bitvector::erase -- invalid iterator");
1270 if(!(iFirst == iLast))
1272 #if EASTL_ASSERT_ENABLED
1274 EASTL_FAIL_MSG(
"bitvector::erase -- invalid iterator");
1277 const size_type eraseCount = (size_type)(iLast - iFirst);
1278 MoveBits(iLast, end(), iFirst);
1279 resize(size() - eraseCount);
1282 #if EASTL_ASSERT_ENABLED
1284 EASTL_FAIL_MSG(
"bitvector::erase -- invalid iterator");
1292 template <
typename Allocator,
typename Element,
typename Container>
1293 typename bitvector<Allocator, Element, Container>::reverse_iterator
1294 bitvector<Allocator, Element, Container>::erase(const_reverse_iterator position)
1296 return reverse_iterator(erase((++position).base()));
1300 template <
typename Allocator,
typename Element,
typename Container>
1301 typename bitvector<Allocator, Element, Container>::reverse_iterator
1302 bitvector<Allocator, Element, Container>::erase(const_reverse_iterator first, const_reverse_iterator last)
1311 return reverse_iterator(erase(last.base(), first.base()));
1315 template <
typename Allocator,
typename Element,
typename Container>
1316 void bitvector<Allocator, Element, Container>::swap(this_type& rhs)
1318 mContainer.swap(rhs.mContainer);
1319 eastl::swap(mFreeBitCount, rhs.mFreeBitCount);
1323 template <
typename Allocator,
typename Element,
typename Container>
1324 void bitvector<Allocator, Element, Container>::reset_lose_memory()
1326 mContainer.reset_lose_memory();
1331 template <
typename Allocator,
typename Element,
typename Container>
1332 void bitvector<Allocator, Element, Container>::clear()
1339 template <
typename Allocator,
typename Element,
typename Container>
1340 bitvector<Allocator, Element, Container>&
1341 bitvector<Allocator, Element, Container>::operator=(
const bitvector& rhs)
1344 mContainer = rhs.mContainer;
1345 mFreeBitCount = rhs.mFreeBitCount;
1351 template <
typename Allocator,
typename Element,
typename Container>
1352 bitvector<Allocator, Element, Container>::bitvector()
1359 template <
typename Allocator,
typename Element,
typename Container>
1360 bitvector<Allocator, Element, Container>::bitvector(
const allocator_type& allocator)
1361 : mContainer(allocator),
1367 template <
typename Allocator,
typename Element,
typename Container>
1368 bitvector<Allocator, Element, Container>::bitvector(size_type n,
const allocator_type& allocator)
1369 : mContainer((n + kBitCount - 1) / kBitCount, allocator)
1371 mFreeBitCount = kBitCount - (n % kBitCount);
1373 if(mFreeBitCount == kBitCount)
1378 template <
typename Allocator,
typename Element,
typename Container>
1379 bitvector<Allocator, Element, Container>::bitvector(size_type n, value_type value,
const allocator_type& allocator)
1380 : mContainer((n + kBitCount - 1) / kBitCount, value ? ~element_type(0) : element_type(0), allocator)
1382 mFreeBitCount = kBitCount - (n % kBitCount);
1384 if(mFreeBitCount == kBitCount)
1389 template <
typename Allocator,
typename Element,
typename Container>
1390 bitvector<Allocator, Element, Container>::bitvector(
const bitvector&
copy)
1391 : mContainer(
copy.mContainer),
1392 mFreeBitCount(
copy.mFreeBitCount)
1397 template <
typename Allocator,
typename Element,
typename Container>
1398 template <
typename InputIterator>
1399 bitvector<Allocator, Element, Container>::bitvector(InputIterator first, InputIterator last)
1403 assign(first, last);
1412 template <
typename Allocator,
typename Element,
typename Container>
1413 inline bool operator==(
const bitvector<Allocator, Element, Container>& a,
1414 const bitvector<Allocator, Element, Container>& b)
1417 return ((a.size() == b.size()) &&
eastl::equal(a.begin(), a.end(), b.begin()));
1421 template <
typename Allocator,
typename Element,
typename Container>
1422 inline bool operator!=(
const bitvector<Allocator, Element, Container>& a,
1423 const bitvector<Allocator, Element, Container>& b)
1425 return !operator==(a, b);
1429 template <
typename Allocator,
typename Element,
typename Container>
1430 inline bool operator<(
const bitvector<Allocator, Element, Container>& a,
1431 const bitvector<Allocator, Element, Container>& b)
1438 template <
typename Allocator,
typename Element,
typename Container>
1439 inline bool operator>(
const bitvector<Allocator, Element, Container>& a,
1440 const bitvector<Allocator, Element, Container>& b)
1446 template <
typename Allocator,
typename Element,
typename Container>
1447 inline bool operator<=(
const bitvector<Allocator, Element, Container>& a,
1448 const bitvector<Allocator, Element, Container>& b)
1454 template <
typename Allocator,
typename Element,
typename Container>
1455 inline bool operator>=(
const bitvector<Allocator, Element, Container>& a,
1456 const bitvector<Allocator, Element, Container>& b)
1461 template <
typename Allocator,
typename Element,
typename Container>
1462 inline void swap(bitvector<Allocator, Element, Container>& a,
1463 bitvector<Allocator, Element, Container>& b)
1472 EA_RESTORE_VC_WARNING();
Definition: allocator.h:52
Definition: bitvector.h:88
Definition: bitvector.h:151
Definition: bitvector.h:63
Definition: bitvector.h:203
static const size_type kMaxSize
'npos' means non-valid position or simply non-position.
Definition: bitvector.h:226
Definition: iterator.h:224
EA Standard Template Library.
Definition: algorithm.h:288
EASTL_BITSET_WORD_TYPE_DEFAULT BitvectorWordType
Definition: bitvector.h:54
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
Definition: copy_help.h:191
EA_CPP14_CONSTEXPR bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
Definition: algorithm.h:1856
@ isf_valid
This is called none and not called invalid because it is not strictly the opposite of invalid.
Definition: iterator.h:56
@ isf_can_dereference
The iterator is valid and points to the same element it did when created. For example,...
Definition: iterator.h:58
@ isf_current
The iterator is valid, which means it is in the range of [begin, end].
Definition: iterator.h:57
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
Definition: algorithm.h:1996
Definition: iterator.h:86