libstdc++
dynamic_bitset
Go to the documentation of this file.
1// TR2 <dynamic_bitset> -*- C++ -*-
2
3// Copyright (C) 2009-2025 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file tr2/dynamic_bitset
26 * This is a TR2 C++ Library header.
27 */
28
29#ifndef _GLIBCXX_TR2_DYNAMIC_BITSET
30#define _GLIBCXX_TR2_DYNAMIC_BITSET 1
31
32#ifdef _GLIBCXX_SYSHDR
33#pragma GCC system_header
34#endif
35
36#include <limits>
37#include <vector>
38#include <string>
39#include <istream>
40#include <bits/functexcept.h>
41#include <bits/stl_algo.h> // For fill
42#include <bits/cxxabi_forced.h>
43
44namespace std _GLIBCXX_VISIBILITY(default)
45{
46_GLIBCXX_BEGIN_NAMESPACE_VERSION
47
48namespace tr2
49{
50 /**
51 * @defgroup dynamic_bitset Dynamic Bitset.
52 * @ingroup extensions
53 *
54 * @{
55 */
56
57 /**
58 * Base class, general case.
59 *
60 * See documentation for dynamic_bitset.
61 */
62 template<typename _WordT = unsigned long long,
63 typename _Alloc = std::allocator<_WordT>>
65 {
66 static_assert(std::is_unsigned<_WordT>::value, "template argument "
67 "_WordT not an unsigned integral type");
68
69 typedef _WordT block_type;
70 typedef _Alloc allocator_type;
71 typedef size_t size_type;
72
73 static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type);
74 static const size_type npos = static_cast<size_type>(-1);
75
76 /// 0 is the least significant word.
78
79 explicit
80 __dynamic_bitset_base(const allocator_type& __alloc)
81 : _M_w(__alloc)
82 { }
83
84 __dynamic_bitset_base() = default;
87 __dynamic_bitset_base& operator=(const __dynamic_bitset_base&) = default;
88 __dynamic_bitset_base& operator=(__dynamic_bitset_base&&) = default;
89 ~__dynamic_bitset_base() = default;
90
91 explicit
92 __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL,
93 const allocator_type& __alloc = allocator_type())
94 : _M_w(__nbits / _S_bits_per_block + (__nbits % _S_bits_per_block > 0),
95 block_type(0), __alloc)
96 {
97 if (__nbits < std::numeric_limits<decltype(__val)>::digits)
98 __val &= ~(-1ULL << __nbits);
99 if (__val == 0)
100 return;
101
102 if _GLIBCXX17_CONSTEXPR (sizeof(__val) == sizeof(block_type))
103 _M_w[0] = __val;
104 else
105 {
106 const size_t __n
107 = std::min(_M_w.size(), sizeof(__val) / sizeof(block_type));
108 for (size_t __i = 0; __val && __i < __n; ++__i)
109 {
110 _M_w[__i] = static_cast<block_type>(__val);
111 __val >>= _S_bits_per_block;
112 }
113 }
114 }
115
116 void
117 _M_swap(__dynamic_bitset_base& __b) noexcept
118 { this->_M_w.swap(__b._M_w); }
119
120 void
121 _M_clear() noexcept
122 { this->_M_w.clear(); }
123
124 void
125 _M_resize(size_t __nbits, bool __value)
126 {
127 size_t __sz = __nbits / _S_bits_per_block;
128 if (__nbits % _S_bits_per_block > 0)
129 ++__sz;
130 if (__sz != this->_M_w.size())
131 {
132 block_type __val = 0;
133 if (__value)
135 this->_M_w.resize(__sz, __val);
136 }
137 }
138
139 allocator_type
140 _M_get_allocator() const noexcept
141 { return this->_M_w.get_allocator(); }
142
143 static size_type
144 _S_whichword(size_type __pos) noexcept
145 { return __pos / _S_bits_per_block; }
146
147 static size_type
148 _S_whichbyte(size_type __pos) noexcept
149 { return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
150
151 static size_type
152 _S_whichbit(size_type __pos) noexcept
153 { return __pos % _S_bits_per_block; }
154
155 static block_type
156 _S_maskbit(size_type __pos) noexcept
157 { return (static_cast<block_type>(1)) << _S_whichbit(__pos); }
158
159 block_type&
160 _M_getword(size_type __pos) noexcept
161 { return this->_M_w[_S_whichword(__pos)]; }
162
163 block_type
164 _M_getword(size_type __pos) const noexcept
165 { return this->_M_w[_S_whichword(__pos)]; }
166
167 block_type&
168 _M_hiword() noexcept
169 { return this->_M_w[_M_w.size() - 1]; }
170
171 block_type
172 _M_hiword() const noexcept
173 { return this->_M_w[_M_w.size() - 1]; }
174
175 void
176 _M_do_and(const __dynamic_bitset_base& __x) noexcept
177 {
178 if (__x._M_w.size() == this->_M_w.size())
179 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
180 this->_M_w[__i] &= __x._M_w[__i];
181 else
182 return;
183 }
184
185 void
186 _M_do_or(const __dynamic_bitset_base& __x) noexcept
187 {
188 if (__x._M_w.size() == this->_M_w.size())
189 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
190 this->_M_w[__i] |= __x._M_w[__i];
191 else
192 return;
193 }
194
195 void
196 _M_do_xor(const __dynamic_bitset_base& __x) noexcept
197 {
198 if (__x._M_w.size() == this->_M_w.size())
199 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
200 this->_M_w[__i] ^= __x._M_w[__i];
201 else
202 return;
203 }
204
205 void
206 _M_do_dif(const __dynamic_bitset_base& __x) noexcept
207 {
208 if (__x._M_w.size() == this->_M_w.size())
209 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
210 this->_M_w[__i] &= ~__x._M_w[__i];
211 else
212 return;
213 }
214
215 void
216 _M_do_left_shift(size_t __shift);
217
218 void
219 _M_do_right_shift(size_t __shift);
220
221 void
222 _M_do_flip() noexcept
223 {
224 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
225 this->_M_w[__i] = ~this->_M_w[__i];
226 }
227
228 void
229 _M_do_set() noexcept
230 {
231 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
232 this->_M_w[__i] = static_cast<block_type>(-1);
233 }
234
235 void
236 _M_do_reset() noexcept
237 {
238 std::fill(_M_w.begin(), _M_w.end(), static_cast<block_type>(0));
239 }
240
241 bool
242 _M_is_equal(const __dynamic_bitset_base& __x) const noexcept
243 {
244 if (__x._M_w.size() == this->_M_w.size())
245 {
246 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
247 if (this->_M_w[__i] != __x._M_w[__i])
248 return false;
249 return true;
250 }
251 else
252 return false;
253 }
254
255 bool
256 _M_is_less(const __dynamic_bitset_base& __x) const noexcept
257 {
258 if (__x._M_w.size() == this->_M_w.size())
259 {
260 for (size_t __i = this->_M_w.size(); __i > 0; --__i)
261 {
262 if (this->_M_w[__i-1] < __x._M_w[__i-1])
263 return true;
264 else if (this->_M_w[__i-1] > __x._M_w[__i-1])
265 return false;
266 }
267 return false;
268 }
269 else
270 return false;
271 }
272
273 size_t
274 _M_are_all_aux() const noexcept
275 {
276 for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i)
277 if (_M_w[__i] != static_cast<block_type>(-1))
278 return 0;
279 return ((this->_M_w.size() - 1) * _S_bits_per_block
280 + __builtin_popcountll(this->_M_hiword()));
281 }
282
283 bool
284 _M_is_any() const noexcept
285 {
286 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
287 if (this->_M_w[__i] != static_cast<block_type>(0))
288 return true;
289 return false;
290 }
291
292 bool
293 _M_is_subset_of(const __dynamic_bitset_base& __b) noexcept
294 {
295 if (__b._M_w.size() == this->_M_w.size())
296 {
297 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
298 if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i]))
299 return false;
300 return true;
301 }
302 else
303 return false;
304 }
305
306 bool
307 _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const noexcept
308 {
309 if (this->_M_is_subset_of(__b))
310 {
311 if (*this == __b)
312 return false;
313 else
314 return true;
315 }
316 else
317 return false;
318 }
319
320 size_t
321 _M_do_count() const noexcept
322 {
323 size_t __result = 0;
324 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
325 __result += __builtin_popcountll(this->_M_w[__i]);
326 return __result;
327 }
328
329 size_type
330 _M_size() const noexcept
331 { return this->_M_w.size(); }
332
333 unsigned long
334 _M_do_to_ulong() const;
335
336 unsigned long long
337 _M_do_to_ullong() const;
338
339 // find first "on" bit
340 size_type
341 _M_do_find_first(size_t __not_found) const;
342
343 // find the next "on" bit that follows "prev"
344 size_type
345 _M_do_find_next(size_t __prev, size_t __not_found) const;
346
347 // do append of block
348 void
349 _M_do_append_block(block_type __block, size_type __pos)
350 {
351 size_t __offset = __pos % _S_bits_per_block;
352 if (__offset == 0)
353 this->_M_w.push_back(__block);
354 else
355 {
356 this->_M_hiword() |= (__block << __offset);
357 this->_M_w.push_back(__block >> (_S_bits_per_block - __offset));
358 }
359 }
360 };
361
362 /**
363 * @brief The %dynamic_bitset class represents a sequence of bits.
364 *
365 * See N2050,
366 * Proposal to Add a Dynamically Sizeable Bitset to the Standard Library.
367 * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2050.pdf
368 *
369 * In the general unoptimized case, storage is allocated in
370 * word-sized blocks. Let B be the number of bits in a word, then
371 * (Nb+(B-1))/B words will be used for storage. B - Nb%B bits are
372 * unused. (They are the high-order bits in the highest word.) It
373 * is a class invariant that those unused bits are always zero.
374 *
375 * If you think of %dynamic_bitset as "a simple array of bits," be
376 * aware that your mental picture is reversed: a %dynamic_bitset
377 * behaves the same way as bits in integers do, with the bit at
378 * index 0 in the "least significant / right-hand" position, and
379 * the bit at index Nb-1 in the "most significant / left-hand"
380 * position. Thus, unlike other containers, a %dynamic_bitset's
381 * index "counts from right to left," to put it very loosely.
382 *
383 * This behavior is preserved when translating to and from strings.
384 * For example, the first line of the following program probably
385 * prints "b('a') is 0001100001" on a modern ASCII system.
386 *
387 * @code
388 * #include <dynamic_bitset>
389 * #include <iostream>
390 * #include <sstream>
391 *
392 * using namespace std;
393 *
394 * int main()
395 * {
396 * long a = 'a';
397 * dynamic_bitset<> b(a);
398 *
399 * cout << "b('a') is " << b << endl;
400 *
401 * ostringstream s;
402 * s << b;
403 * string str = s.str();
404 * cout << "index 3 in the string is " << str[3] << " but\n"
405 * << "index 3 in the bitset is " << b[3] << endl;
406 * }
407 * @endcode
408 *
409 * Most of the actual code isn't contained in %dynamic_bitset<>
410 * itself, but in the base class __dynamic_bitset_base. The base
411 * class works with whole words, not with individual bits. This
412 * allows us to specialize __dynamic_bitset_base for the important
413 * special case where the %dynamic_bitset is only a single word.
414 *
415 * Extra confusion can result due to the fact that the storage for
416 * __dynamic_bitset_base @e is a vector, and is indexed as such. This is
417 * carefully encapsulated.
418 */
419 template<typename _WordT = unsigned long long,
420 typename _Alloc = std::allocator<_WordT>>
422 : private __dynamic_bitset_base<_WordT, _Alloc>
423 {
424 static_assert(std::is_unsigned<_WordT>::value, "template argument "
425 "_WordT not an unsigned integral type");
426
427 public:
428
430 typedef _WordT block_type;
431 typedef _Alloc allocator_type;
432 typedef size_t size_type;
433
434 static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type);
435 // Use this: constexpr size_type std::numeric_limits<size_type>::max().
436 static const size_type npos = static_cast<size_type>(-1);
437
438 private:
439
440 // Clear the unused bits in the uppermost word.
441 void
442 _M_do_sanitize()
443 {
444 size_type __shift = this->_M_Nb % bits_per_block;
445 if (__shift > 0)
446 this->_M_hiword() &= block_type(~(block_type(-1) << __shift));
447 }
448
449 // Set the unused bits in the uppermost word.
450 void
451 _M_do_fill()
452 {
453 size_type __shift = this->_M_Nb % bits_per_block;
454 if (__shift > 0)
455 this->_M_hiword() |= block_type(block_type(-1) << __shift);
456 }
457
458 /**
459 * These versions of single-bit set, reset, flip, and test
460 * do no range checking.
461 */
463 _M_unchecked_set(size_type __pos) noexcept
464 {
465 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
466 return *this;
467 }
468
470 _M_unchecked_set(size_type __pos, int __val) noexcept
471 {
472 if (__val)
473 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
474 else
475 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
476 return *this;
477 }
478
480 _M_unchecked_reset(size_type __pos) noexcept
481 {
482 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
483 return *this;
484 }
485
487 _M_unchecked_flip(size_type __pos) noexcept
488 {
489 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
490 return *this;
491 }
492
493 bool
494 _M_unchecked_test(size_type __pos) const noexcept
495 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
496 != static_cast<_WordT>(0)); }
497
498 size_type _M_Nb = 0;
499
500 public:
501 /**
502 * This encapsulates the concept of a single bit. An instance
503 * of this class is a proxy for an actual bit; this way the
504 * individual bit operations are done as faster word-size
505 * bitwise instructions.
506 *
507 * Most users will never need to use this class directly;
508 * conversions to and from bool are automatic and should be
509 * transparent. Overloaded operators help to preserve the
510 * illusion.
511 *
512 * (On a typical system, this "bit %reference" is 64 times the
513 * size of an actual bit. Ha.)
514 */
516 {
517 friend class dynamic_bitset;
518
519 block_type *_M_wp;
520 size_type _M_bpos;
521
522 public:
523 reference(dynamic_bitset& __b, size_type __pos) noexcept
524 {
525 this->_M_wp = &__b._M_getword(__pos);
526 this->_M_bpos = _Base::_S_whichbit(__pos);
527 }
528
529 // For b[i] = __x;
530 reference&
531 operator=(bool __x) noexcept
532 {
533 if (__x)
534 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
535 else
536 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
537 return *this;
538 }
539
540 // For b[i] = b[__j];
541 reference&
542 operator=(const reference& __j) noexcept
543 {
544 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
545 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
546 else
547 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
548 return *this;
549 }
550
551 // Flips the bit
552 bool
553 operator~() const noexcept
554 { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
555
556 // For __x = b[i];
557 operator bool() const noexcept
558 { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
559
560 // For b[i].flip();
561 reference&
562 flip() noexcept
563 {
564 *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
565 return *this;
566 }
567 };
568
569 friend class reference;
570
571 typedef bool const_reference;
572
573 // 23.3.5.1 constructors:
574
575 /// All bits set to zero.
576 dynamic_bitset() = default;
577
578 /// All bits set to zero.
579 explicit
580 dynamic_bitset(const allocator_type& __alloc)
581 : _Base(__alloc)
582 { }
583
584 /// Initial bits bitwise-copied from a single word (others set to zero).
585 explicit
586 dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL,
587 const allocator_type& __alloc = allocator_type())
588 : _Base(__nbits, __val, __alloc),
589 _M_Nb(__nbits)
590 { }
591
593 const allocator_type& __alloc = allocator_type())
594 : _Base(__alloc)
595 { this->append(__il); }
596
597 /**
598 * @brief Use a subset of a string.
599 * @param __str A string of '0' and '1' characters.
600 * @param __pos Index of the first character in @p __str to use.
601 * @param __n The number of characters to copy.
602 * @param __zero The character to use for unset bits.
603 * @param __one The character to use for set bits.
604 * @param __alloc An allocator.
605 * @throw std::out_of_range If @p __pos is bigger the size of @p __str.
606 * @throw std::invalid_argument If a character appears in the string
607 * which is neither '0' nor '1'.
608 */
609 template<typename _CharT, typename _Traits, typename _Alloc1>
610 explicit
612 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
613 __pos = 0,
614 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
616 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
617 const allocator_type& __alloc = allocator_type())
618 : _Base(__alloc)
619 {
620 if (__pos > __str.size())
621 __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
622 "not valid"));
623
624 // Watch for npos.
625 this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n);
626 this->resize(this->_M_Nb);
627 this->_M_copy_from_string(__str, __pos, __n, __zero, __one);
628 }
629
630 /**
631 * @brief Construct from a string.
632 * @param __str A string of '0' and '1' characters.
633 * @param __alloc An allocator.
634 * @throw std::invalid_argument If a character appears in the string
635 * which is neither '0' nor '1'.
636 */
637 explicit
638 dynamic_bitset(const char* __str,
639 const allocator_type& __alloc = allocator_type())
640 : _Base(__builtin_strlen(__str), 0ULL, __alloc),
641 _M_Nb(__builtin_strlen(__str))
642 {
643 this->_M_copy_from_ptr(__str, _M_Nb, 0, _M_Nb);
644 }
645
646 /// Copy constructor.
648
649 /// Move constructor.
651 : _Base(std::move(__b)), _M_Nb(__b._M_Nb)
652 { __b.clear(); }
653
654 /// Swap with another bitset.
655 void
656 swap(dynamic_bitset& __b) noexcept
657 {
658 this->_M_swap(__b);
659 std::swap(this->_M_Nb, __b._M_Nb);
660 }
661
662 /// Copy assignment operator.
664
665 /// Move assignment operator.
669 {
670 static_cast<_Base&>(*this) = static_cast<_Base&&>(__b);
671 _M_Nb = __b._M_Nb;
672 if _GLIBCXX17_CONSTEXPR (std::is_nothrow_move_assignable<_Base>::value)
673 __b._M_Nb = 0;
674 else if (get_allocator() == __b.get_allocator())
675 __b._M_Nb = 0;
676 return *this;
677 }
678
679 /**
680 * @brief Return the allocator for the bitset.
681 */
682 allocator_type
683 get_allocator() const noexcept
684 { return this->_M_get_allocator(); }
685
686 /**
687 * @brief Resize the bitset.
688 */
689 void
690 resize(size_type __nbits, bool __value = false)
691 {
692 if (__value)
693 this->_M_do_fill();
694 this->_M_resize(__nbits, __value);
695 this->_M_Nb = __nbits;
696 this->_M_do_sanitize();
697 }
698
699 /**
700 * @brief Clear the bitset.
701 */
702 void
704 {
705 this->_M_clear();
706 this->_M_Nb = 0;
707 }
708
709 /**
710 * @brief Push a bit onto the high end of the bitset.
711 */
712 void
713 push_back(bool __bit)
714 {
715 if (this->size() % bits_per_block == 0)
716 this->_M_do_append_block(block_type(__bit), this->_M_Nb);
717 else
718 this->_M_unchecked_set(this->_M_Nb, __bit);
719 ++this->_M_Nb;
720 }
721
722 // XXX why is there no pop_back() member in the proposal?
723
724 /**
725 * @brief Append a block.
726 */
727 void
728 append(block_type __block)
729 {
730 this->_M_do_append_block(__block, this->_M_Nb);
731 this->_M_Nb += bits_per_block;
732 }
733
734 /**
735 * @brief
736 */
737 void
739 { this->append(__il.begin(), __il.end()); }
740
741 /**
742 * @brief Append an iterator range of blocks.
743 */
744 template <typename _BlockInputIterator>
745 void
746 append(_BlockInputIterator __first, _BlockInputIterator __last)
747 {
748 for (; __first != __last; ++__first)
749 this->append(*__first);
750 }
751
752 // 23.3.5.2 dynamic_bitset operations:
753 ///@{
754 /**
755 * @brief Operations on dynamic_bitsets.
756 * @param __rhs A same-sized dynamic_bitset.
757 *
758 * These should be self-explanatory.
759 */
762 {
763 this->_M_do_and(__rhs);
764 return *this;
765 }
766
769 {
770 this->_M_do_and(std::move(__rhs));
771 return *this;
772 }
773
776 {
777 this->_M_do_or(__rhs);
778 return *this;
779 }
780
783 {
784 this->_M_do_xor(__rhs);
785 return *this;
786 }
787
790 {
791 this->_M_do_dif(__rhs);
792 return *this;
793 }
794 ///@}
795
796 ///@{
797 /**
798 * @brief Operations on dynamic_bitsets.
799 * @param __pos The number of places to shift.
800 *
801 * These should be self-explanatory.
802 */
804 operator<<=(size_type __pos)
805 {
806 if (__builtin_expect(__pos < this->_M_Nb, 1))
807 {
808 this->_M_do_left_shift(__pos);
809 this->_M_do_sanitize();
810 }
811 else
812 this->_M_do_reset();
813 return *this;
814 }
815
817 operator>>=(size_type __pos)
818 {
819 if (__builtin_expect(__pos < this->_M_Nb, 1))
820 this->_M_do_right_shift(__pos);
821 else
822 this->_M_do_reset();
823 return *this;
824 }
825 ///@}
826
827 // Set, reset, and flip.
828 /**
829 * @brief Sets every bit to true.
830 */
833 {
834 this->_M_do_set();
835 this->_M_do_sanitize();
836 return *this;
837 }
838
839 /**
840 * @brief Sets a given bit to a particular value.
841 * @param __pos The index of the bit.
842 * @param __val Either true or false, defaults to true.
843 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
844 */
846 set(size_type __pos, bool __val = true)
847 {
848 if (__pos >= _M_Nb)
849 __throw_out_of_range(__N("dynamic_bitset::set"));
850 return this->_M_unchecked_set(__pos, __val);
851 }
852
853 /**
854 * @brief Sets every bit to false.
855 */
858 {
859 this->_M_do_reset();
860 return *this;
861 }
862
863 /**
864 * @brief Sets a given bit to false.
865 * @param __pos The index of the bit.
866 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
867 *
868 * Same as writing @c set(__pos, false).
869 */
871 reset(size_type __pos)
872 {
873 if (__pos >= _M_Nb)
874 __throw_out_of_range(__N("dynamic_bitset::reset"));
875 return this->_M_unchecked_reset(__pos);
876 }
877
878 /**
879 * @brief Toggles every bit to its opposite value.
880 */
883 {
884 this->_M_do_flip();
885 this->_M_do_sanitize();
886 return *this;
887 }
888
889 /**
890 * @brief Toggles a given bit to its opposite value.
891 * @param __pos The index of the bit.
892 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
893 */
895 flip(size_type __pos)
896 {
897 if (__pos >= _M_Nb)
898 __throw_out_of_range(__N("dynamic_bitset::flip"));
899 return this->_M_unchecked_flip(__pos);
900 }
901
902 /// See the no-argument flip().
904 operator~() const
905 { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
906
907 ///@{
908 /**
909 * @brief Array-indexing support.
910 * @param __pos Index into the %dynamic_bitset.
911 * @return A bool for a 'const %dynamic_bitset'. For non-const
912 * bitsets, an instance of the reference proxy class.
913 * @note These operators do no range checking and throw no
914 * exceptions, as required by DR 11 to the standard.
915 */
916 reference
917 operator[](size_type __pos)
918 { return reference(*this,__pos); }
919
920 const_reference
921 operator[](size_type __pos) const
922 { return _M_unchecked_test(__pos); }
923 ///@}
924
925 /**
926 * @brief Returns a numerical interpretation of the %dynamic_bitset.
927 * @return The integral equivalent of the bits.
928 * @throw std::overflow_error If there are too many bits to be
929 * represented in an @c unsigned @c long.
930 */
931 unsigned long
932 to_ulong() const
933 { return this->_M_do_to_ulong(); }
934
935 /**
936 * @brief Returns a numerical interpretation of the %dynamic_bitset.
937 * @return The integral equivalent of the bits.
938 * @throw std::overflow_error If there are too many bits to be
939 * represented in an @c unsigned @c long.
940 */
941 unsigned long long
942 to_ullong() const
943 { return this->_M_do_to_ullong(); }
944
945 /**
946 * @brief Returns a character interpretation of the %dynamic_bitset.
947 * @return The string equivalent of the bits.
948 *
949 * Note the ordering of the bits: decreasing character positions
950 * correspond to increasing bit positions (see the main class notes for
951 * an example).
952 */
953 template<typename _CharT = char,
954 typename _Traits = std::char_traits<_CharT>,
955 typename _Alloc1 = std::allocator<_CharT>>
957 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
958 {
960 _M_copy_to_string(__result, __zero, __one);
961 return __result;
962 }
963
964 // Helper functions for string operations.
965 template<typename _Traits = std::char_traits<char>,
966 typename _CharT = typename _Traits::char_type>
967 void
968 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
969 _CharT __zero = _CharT('0'),
970 _CharT __one = _CharT('1'));
971
972 template<typename _CharT, typename _Traits, typename _Alloc1>
973 void
974 _M_copy_from_string(const basic_string<_CharT, _Traits, _Alloc1>& __str,
975 size_t __pos, size_t __n,
976 _CharT __zero = _CharT('0'),
977 _CharT __one = _CharT('1'))
978 {
979 _M_copy_from_ptr<_Traits>(__str.data(), __str.size(), __pos, __n,
980 __zero, __one);
981 }
982
983 template<typename _CharT, typename _Traits, typename _Alloc1>
984 void
985 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
986 _CharT __zero = _CharT('0'),
987 _CharT __one = _CharT('1')) const;
988
989 /// Returns the number of bits which are set.
990 size_type
991 count() const noexcept
992 { return this->_M_do_count(); }
993
994 /// Returns the total number of bits.
995 size_type
996 size() const noexcept
997 { return this->_M_Nb; }
998
999 /// Returns the total number of blocks.
1000 size_type
1001 num_blocks() const noexcept
1002 { return this->_M_size(); }
1003
1004 /// Returns true if the dynamic_bitset is empty.
1005 _GLIBCXX_NODISCARD bool
1006 empty() const noexcept
1007 { return (this->_M_Nb == 0); }
1008
1009 /// Returns the maximum size of a dynamic_bitset object having the same
1010 /// type as *this.
1011 /// The real answer is max() * bits_per_block but is likely to overflow.
1012 constexpr size_type
1013 max_size() noexcept
1015
1016 /**
1017 * @brief Tests the value of a bit.
1018 * @param __pos The index of a bit.
1019 * @return The value at @a __pos.
1020 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
1021 */
1022 bool
1023 test(size_type __pos) const
1024 {
1025 if (__pos >= _M_Nb)
1026 __throw_out_of_range(__N("dynamic_bitset::test"));
1027 return _M_unchecked_test(__pos);
1028 }
1029
1030 /**
1031 * @brief Tests whether all the bits are on.
1032 * @return True if all the bits are set.
1033 */
1034 bool
1035 all() const
1036 { return this->_M_are_all_aux() == _M_Nb; }
1037
1038 /**
1039 * @brief Tests whether any of the bits are on.
1040 * @return True if at least one bit is set.
1041 */
1042 bool
1043 any() const
1044 { return this->_M_is_any(); }
1045
1046 /**
1047 * @brief Tests whether any of the bits are on.
1048 * @return True if none of the bits are set.
1049 */
1050 bool
1051 none() const
1052 { return !this->_M_is_any(); }
1053
1054 ///@{
1055 /// Self-explanatory.
1057 operator<<(size_type __pos) const
1058 { return dynamic_bitset(*this) <<= __pos; }
1059
1061 operator>>(size_type __pos) const
1062 { return dynamic_bitset(*this) >>= __pos; }
1063 ///@}
1064
1065 /**
1066 * @brief Finds the index of the first "on" bit.
1067 * @return The index of the first bit set, or size() if not found.
1068 * @sa find_next
1069 */
1070 size_type
1072 { return this->_M_do_find_first(this->_M_Nb); }
1073
1074 /**
1075 * @brief Finds the index of the next "on" bit after prev.
1076 * @return The index of the next bit set, or size() if not found.
1077 * @param __prev Where to start searching.
1078 * @sa find_first
1079 */
1080 size_type
1081 find_next(size_t __prev) const
1082 { return this->_M_do_find_next(__prev, this->_M_Nb); }
1083
1084 bool
1085 is_subset_of(const dynamic_bitset& __b) const
1086 { return this->_M_is_subset_of(__b); }
1087
1088 bool
1089 is_proper_subset_of(const dynamic_bitset& __b) const
1090 { return this->_M_is_proper_subset_of(__b); }
1091
1092 friend bool
1093 operator==(const dynamic_bitset& __lhs,
1094 const dynamic_bitset& __rhs) noexcept
1095 { return __lhs._M_Nb == __rhs._M_Nb && __lhs._M_is_equal(__rhs); }
1096
1097 friend bool
1098 operator<(const dynamic_bitset& __lhs,
1099 const dynamic_bitset& __rhs) noexcept
1100 { return __lhs._M_is_less(__rhs) || __lhs._M_Nb < __rhs._M_Nb; }
1101 };
1102
1103 template<typename _WordT, typename _Alloc>
1104 template<typename _CharT, typename _Traits, typename _Alloc1>
1105 inline void
1106 dynamic_bitset<_WordT, _Alloc>::
1107 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
1108 _CharT __zero, _CharT __one) const
1109 {
1110 __str.assign(_M_Nb, __zero);
1111 for (size_t __i = _M_Nb; __i > 0; --__i)
1112 if (_M_unchecked_test(__i - 1))
1113 _Traits::assign(__str[_M_Nb - __i], __one);
1114 }
1115
1116
1117 ///@{
1118 /// These comparisons for equality/inequality are, well, @e bitwise.
1119
1120 template<typename _WordT, typename _Alloc>
1121 inline bool
1122 operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1123 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1124 { return !(__lhs == __rhs); }
1125
1126 template<typename _WordT, typename _Alloc>
1127 inline bool
1129 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1130 { return !(__lhs > __rhs); }
1131
1132 template<typename _WordT, typename _Alloc>
1133 inline bool
1135 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1136 { return __rhs < __lhs; }
1137
1138 template<typename _WordT, typename _Alloc>
1139 inline bool
1141 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1142 { return !(__lhs < __rhs); }
1143 ///@}
1144
1145 // 23.3.5.3 bitset operations:
1146 ///@{
1147 /**
1148 * @brief Global bitwise operations on bitsets.
1149 * @param __x A bitset.
1150 * @param __y A bitset of the same size as @a __x.
1151 * @return A new bitset.
1152 *
1153 * These should be self-explanatory.
1154 */
1155 template<typename _WordT, typename _Alloc>
1156 inline dynamic_bitset<_WordT, _Alloc>
1159 {
1160 dynamic_bitset<_WordT, _Alloc> __result(__x);
1161 __result &= __y;
1162 return __result;
1163 }
1164
1165 template<typename _WordT, typename _Alloc>
1166 inline dynamic_bitset<_WordT, _Alloc>
1169 {
1170 dynamic_bitset<_WordT, _Alloc> __result(__x);
1171 __result |= __y;
1172 return __result;
1173 }
1174
1175 template <typename _WordT, typename _Alloc>
1176 inline dynamic_bitset<_WordT, _Alloc>
1179 {
1180 dynamic_bitset<_WordT, _Alloc> __result(__x);
1181 __result ^= __y;
1182 return __result;
1183 }
1184
1185 template <typename _WordT, typename _Alloc>
1186 inline dynamic_bitset<_WordT, _Alloc>
1189 {
1190 dynamic_bitset<_WordT, _Alloc> __result(__x);
1191 __result -= __y;
1192 return __result;
1193 }
1194 ///@}
1195
1196 /// Stream output operator for dynamic_bitset.
1197 template <typename _CharT, typename _Traits,
1198 typename _WordT, typename _Alloc>
1201 const dynamic_bitset<_WordT, _Alloc>& __x)
1202 {
1204
1205 const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
1206 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
1207 return __os << __tmp;
1208 }
1209 /**
1210 * @}
1211 */
1212} // tr2
1213
1214_GLIBCXX_END_NAMESPACE_VERSION
1215} // std
1216
1217#include <tr2/dynamic_bitset.tcc>
1218
1219#endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:138
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
bool operator>=(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
std::basic_ostream< _CharT, _Traits > & operator<<(std::basic_ostream< _CharT, _Traits > &__os, const dynamic_bitset< _WordT, _Alloc > &__x)
Stream output operator for dynamic_bitset.
bool operator>(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
bool operator<=(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
dynamic_bitset< _WordT, _Alloc > operator-(const dynamic_bitset< _WordT, _Alloc > &__x, const dynamic_bitset< _WordT, _Alloc > &__y)
Global bitwise operations on bitsets.
ISO C++ entities toplevel namespace is std.
constexpr bitset< _Nb > operator^(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
Definition bitset:1582
constexpr bitset< _Nb > operator|(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
Definition bitset:1572
constexpr bitset< _Nb > operator&(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
Definition bitset:1562
initializer_list
Template class basic_ostream.
Definition ostream.h:67
Properties of fundamental types.
Definition limits:320
static constexpr _Tp max() noexcept
Definition limits:328
is_unsigned
Definition type_traits:1001
is_nothrow_move_assignable
Definition type_traits:1331
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:134
Basis for explicit traits specializations.
Managing sequences of characters and character-like objects.
Definition cow_string.h:109
const _CharT * data() const noexcept
Return const pointer to contents.
basic_string & assign(const basic_string &__str)
Set value to contents of another string.
size_type size() const noexcept
Returns the number of characters in the string, not including any null-termination.
Definition cow_string.h:913
locale getloc() const
Locale access.
Definition ios_base.h:841
char_type widen(char __c) const
Widen char to char_type.
Primary class template ctype facet.
A standard container which offers fixed time access to individual elements in any order.
Definition stl_vector.h:456
constexpr void push_back(const value_type &__x)
Add data to the end of the vector.
constexpr iterator end() noexcept
constexpr iterator begin() noexcept
Definition stl_vector.h:997
constexpr void swap(vector &__x) noexcept
Swaps data with another vector.
constexpr void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
constexpr void clear() noexcept
constexpr allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
Definition stl_vector.h:314
constexpr size_type size() const noexcept
std::vector< block_type, allocator_type > _M_w
0 is the least significant word.
The dynamic_bitset class represents a sequence of bits.
size_type find_next(size_t __prev) const
Finds the index of the next "on" bit after prev.
dynamic_bitset & reset()
Sets every bit to false.
dynamic_bitset & operator>>=(size_type __pos)
Operations on dynamic_bitsets.
dynamic_bitset(size_type __nbits, unsigned long long __val=0ULL, const allocator_type &__alloc=allocator_type())
Initial bits bitwise-copied from a single word (others set to zero).
dynamic_bitset(const dynamic_bitset &)=default
Copy constructor.
dynamic_bitset & operator<<=(size_type __pos)
Operations on dynamic_bitsets.
dynamic_bitset(const allocator_type &__alloc)
All bits set to zero.
void append(block_type __block)
Append a block.
unsigned long to_ulong() const
Returns a numerical interpretation of the dynamic_bitset.
dynamic_bitset & set()
Sets every bit to true.
dynamic_bitset & flip(size_type __pos)
Toggles a given bit to its opposite value.
dynamic_bitset & operator=(dynamic_bitset &&__b) noexcept(std::is_nothrow_move_assignable< _Base >::value)
Move assignment operator.
void swap(dynamic_bitset &__b) noexcept
Swap with another bitset.
dynamic_bitset & operator-=(const dynamic_bitset &__rhs)
Operations on dynamic_bitsets.
void push_back(bool __bit)
Push a bit onto the high end of the bitset.
dynamic_bitset()=default
All bits set to zero.
void resize(size_type __nbits, bool __value=false)
Resize the bitset.
dynamic_bitset operator<<(size_type __pos) const
Self-explanatory.
dynamic_bitset(const char *__str, const allocator_type &__alloc=allocator_type())
Construct from a string.
bool none() const
Tests whether any of the bits are on.
allocator_type get_allocator() const noexcept
Return the allocator for the bitset.
constexpr size_type max_size() noexcept
Returns the maximum size of a dynamic_bitset object having the same type as *this....
const_reference operator[](size_type __pos) const
Array-indexing support.
reference operator[](size_type __pos)
Array-indexing support.
dynamic_bitset & operator|=(const dynamic_bitset &__rhs)
Operations on dynamic_bitsets.
dynamic_bitset(const std::basic_string< _CharT, _Traits, _Alloc1 > &__str, typename basic_string< _CharT, _Traits, _Alloc1 >::size_type __pos=0, typename basic_string< _CharT, _Traits, _Alloc1 >::size_type __n=std::basic_string< _CharT, _Traits, _Alloc1 >::npos, _CharT __zero=_CharT('0'), _CharT __one=_CharT('1'), const allocator_type &__alloc=allocator_type())
Use a subset of a string.
size_type num_blocks() const noexcept
Returns the total number of blocks.
dynamic_bitset & operator&=(dynamic_bitset &&__rhs)
Operations on dynamic_bitsets.
dynamic_bitset & operator&=(const dynamic_bitset &__rhs)
Operations on dynamic_bitsets.
size_type find_first() const
Finds the index of the first "on" bit.
size_type count() const noexcept
Returns the number of bits which are set.
size_type size() const noexcept
Returns the total number of bits.
dynamic_bitset(dynamic_bitset &&__b) noexcept
Move constructor.
void append(_BlockInputIterator __first, _BlockInputIterator __last)
Append an iterator range of blocks.
dynamic_bitset & reset(size_type __pos)
Sets a given bit to false.
std::basic_string< _CharT, _Traits, _Alloc1 > to_string(_CharT __zero=_CharT('0'), _CharT __one=_CharT('1')) const
Returns a character interpretation of the dynamic_bitset.
unsigned long long to_ullong() const
Returns a numerical interpretation of the dynamic_bitset.
dynamic_bitset & flip()
Toggles every bit to its opposite value.
bool any() const
Tests whether any of the bits are on.
bool test(size_type __pos) const
Tests the value of a bit.
bool empty() const noexcept
Returns true if the dynamic_bitset is empty.
dynamic_bitset & set(size_type __pos, bool __val=true)
Sets a given bit to a particular value.
dynamic_bitset & operator^=(const dynamic_bitset &__rhs)
Operations on dynamic_bitsets.
dynamic_bitset operator>>(size_type __pos) const
Self-explanatory.
void clear()
Clear the bitset.
dynamic_bitset operator~() const
See the no-argument flip().
dynamic_bitset & operator=(const dynamic_bitset &)=default
Copy assignment operator.
bool all() const
Tests whether all the bits are on.