Quick Links:

bal | bbl | bdl | bsl

Namespaces

Component bdlc_bitarray
[Package bdlc]

Provide a space-efficient, sequential container of boolean values. More...

Namespaces

namespace  bdlc

Detailed Description

Outline
Purpose:
Provide a space-efficient, sequential container of boolean values.
Classes:
bdlc::BitArray vector-like, sequential container of boolean values
Description:
This component implements bdlc::BitArray, an efficient value-semantic, sequential container of boolean values (i.e., 0 or 1) of type bool. A BitArray may be thought of as an arbitrary-precision unsigned int. This metaphor is used to motivate the rich set of "bitwise" operations on BitArray objects provided by this component, as well as the notion of "zero extension" of a (shorter) bit array during binary operations on bit arrays having lengths that are not the same.
Bit-Array-Specific Functionality:
In addition to many typical vector-like container methods, this component supports "boolean" functionality unique to BitArray. However, unlike other standard container types such as bsl::bitset, there is no operator[](bsl::size_t index) that returns a reference to a (modifiable) boolean element at the specified index position. This difference is due to the densely-packed internal representation of bits within bit arrays: 
  bdlc::BitArray mA(128);
  assert(0 == mA[13]);             // Ok
  mA[13] = 'false';                // Error -- 'mA[13]' is not an lvalue.
  mA.assign(13, 1);                // Ok

  const bdlc::BitArray& A = mA;    // Ok
  assert(1 == A[13]);              // Ok
  const bool *bp  = &A[13]         // Error -- 'A[13]' is not an lvalue.
  const bool  bit = A[13];         // Ok
Also note that there is no data method returning a contiguous sequence of bool.
Finally note that, wherever an argument of non-boolean type -- e.g., the literal 5 (of type int) -- is used in a BitArray method to specify a boolean (bit) value, every non-zero value is automatically converted (via a standard conversion) to a bool value true, before the method of the BitArray is invoked: 
  bdlc::BitArray a(10);
  assert(0 == a[5]);
  a.assign(5, 24);            // Ok -- non-boolean value converted to 'true'.
  assert(1 == a[5]);
Performance and Exception-Safety Guarantees:
The asymptotic worst-case performance of representative operations is characterized using big-O notation, O[f(N,M)], where N and M refer to the number of respective bits (i.e., length) of arrays X and Y, respectively. Here, Amortized Case complexity, denoted by A[f(N)], is defined as the average of N successive invocations, as N gets very large. 
                                        Average   Exception-Safety
  Operation                Worst Case    Case        Guarantee
  ---------                ----------   -------   ----------------
  DEFAULT CTOR             O[1]                   No-Throw
  COPY CTOR(Y)             O[M]                   Exception Safe

  X.DTOR()                 O[1]                   No-Throw

  X.OP=(Y)                 O[M]                   Basic <*>
  X.insert(index, value)   O[N]                   Basic <*>

  X.reserveCapacity(M)     O[N]                   Strong <*>
  X.append(value)          O[N]         A[1]      Strong <*>

  X.assign(index, value)   O[1]                   No-Throw
  X.assign1(value)         O[1]                   No-Throw
  X.assign0(value)         O[1]                   No-Throw

  X.remove(index)          O[N]                   No-Throw
  X.assignAll0()           O[N]                   No-Throw
  X.assignAll1()           O[N]                   No-Throw

  X.length()               O[1]                   No-Throw
  X.OP[](index)            O[1]                   No-Throw

  X.isAny1                 O[N]                   No-Throw
  X.isAny0                 O[N]                   No-Throw

  other 'const' methods    O[1] .. O[N]           No-Throw

  OP==(X, Y)               O[min(N, M)]           No-Throw
  OP!=(X, Y)               O[min(N, M)]           No-Throw

                <*> No-Throw guarantee when capacity is sufficient.
