BDE 4.14.0 Production release
Loading...
Searching...
No Matches
bdlc_bitarray
Group bdl » Package bdlc

Detailed Description

Outline

Purpose

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

Classes

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
bdlc::BitArray
Definition bdlc_bitarray.h:521

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@ref 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.
bdlc::BitArray::assign
void assign(bsl::size_t index, bool value)
Definition bdlc_bitarray.h:1368

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.
};
BSLMF_NESTED_TRAIT_DECLARATION
#define BSLMF_NESTED_TRAIT_DECLARATION(t_TYPE, t_TRAIT)
Definition bslmf_nestedtraitdeclaration.h:231
bsl::vector
Definition bslstl_vector.h:1025
bslma::Allocator
Definition bslma_allocator.h:457
bslma::UsesBslmaAllocator
Definition bslma_usesbslmaallocator.h:343

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();
}
BSLS_ASSERT
#define BSLS_ASSERT(X)
Definition bsls_assert.h:1804
BSLS_ASSERT_SAFE
#define BSLS_ASSERT_SAFE(X)
Definition bsls_assert.h:1762

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());