Quick Links:

bal | bbl | bdl | bsl

Classes | Enumerator | Functions | Friends

Component bslstl_bitset
[Package bslstl]

Provide an STL-compliant bitset class. More...

Classes

struct  bsl::Bitset_ImpUtil
class  bsl::Bitset_ImpBase< BITSETSIZE, 1 >
class  bsl::Bitset_ImpBase< BITSETSIZE, 2 >
class  bsl::bitset< N >
class  bsl::bitset< N >::reference

Functions

static void bsl::Bitset_ImpUtil::defaultInit (unsigned int *data, size_t size, unsigned long val=0)
BSLS_KEYWORD_CONSTEXPR bsl::Bitset_ImpBase< BITSETSIZE, 1 >::Bitset_ImpBase ()
BSLS_KEYWORD_CONSTEXPR bsl::Bitset_ImpBase< BITSETSIZE, 1 >::Bitset_ImpBase (unsigned long val)
BSLS_KEYWORD_CONSTEXPR bsl::Bitset_ImpBase< BITSETSIZE, 2 >::Bitset_ImpBase ()
BSLS_KEYWORD_CONSTEXPR bsl::Bitset_ImpBase< BITSETSIZE, 2 >::Bitset_ImpBase (unsigned long)
reference & bsl::bitset::reference::operator= (bool x) BSLS_KEYWORD_NOEXCEPT
reference & bsl::bitset::reference::operator= (const reference &x) BSLS_KEYWORD_NOEXCEPT
reference & bsl::bitset::reference::flip () BSLS_KEYWORD_NOEXCEPT
 bsl::bitset::reference::operator bool () const BSLS_KEYWORD_NOEXCEPT
bool bsl::bitset::reference::operator~ () const BSLS_KEYWORD_NOEXCEPT
BSLS_KEYWORD_CONSTEXPR bsl::bitset::bitset () BSLS_KEYWORD_NOEXCEPT
BSLS_KEYWORD_CONSTEXPR bsl::bitset::bitset (unsigned long val) BSLS_KEYWORD_NOEXCEPT
template<class CHAR_TYPE , class TRAITS , class ALLOCATOR >
 bsl::bitset::bitset (const std::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR > &str, typename std::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR >::size_type pos=0, typename std::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR >::size_type n=std::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR >::npos, CHAR_TYPE zeroChar=CHAR_TYPE('0'), CHAR_TYPE oneChar=CHAR_TYPE('1'))
template<class CHAR_TYPE , class TRAITS , class ALLOCATOR >
 bsl::bitset::bitset (const bsl::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR > &str, typename bsl::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR >::size_type pos=0, typename bsl::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR >::size_type n=bsl::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR >::npos, CHAR_TYPE zeroChar=CHAR_TYPE('0'), CHAR_TYPE oneChar=CHAR_TYPE('1'))