Note that all of the non-creator methods of BitArray provide the No-Throw guarantee whenever sufficient capacity is already available.
Usage:
This section illustrates the intended use of this component.
Example 1: Creating a NullableVector Class:
An efficient implementation of an arbitrary precision bit sequence container has myriad applications. For example, a bdlc::BitArray can be used effectively as a parallel array of flags indicating some special property, such as isNull, isBusinessDay, etc.; its use is especially indicated when (1) the number of elements of the primary array can grow large, and (2) the individual elements do not have the capacity or capability to store the information directly.
As a simple example, we'll implement a (heavily elided) value-semantic template class, NullableVector<TYPE>, that behaves like a bsl::vector<TYPE> but additionally allows storing a nullness flag to signify that the corresponding element was not specified. Elements added to a NullableVector are null by default, although there are manipulator functions that allow appending a non-null element. Each null element stores the default value for TYPE.
Note that this class has a minimal interface (suitable for illustration purpose only) that allows users to either append a (non-null) TYPE value or a null value. A real NullableVector class would support a complete set of value semantic operations, including copy construction, assignment, equality comparison, ostream printing, and BDEX serialization. Also note that, for simplicity, exception-neutrality is ignored (some methods are clearly not exception-neutral).
First, we define the interface of NullableVector: 
  template <class TYPE>
  class NullableVector {
      // This class implements a sequential container of elements of the
      // template parameter 'TYPE'.

      // DATA
      bsl::vector<TYPE>  d_values;       // data elements
      bdlc::BitArray     d_nullFlags;    // 'true' indicates i'th element is
                                         // null

    private:
      // NOT IMPLEMENTED
      NullableVector(const NullableVector&);
      NullableVector& operator=(const NullableVector&);

    public:
      // TRAITS
      BSLMF_NESTED_TRAIT_DECLARATION(NullableVector,
                                     bslma::UsesBslmaAllocator);

    public:
      // CREATORS
      explicit
      NullableVector(bsl::size_t       initialLength,
                     bslma::Allocator *basicAllocator = 0);
          // Construct a vector having the specified 'initialLength' null
          // elements.  Optionally specify a 'basicAllocator' used to supply
          // memory.  If 'basicAllocator' is 0, the currently supplied
          // default allocator is used.

      // ...

      ~NullableVector();
          // Destroy this vector.

      // MANIPULATORS
      void appendNullElement();
          // Append a null element to this vector.  Note that the appended
          // element will have the same value as a default constructed 'TYPE'
          // object.

      void appendElement(const TYPE& value);
          // Append an element having the specified 'value' to the end of
          // this vector.

      void makeNonNull(bsl::size_t index);
          // Make the element at the specified 'index' in this vector
          // non-null.  The behavior is undefined unless 'index < length()'.

      void makeNull(bsl::size_t index);
          // Make the element at the specified 'index' in this vector null.
          // The behavior is undefined unless 'index < length()'.  Note that
          // the new value of the element will be the default constructed
          // value for 'TYPE'.

      TYPE& modifiableElement(bsl::size_t index);
          // Return a reference providing modifiable access to the (valid)
          // element at the specified 'index' in this vector.  The behavior
          // is undefined unless 'index < length()'.  Note that if the
          // element at 'index' is null then the nullness flag is reset and
          // the returned value is the default constructed value for 'TYPE'.

      void removeElement(bsl::size_t index);
          // Remove the element at the specified 'index' in this vector.  The
          // behavior is undefined unless 'index < length()'.

      // ACCESSORS
      const TYPE& constElement(bsl::size_t index) const;
          // Return a reference providing non-modifiable access to the
          // element at the specified 'index' in this vector.  The behavior
          // is undefined unless 'index < length()'.  Note that if the
          // element at 'index' is null then the nullness flag is not reset
          // and the returned value is the default constructed value for
          // 'TYPE'.

      bool isAnyElementNonNull() const;
          // Return 'true' if any element in this vector is non-null, and
          // 'false' otherwise.

      bool isAnyElementNull() const;
          // Return 'true' if any element in this vector is null, and 'false'
          // otherwise.

      bool isElementNull(bsl::size_t index) const;
          // Return 'true' if the element at the specified 'index' in this
          // vector is null, and 'false' otherwise.  The behavior is
          // undefined unless 'index < length()'.

      bsl::size_t length() const;
          // Return the number of elements in this vector.

      bsl::size_t numNullElements() const;
          // Return the number of null elements in this vector.
  };
