bslalg_arrayprimitives

Typedefs
typedef bslalg::ArrayPrimitives	bslalg_ArrayPrimitives
	This alias is defined for backward compatibility.

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Aliasing
  • Usage
    • Example 1: Defining a Vector-Like Type

Purpose

Provide primitive algorithms that operate on arrays.

Classes

• bslalg::ArrayPrimitives: namespace for array algorithms

See also

bslalg_dequeprimitives, bslma_constructionutil

Description

This component provides utilities to initialize, move, and otherwise perform various primitive manipulations on arrays with a uniform interface, but selecting a different implementation according to the various traits possessed by the underlying type. Such primitives are exceptionally useful for implementing generic components such as containers.

Several algorithms are provided, with the following short synopsis describing the observable behavior and mentioning the relevant traits. See the full function-level contract for detailed description, including exception-safety guarantees. In the description below, ADP stands for bslalg::ArrayDestructionPrimitives. Note that some algorithms (e.g., insert) are explained in terms of previous algorithms (e.g., destructiveMove).

Algorithm                     Short description of observable behavior
----------------------------  ---------------------------------------------
defaultConstruct              Construct each element in the target range
                              by value-initialization, or 'std::memset' if
                              type has a trivial default constructor.
                              Note that this function *does* *not* perform
                              default-initialization, the colloquial
                              terminology "default construct" is maintained
                              for backwards compatibility.
 
uninitializedFillN            Copy construct from value for each element in
                              the target range, or 'std::memset' if value
                              is all 0s or 1s bits, and type is bit-wise
                              copyable
 
copyConstruct                 Copy construct from each element in the
                              original range to the corresponding element
                              in the target range, or 'std::memcpy' if
                              value is null and type is bit-wise copyable
 
destructiveMove               Copy from each element in the original range
                              to the corresponding element in the target
                              and destroy objects in the original range, or
                              'std::memcpy' if type is bit-wise moveable
 
destructiveMoveAndInsert      'destructiveMove' from the original range to
                              target range, leaving a hole in the middle,
                              followed by 'defaultConstruct',
                              'uninitializedFillN' or 'copyConstruct' to
                              fill hole with the appropriate values
 
destructiveMoveAndMoveInsert  'destructiveMove' from the original range to
                              the target range, leaving a hole in the
                              middle, followed by 'destructiveMove'
                              from second range to fill hole
 
insert                        'std::memmove' or 'copyConstruct' by some
                              positive offset to create a hole, followed by
                              'uninitializedFillN', 'copyConstruct', or
                              copy assignment to fill hole with the
                              appropriate values
 
emplace                       'std::memmove' or 'copyConstruct' by some
                              positive offset to create a hole, followed by
                              in-place construction, 'copyConstruct', or
                              copy assignment to fill hole with the
                              appropriate values
 
moveInsert                    'destructiveMove' by some positive offset to
                              create a hole, followed by 'destructiveMove'
                              to fill hole with the appropriate values
 
erase                         'ADP::destroy' elements in target range until
                              specified position, followed by
                              'destructiveMove' by some negative offset
                              from the end of the range to fill hole with
                              the remaining values
 
rotate                        'destructiveMove' to move elements into a
                              shifting hole along parallel cyclic
                              permutations, or 'std::memmove' for small
                              rotations if type is bit-wise moveable

The traits under consideration by this component are:

Trait                                         English description
--------------------------------------------  -----------------------------
bsl::is_trivially_default_constructible       "TYPE has the trivial default
                                              constructor trait", or
                                              "TYPE has a trivial default
                                              constructor"
 
bslmf::IsBitwiseCopyable                      "TYPE has the bit-wise
                                              copyable trait", or
                                              "TYPE is bit-wise copyable"
 
bslmf::IsBitwiseMoveable                      "TYPE has the bit-wise
                                              moveable trait", or
                                              "TYPE is bit-wise moveable"

Aliasing

There are some aliasing concerns in this component, due to the presence of the reference const TARGET_TYPE& value argument, which may belong to a range that will be modified during the course of the operation. All such aliasing concerns are taken care of properly. Other aliasing concerns due to the copying or a range [first, last) are not taken care of, since their intended use is for range assignments and insertions in standard containers, for which the standard explicitly says that first and last shall not be iterators into the container.

Usage

In this section we show intended use of this component.

Example 1: Defining a Vector-Like Type

Suppose we want to define a STL-vector-like type. One requirement is that an object of this vector should forward its allocator to its contained elements when appropriate. Another requirement is that the vector should take advantage of the optimizations available for certain traits of the contained element type. For example, if the contained element type has the bslmf::IsBitwiseMoveable trait, moving an element in a vector can be done using memcpy instead of copy construction.

We can utilize the class methods provided by bslalg::ArrayPrimitives to satisfy the above requirements. Unlike bslma::ConstructionUtil, which operates on a single element, bslalg::ArrayPrimitives operates on arrays, which will further help simplify our implementation.

First, we create an elided definition of the class template MyVector:

template <class TYPE, class ALLOC>
class MyVector {
    // This class implements a vector of elements of the (template
    // parameter) 'TYPE', which must be copy constructible.  Note that for
    // the brevity of the usage example, this class does not provide any
    // Exception-Safety guarantee.
 
    // DATA
    TYPE             *d_array_p;     // pointer to the allocated array
    int               d_capacity;    // capacity of the allocated array
    int               d_size;        // number of objects
    ALLOC             d_allocator;   // allocator pointer (held, not owned)
 
  public:
    // TYPE TRAITS
    BSLMF_NESTED_TRAIT_DECLARATION(
        MyVector,
        BloombergLP::bslmf::IsBitwiseMoveable);
 
    // CREATORS
    explicit MyVector(bslma::Allocator *basicAllocator = 0)
        // Construct a 'MyVector' object having a size of 0 and and a
        // capacity of 0.  Optionally specify a 'basicAllocator' used to
        // supply memory.  If 'basicAllocator' is 0, the currently
        // installed default allocator is used.
    : d_array_p(0)
    , d_capacity(0)
    , d_size(0)
    , d_allocator_p(bslma::Default::allocator(basicAllocator))
    {
    }
 
    MyVector(const MyVector&   original,
             bslma::Allocator *basicAllocator = 0);
        // Create a 'MyVector' object having the same value as the
        // specified 'original' object.  Optionally specify a
        // 'basicAllocator' used to supply memory.  If 'basicAllocator' is
        // 0, the currently installed default allocator is used.
 
    // ...
 
    // MANIPULATORS
    void reserve(int minCapacity);
        // Change the capacity of this vector to at least the specified
        // 'minCapacity' if it is greater than the vector's current
        // capacity.
 
    void insert(int dstIndex, int numElements, const TYPE& value);
        // Insert, into this vector, the specified 'numElements' of the
        // specified 'value' at the specified 'dstIndex'.  The behavior is
        // undefined unless '0 <= dstIndex <= size()'.
 
    // ACCESSORS
    const TYPE& operator[](int position) const
        // Return a reference providing non-modifiable access to the
        // element at the specified 'position' in this vector.
    {
        return d_array_p[position];
    }
 
    int size() const
        // Return the size of this vector.
    {
        return d_size;
    }
};

Then, we implement the copy constructor of MyVector:

template <class TYPE>
MyVector<TYPE>::MyVector(const MyVector<TYPE>&  original,
                         bslma::Allocator      *basicAllocator)
: d_array_p(0)
, d_capacity(0)
, d_size(0)
, d_allocator_p(bslma::Default::allocator(basicAllocator))
{
    reserve(original.d_size);

Here, we call the bslalg::ArrayPrimitives::copyConstruct class method to copy each element from original.d_array_p to d_array_p (When appropriate, this class method passes this vector's allocator to the copy constructor of TYPE or uses bit-wise copy.):

    bslalg::ArrayPrimitives::copyConstruct(
                                      d_array_p,
                                      original.d_array_p,
                                      original.d_array_p + original.d_size,
                                      d_allocator_p);
 
    d_size = original.d_size;
}

Now, we implement the reserve method of MyVector:

template <class TYPE>
void MyVector<TYPE>::reserve(int minCapacity)
{
    if (d_capacity >= minCapacity) return;                        // RETURN
 
    TYPE *newArrayPtr = static_cast<TYPE*>(d_allocator_p->allocate(
    BloombergLP::bslma::Allocator::size_type(minCapacity * sizeof(TYPE))));
 
    if (d_array_p) {

Here, we call the bslalg::ArrayPrimitives::destructiveMove class method to copy each original element from d_array_p to newArrayPtr and then destroy all the original elements (When appropriate, this class method passes this vector's allocator to the copy constructor of TYPE or uses bit-wise copy.):

        bslalg::ArrayPrimitives::destructiveMove(newArrayPtr,
                                                 d_array_p,
                                                 d_array_p + d_size,
                                                 d_allocator_p);
        d_allocator_p->deallocate(d_array_p);
    }
 
    d_array_p = newArrayPtr;
    d_capacity = minCapacity;
}

Finally, we implement the insert method of MyVector:

template <class TYPE>
void
MyVector<TYPE>::insert(int dstIndex, int numElements, const TYPE& value)
{
    int newSize = d_size + numElements;
 
    if (newSize > d_capacity) {
        int newCapacity = d_capacity == 0 ? 2 : d_capacity * 2;
        reserve(newCapacity);
    }

Here, we call the bslalg::ArrayPrimitives::insert class method to first move each element after dstIndex by numElements and then copy construct numElements of value at dstIndex. (When appropriate, this class method passes this vector's allocator to the copy constructor of TYPE or uses bit-wise copy.):

    bslalg::ArrayPrimitives::insert(d_array_p + dstIndex,
                                    d_array_p + d_size,
                                    value,
                                    numElements,
                                    d_allocator_p);
 
    d_size = newSize;
}

Typedef Documentation

bslalg_ArrayPrimitives

typedef bslalg::ArrayPrimitives bslalg_ArrayPrimitives