bitset & bsl::bitset::operator&= (const bitset &rhs) BSLS_KEYWORD_NOEXCEPT
bitset & bsl::bitset::operator|= (const bitset &rhs) BSLS_KEYWORD_NOEXCEPT
bitset & bsl::bitset::operator^= (const bitset &rhs) BSLS_KEYWORD_NOEXCEPT
bitset & bsl::bitset::operator<<= (std::size_t pos) BSLS_KEYWORD_NOEXCEPT
bitset & bsl::bitset::operator>>= (std::size_t pos) BSLS_KEYWORD_NOEXCEPT
bitset & bsl::bitset::flip () BSLS_KEYWORD_NOEXCEPT
bitset & bsl::bitset::flip (std::size_t pos)
bitset & bsl::bitset::reset () BSLS_KEYWORD_NOEXCEPT
bitset & bsl::bitset::reset (std::size_t pos)
bitset & bsl::bitset::set () BSLS_KEYWORD_NOEXCEPT
bitset & bsl::bitset::set (std::size_t pos, int val=true)
reference bsl::bitset::operator[] (std::size_t pos)
bitset bsl::bitset::operator<< (std::size_t pos) const BSLS_KEYWORD_NOEXCEPT
bitset bsl::bitset::operator>> (std::size_t pos) const BSLS_KEYWORD_NOEXCEPT
bitset bsl::bitset::operator~ () const BSLS_KEYWORD_NOEXCEPT
BSLS_KEYWORD_CONSTEXPR bool bsl::bitset::operator[] (std::size_t pos) const
bool bsl::bitset::operator== (const bitset &rhs) const BSLS_KEYWORD_NOEXCEPT
bool bsl::bitset::operator!= (const bitset &rhs) const BSLS_KEYWORD_NOEXCEPT
bool bsl::bitset::all () const BSLS_KEYWORD_NOEXCEPT
bool bsl::bitset::any () const BSLS_KEYWORD_NOEXCEPT
bool bsl::bitset::none () const BSLS_KEYWORD_NOEXCEPT
std::size_t bsl::bitset::count () const BSLS_KEYWORD_NOEXCEPT
BSLS_KEYWORD_CONSTEXPR std::size_t bsl::bitset::size () const BSLS_KEYWORD_NOEXCEPT
bool bsl::bitset::test (size_t pos) const
template<class CHAR_TYPE , class TRAITS , class ALLOCATOR >
basic_string< CHAR_TYPE,
TRAITS, ALLOCATOR > 
bsl::bitset::to_string (CHAR_TYPE zero=CHAR_TYPE('0'), CHAR_TYPE one=CHAR_TYPE('1')) const
unsigned long bsl::bitset::to_ulong () const
template<std::size_t N>
bitset< N > bsl::operator& (const bitset< N > &lhs, const bitset< N > &rhs) BSLS_KEYWORD_NOEXCEPT
template<std::size_t N>
bitset< N > bsl::operator| (const bitset< N > &lhs, const bitset< N > &rhs) BSLS_KEYWORD_NOEXCEPT
template<std::size_t N>
bitset< N > bsl::operator^ (const bitset< N > &lhs, const bitset< N > &rhs) BSLS_KEYWORD_NOEXCEPT
template<class CHAR_TYPE , class TRAITS , std::size_t N>
std::basic_istream< CHAR_TYPE,
TRAITS > & 
bsl::operator>> (std::basic_istream< CHAR_TYPE, TRAITS > &is, bitset< N > &x)
template<class CHAR_TYPE , class TRAITS , std::size_t N>
std::basic_ostream< CHAR_TYPE,
TRAITS > & 
bsl::operator<< (std::basic_ostream< CHAR_TYPE, TRAITS > &os, const bitset< N > &x)

Friends

class bsl::bitset::reference

Detailed Description

