Component bslalg_arrayprimitives [Package bslalg]

Provide primitive algorithms that operate on arrays. More...

Namespaces
namespace	bslalg

---

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:

Component bslalg_dequeprimitives, Component 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"

  bsl::is_trivially_copyable                    "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;
  }