Then, we implement, in turn, each of the methods declared above: 
                   // --------------------
                   // class NullableVector
                   // --------------------

  // CREATORS
  template <class TYPE>
  NullableVector<TYPE>::NullableVector(bsl::size_t       initialLength,
                                       bslma::Allocator *basicAllocator)
  : d_values(initialLength, TYPE(), basicAllocator)
  , d_nullFlags(initialLength, true, basicAllocator)
  {
  }

  template <class TYPE>
  NullableVector<TYPE>::~NullableVector()
  {
      BSLS_ASSERT(d_values.size() == d_nullFlags.length());
  }

  // MANIPULATORS
  template <class TYPE>
  inline
  void NullableVector<TYPE>::appendElement(const TYPE& value)
  {
      d_values.push_back(value);
      d_nullFlags.append(false);
  }

  template <class TYPE>
  inline
  void NullableVector<TYPE>::appendNullElement()
  {
      d_values.push_back(TYPE());
      d_nullFlags.append(true);
  }

  template <class TYPE>
  inline
  void NullableVector<TYPE>::makeNonNull(bsl::size_t index)
  {
      BSLS_ASSERT_SAFE(index < length());

      d_nullFlags.assign(index, false);
  }

  template <class TYPE>
  inline
  void NullableVector<TYPE>::makeNull(bsl::size_t index)
  {
      BSLS_ASSERT_SAFE(index < length());

      d_values[index] = TYPE();
      d_nullFlags.assign(index, true);
  }

  template <class TYPE>
  inline
  TYPE& NullableVector<TYPE>::modifiableElement(bsl::size_t index)
  {
      BSLS_ASSERT_SAFE(index < length());

      d_nullFlags.assign(index, false);
      return d_values[index];
  }

  template <class TYPE>
  inline
  void NullableVector<TYPE>::removeElement(bsl::size_t index)
  {
      BSLS_ASSERT_SAFE(index < length());

      d_values.erase(d_values.begin() + index);
      d_nullFlags.remove(index);
  }

  // ACCESSORS
  template <class TYPE>
  inline
  const TYPE& NullableVector<TYPE>::constElement(bsl::size_t index) const
  {
      BSLS_ASSERT_SAFE(index < length());

      return d_values[index];
  }

  template <class TYPE>
  inline
  bool NullableVector<TYPE>::isAnyElementNonNull() const
  {
      return d_nullFlags.isAny0();
  }

  template <class TYPE>
  inline
  bool NullableVector<TYPE>::isAnyElementNull() const
  {
      return d_nullFlags.isAny1();
  }

  template <class TYPE>
  inline
  bool NullableVector<TYPE>::isElementNull(bsl::size_t index) const
  {
      BSLS_ASSERT_SAFE(index < length());

      return d_nullFlags[index];
  }

  template <class TYPE>
  inline
  bsl::size_t NullableVector<TYPE>::length() const
  {
      return d_values.size();
  }

  template <class TYPE>
  inline
  bsl::size_t NullableVector<TYPE>::numNullElements() const
  {
      return d_nullFlags.num1();
  }
Next, we create an empty NullableVector: 
  NullableVector<int>        array(0);
  const NullableVector<int>& ARRAY       = array;
  const int                  DEFAULT_INT = 0;

  assert(0       == ARRAY.length());
  assert(0       == ARRAY.numNullElements());
  assert(false   == ARRAY.isAnyElementNonNull());
  assert(false   == ARRAY.isAnyElementNull());
Then, we append a non-null element to it: 
  array.appendElement(5);
  assert(1       == ARRAY.length());
  assert(5       == ARRAY.constElement(0));
  assert(false   == ARRAY.isElementNull(0));
  assert(0       == ARRAY.numNullElements());
  assert(true    == ARRAY.isAnyElementNonNull());
  assert(false   == ARRAY.isAnyElementNull());
Next, we append a null element: 
  array.appendNullElement();
  assert(2           == ARRAY.length());
  assert(5           == ARRAY.constElement(0));
  assert(DEFAULT_INT == ARRAY.constElement(1));
  assert(false       == ARRAY.isElementNull(0));
  assert(true        == ARRAY.isElementNull(1));
  assert(1           == ARRAY.numNullElements());
  assert(true        == ARRAY.isAnyElementNonNull());
  assert(true        == ARRAY.isAnyElementNull());
Then, we make the null element non-null: 
  array.makeNonNull(1);
  assert(2           == ARRAY.length());
  assert(5           == ARRAY.constElement(0));
  assert(DEFAULT_INT == ARRAY.constElement(1));
  assert(false       == ARRAY.isElementNull(0));
  assert(false       == ARRAY.isElementNull(1));
  assert(0           == ARRAY.numNullElements());
  assert(true        == ARRAY.isAnyElementNonNull());
  assert(false       == ARRAY.isAnyElementNull());
Next, we make the first element null: 
  array.makeNull(0);
  assert(2           == ARRAY.length());
  assert(DEFAULT_INT == ARRAY.constElement(0));
  assert(DEFAULT_INT == ARRAY.constElement(1));
  assert(true        == ARRAY.isElementNull(0));
  assert(false       == ARRAY.isElementNull(1));
  assert(1           == ARRAY.numNullElements());
  assert(true        == ARRAY.isAnyElementNonNull());
  assert(true        == ARRAY.isAnyElementNull());
Now, we remove the front element: 
  array.removeElement(0);
  assert(1           == ARRAY.length());
  assert(DEFAULT_INT == ARRAY.constElement(0));
  assert(false       == ARRAY.isElementNull(0));
  assert(0           == ARRAY.numNullElements());
  assert(true        == ARRAY.isAnyElementNonNull());
  assert(false       == ARRAY.isAnyElementNull());
Finally, we remove the last remaining element and observe that the object is empty again: 
  array.removeElement(0);
  assert(0       == ARRAY.length());
  assert(0       == ARRAY.numNullElements());
  assert(false   == ARRAY.isAnyElementNonNull());
  assert(false   == ARRAY.isAnyElementNull());
Generated on Fri Mar 31 2023 13:25:44 for BDE Release 3.115.0.0 Production Release by  doxygen 1.7.1