Outline
Purpose:
Provide an STL-compliant bitset class.
Classes:
bsl::bitset STL-compatible bitset template
Canonical Header:
bsl_bitset.h
See also:
package bos+stdhdrs in the bos package group
Description:
This component is for internal use only. Please include <bsl_bitset.h> instead and use bsl::bitset directly. This component implements a static bitset class that is suitable for use as an implementation of the std::bitset class template.
Usage:
This section illustrates intended use of this component.
Example 1: Determining if a Number is Prime (Sieve of Eratosthenes):
Suppose we want to write a function to determine whether or not a given number is prime. One way to implement this function is by using what's called the Sieve of Eratosthenes. The basic idea of this algorithm is to repeatedly walk the sequence of integer values and mark any numbers up to and including the particular value of interest that are integer multiples of first 2, then 3, then 5, etc. (skipping 4 because it was previously marked when we walked the sequence by 2's). Once we have walked the sequence with all primes up to and including the square root of the number of interest, we check to see if that number has been marked: If it has, it's composite; otherwise it's prime.
When implementing this classic algorithm, we need an efficient way of representing a flag for each potential prime number. The following illustrates how we can use bsl::bitset to accomplish this result, provided we know an upper bound on supplied candidate values at compile time.
First, we begin to define a function template that will determine whether or not a given candidate value is prime:
  template <unsigned int MAX_VALUE>
  bool isPrime(int candidate)
      // Return 'true' if the specified 'candidate' value is a prime number,
      // and 'false' otherwise.  The behavior is undefined unless
      // '2 <= candidate <= MAX_VALUE'
  {
      BSLMF_ASSERT(2 <= MAX_VALUE);
      BSLS_ASSERT(2 <= candidate); BSLS_ASSERT(candidate <= MAX_VALUE);
Then, we declare a bsl::bitset, compositeFlags, that will contain flags indicating whether a value corresponding to a given index is known to be composite (true) or is still potentially prime (false) up to and including the compile-time constant template parameter, MAX_VALUE.
      // Candidate primes in the '[2 .. MAX_VALUE]' range.

      bsl::bitset<MAX_VALUE + 1> compositeFlags;
Next, we observe that a default-constructed bsl::bitset has no flags set, We can check this by asserting that the none method returns true, by asserting that the any method returns false, or by asserting that the count of set bits is 0:
      assert(true  == compositeFlags.none());
      assert(false == compositeFlags.any());
      assert(0     == compositeFlags.count());
Then, we note that a bsl::bitset has a fixed size (the set can't be grown or shrunk) and verify that size is the same as the template argument used to create the bsl::bitset:
      assert(MAX_VALUE + 1 == compositeFlags.size());
Next, we compute sqrt(candidate), which is as far as we need to look:
      // We need to cast the 'sqrt' argument to avoid an overload ambiguity.
      const int sqrtOfCandidate = std::sqrt(static_cast<double>(candidate))
                                + 0.01;  // fudge factor
Now, we loop from 2 to sqrtOfCandidate, and use the sieve algorithm to eliminate non-primes:
      // Note that we treat 'false' values as potential primes,
      // since that is how 'bsl::bitset' is default-initialized.

      for (std::size_t i = 2; i <= sqrtOfCandidate; ++i) {
          if (compositeFlags[i]) {
              continue; // Skip this value: it's flagged as composite, so all
                        // of its multiples are already flagged as composite
                        // as well.
          }

          for (std::size_t flagValue = i;
               flagValue <= candidate;
               flagValue += i) {
              compositeFlags[flagValue] = true;
          }

          if (true == compositeFlags[candidate]) {
              return false;                                         // RETURN
          }
      }

      BSLS_ASSERT(false == compositeFlags[candidate]);

      return true;
  }
Notice that if we don't return false from the loop, none of the lower numbers evenly divided the candidate value; hence, it is a prime number.
Finally, we can exercise our isPrime function with an upper bound of 10,000:
  enum { UPPER_BOUND = 10000 };

  assert(1 == isPrime<UPPER_BOUND>(2));
  assert(1 == isPrime<UPPER_BOUND>(3));
  assert(0 == isPrime<UPPER_BOUND>(4));
  assert(1 == isPrime<UPPER_BOUND>(5));
  assert(0 == isPrime<UPPER_BOUND>(6));
  assert(1 == isPrime<UPPER_BOUND>(7));
  assert(0 == isPrime<UPPER_BOUND>(8));
  assert(0 == isPrime<UPPER_BOUND>(9));
  assert(0 == isPrime<UPPER_BOUND>(10));
  // ...
  assert(1 == isPrime<UPPER_BOUND>(9973));
  assert(0 == isPrime<UPPER_BOUND>(9975));
  assert(0 == isPrime<UPPER_BOUND>(10000));

Function Documentation

static void bsl::Bitset_ImpUtil::defaultInit ( unsigned int *  data,
size_t  size,
unsigned long  val = 0 
) [static, inherited]

Initialize the memory at the address specified by data so that the the first M bit positions correspond to the bit values in the specified val where M is the smaller of size * k_BITS_PER_INT and CHAR_BIT * sizeof(unsigned long). The remaining bits are initialized to zero 0.

template<std::size_t BITSETSIZE>
BSLS_KEYWORD_CONSTEXPR bsl::Bitset_ImpBase< BITSETSIZE, 1 >::Bitset_ImpBase (  )  [inherited]

Create a Bitset_ImpBase with each bit in d_data initialized to zero. In C++11 this constructor can be used in a constant expression.

template<std::size_t BITSETSIZE>
BSLS_KEYWORD_CONSTEXPR bsl::Bitset_ImpBase< BITSETSIZE, 1 >::Bitset_ImpBase ( unsigned long  val  )  [inherited]

Create a Bitset_ImpBase with the first N bit positions of d_data corresponding to the first N bit positions of the specified val after conversion to unsigned int and the remaining bits in d_data initialized to zero, where N is CHAR_BIT * sizeof(int). The behavior is undefined unless BITSETSIZE == 1 or sizeof(long) / sizeof(int) == 1. In C++11 this constructor can be used in a constant expression.

template<std::size_t BITSETSIZE>
BSLS_KEYWORD_CONSTEXPR bsl::Bitset_ImpBase< BITSETSIZE, 2 >::Bitset_ImpBase (  )  [inherited]

Create a Bitset_ImpBase with each bit in d_data initialized to zero. In C++11 this constructor can be used in a constant expression.

template<std::size_t BITSETSIZE>
BSLS_KEYWORD_CONSTEXPR bsl::Bitset_ImpBase< BITSETSIZE, 2 >::Bitset_ImpBase ( unsigned  long  )  [inherited]

Create a Bitset_ImpBase with the first N bit positions of d_data corresponding to the first N bit positions of the specified val after conversion to unsigned int and the remaining bits in d_data initialized to zero, where N is CHAR_BIT * sizeof(int) * 2. The behavior is undefined unless sizeof(long) / sizeof(int) == 2. In C++11 this constructor can be used in a constant expression.

template<std::size_t N>
reference& bsl::bitset< N >::reference::operator= ( bool  x  )  [inherited]

Assign to the bit referenced by this object the specified value x and return a reference offering modifiable access to this object.

template<std::size_t N>
reference& bsl::bitset< N >::reference::operator= ( const reference x  )  [inherited]

Assign this object to refer to the same bit as the specified x and return a reference offering modifiable access to this object.

template<std::size_t N>
reference& bsl::bitset< N >::reference::flip (  )  [inherited]

Invert the value of the bit referenced by this object and return a reference offering modifiable access to this object.

template<std::size_t N>
bsl::bitset< N >::reference::operator bool (  )  const [inherited]

Return the value of the bit referenced by this object.

template<std::size_t N>
bool bsl::bitset< N >::reference::operator~ (  )  const [inherited]

Return the inverted value of the bit referenced by this object. Note that the value of the referenced bit remains unchanged.

template<std::size_t N>
BSLS_KEYWORD_CONSTEXPR bsl::bitset< N >::bitset (  )  [inherited]

Create a bitset with all bits initialized to 0.

template<std::size_t N>
BSLS_KEYWORD_CONSTEXPR bsl::bitset< N >::bitset ( unsigned long  val  )  [inherited]

IMPLICIT: Create a bitset with its first M bit positions correspond to bit values in the specified val. M is the smaller of the parameterized N and 8 * sizeof(unsigned long). If M < N, the remaining bit positions are initialized to 0.

template<std::size_t N>
template<class CHAR_TYPE , class TRAITS , class ALLOCATOR >
bsl::bitset< N >::bitset ( const std::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR > &  str,
typename std::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR >::size_type  pos = 0,
typename std::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR >::size_type  n = std::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR >::npos,
CHAR_TYPE  zeroChar = CHAR_TYPE('0'),
CHAR_TYPE  oneChar = CHAR_TYPE('1') 
) [explicit, inherited]

Create a bitset with its first M bit positions corresponding to the characters in the specified pos of the specified str. M is the smaller of the parameterized N and str.length(). If M < N, the remaining bit positions are initialized to 0. Characters with the value zeroChar correspond to an unset bit and characters with the value oneChar correspond to a set bit. The behavior is undefined if any characters in str is neither the specified zeroChar nor the specified oneChar.

template<std::size_t N>
template<class CHAR_TYPE , class TRAITS , class ALLOCATOR >
bsl::bitset< N >::bitset ( const bsl::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR > &  str,
typename bsl::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR >::size_type  pos = 0,
typename bsl::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR >::size_type  n = bsl::basic_string< CHAR_TYPE, TRAITS, ALLOCATOR >::npos,
CHAR_TYPE  zeroChar = CHAR_TYPE('0'),
CHAR_TYPE  oneChar = CHAR_TYPE('1') 
) [explicit, inherited]

Create a bitset with its first M bit positions corresponding to 0 the characters in the specified pos of the specified str. M is the smaller of the parameterized N and str.length(). If M < N, the remaining bit positions are initialized to 0. Characters with the value zeroChar correspond to an unset bit and characters with the value oneChar correspond to a set bit. The behavior is undefined if the characters in the specified str is not the specified zeroChar and not the specified oneChar

template<std::size_t N>
bitset& bsl::bitset< N >::operator&= ( const bitset< N > &  rhs  )  [inherited]

Clear each bit of this bitset for each corresponding bit that is 0 in the specified rhs, and leaves all other bits unchanged. Return a reference to this modifiable bitset. Note that this is equivalent to a bitwise OR.

template<std::size_t N>
bitset& bsl::bitset< N >::operator|= ( const bitset< N > &  rhs  )  [inherited]

Set each bit of this bitset for each corresponding bit that is 1 in the specified rhs, and leaves all other bits unchanged. Return a reference to this modifiable bitset. Note that this is equivalent to a bitwise AND.

template<std::size_t N>
bitset& bsl::bitset< N >::operator^= ( const bitset< N > &  rhs  )  [inherited]

Toggle each bit of this bitset for each corresponding bit that is 1 in the specified rhs, and leaves all other bits unchanged. Return a reference to this modifiable bitset. Note that this is equivalent to a bitwise XOR.

template<std::size_t N>
bitset& bsl::bitset< N >::operator<<= ( std::size_t  pos  )  [inherited]

Shift the bits of this bitset left (towards the most significant bit) by the specified pos and return a reference to this modifiable bitset. For all bits with position I where I <= pos, the new value is 0. The behavior is undefined unless pos <= N.

template<std::size_t N>
bitset& bsl::bitset< N >::operator>>= ( std::size_t  pos  )  [inherited]

Shift the bits of this bitset right (towards the least significant bit) by the specified pos and return a reference to this modifiable bitset. For all bits with position I where I > N - pos, the new value is 0. The behavior is undefined unless pos <= N.

template<std::size_t N>
bitset& bsl::bitset< N >::flip (  )  [inherited]

Toggle all bits of this bitset and return a reference to this modifiable bitset.

template<std::size_t N>
bitset& bsl::bitset< N >::flip ( std::size_t  pos  )  [inherited]

Toggle the bit at the specified pos of this bitset and return a reference to this modifiable bitset.

template<std::size_t N>
bitset& bsl::bitset< N >::reset (  )  [inherited]

Set all bits of this bitset to 0 and return a reference to this modifiable bitset.

template<std::size_t N>
bitset& bsl::bitset< N >::reset ( std::size_t  pos  )  [inherited]

Set the bit at the specified pos of this bitset to 0 and return a reference to this modifiable bitset.

template<std::size_t N>
bitset& bsl::bitset< N >::set (  )  [inherited]

Set all bits of this bitset to 1 and return a reference to this modifiable bitset.

template<std::size_t N>
bitset& bsl::bitset< N >::set ( std::size_t  pos,
int  val = true 
) [inherited]

Set the bit at the specified pos of this bitset to 1 and return a reference to this modifiable bitset. Optionally specify val as the value to set the bit. If val is non-zero, the bit is set to 1, otherwise the bit is set to 0.

template<std::size_t N>
reference bsl::bitset< N >::operator[] ( std::size_t  pos  )  [inherited]

Return a reference to the modifiable bit position at the specified pos.

template<std::size_t N>
bitset bsl::bitset< N >::operator<< ( std::size_t  pos  )  const [inherited]

Return a bitset constructed from shifting this bitset left by the specified pos.

template<std::size_t N>
bitset bsl::bitset< N >::operator>> ( std::size_t  pos  )  const [inherited]

Return a bitset constructed from shifting this bitset right by the specified pos.

template<std::size_t N>
bitset bsl::bitset< N >::operator~ (  )  const [inherited]

Toggle all bits of this bitset and return a reference to this modifiable bitset.

template<std::size_t N>
BSLS_KEYWORD_CONSTEXPR bool bsl::bitset< N >::operator[] ( std::size_t  pos  )  const [inherited]

Return the value of the bit position at the specified pos.

template<std::size_t N>
bool bsl::bitset< N >::operator== ( const bitset< N > &  rhs  )  const [inherited]

Return true if the specified rhs has the same value as this bitset and false otherwise. Two bitsets have the same value when the sequence and value of bits they hold are the same.

template<std::size_t N>
bool bsl::bitset< N >::operator!= ( const bitset< N > &  rhs  )  const [inherited]

Return true if the specified rhs do not have the same value as this bitset and false otherwise. Two bitset do not have the same value when either the sequence or the value of bits they hold are not the same.

template<std::size_t N>
bool bsl::bitset< N >::all (  )  const [inherited]

Return true if all of the bits in this bitset have the value of 1 and false otherwise. Note that all() and none() are both true for bitsets of size 0.

template<std::size_t N>
bool bsl::bitset< N >::any (  )  const [inherited]

Return true if one or more of the bits in this bitset has the value of 1 and false otherwise.

template<std::size_t N>
bool bsl::bitset< N >::none (  )  const [inherited]

Return true if all the bits in this bitset has the value of 0 and false otherwise. Note that all() and none() are both true for bitsets of size 0.

template<std::size_t N>
std::size_t bsl::bitset< N >::count (  )  const [inherited]

Return the number of bits in this bitset that have the value of 1.

template<std::size_t N>
BSLS_KEYWORD_CONSTEXPR std::size_t bsl::bitset< N >::size (  )  const [inherited]

Return the number of bits this bitset holds.

template<std::size_t N>
bool bsl::bitset< N >::test ( size_t  pos  )  const [inherited]

Return true if the bit at the specified pos has the value of 1 and false otherwise.

template<std::size_t N>
template<class CHAR_TYPE , class TRAITS , class ALLOCATOR >
basic_string<CHAR_TYPE, TRAITS, ALLOCATOR> bsl::bitset< N >::to_string ( CHAR_TYPE  zero = CHAR_TYPE('0'),
CHAR_TYPE  one = CHAR_TYPE('1') 
) const [inherited]

Return a basic_string representation of this bitset, where the zero-bits are represented by the specified zero character and the one-bits are represented by the specified one character. The most-significant bit is placed at the beginning of the string, and the least-significant bit is placed at the end of the string.

template<std::size_t N>
unsigned long bsl::bitset< N >::to_ulong (  )  const [inherited]

Return an unsigned long value that has the same bit value as the bitset. Note that the behavior is undefined if the bitset cannot be represented as an unsigned long.

template<std::size_t N>
bitset<N> bsl::operator& ( const bitset< N > &  lhs,
const bitset< N > &  rhs 
)

Return a bitset that results from a bitwise AND of the specified lhs and rhs.

template<std::size_t N>
bitset<N> bsl::operator| ( const bitset< N > &  lhs,
const bitset< N > &  rhs 
)

Return a bitset that results from a bitwise OR of the specified lhs and rhs.

template<std::size_t N>
bitset<N> bsl::operator^ ( const bitset< N > &  lhs,
const bitset< N > &  rhs 
)

Return a bitset that results from a bitwise XOR of the specified lhs and rhs.

template<class CHAR_TYPE , class TRAITS , std::size_t N>
std::basic_istream<CHAR_TYPE, TRAITS>& bsl::operator>> ( std::basic_istream< CHAR_TYPE, TRAITS > &  is,
bitset< N > &  x 
)
template<class CHAR_TYPE , class TRAITS , std::size_t N>
std::basic_ostream<CHAR_TYPE, TRAITS>& bsl::operator<< ( std::basic_ostream< CHAR_TYPE, TRAITS > &  os,
const bitset< N > &  x 
)

Friends

template<std::size_t N>
friend class reference [friend, inherited]