bslstl_vector

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Requirements on VALUE_TYPE
  • Glossary
  • Memory Allocation
    • bslma-Style Allocators
  • Operations
  • Comparing a vector of floating point values
  • Usage
    • Example 1: Creating a Matrix Type

Purpose

Provide an STL-compliant vector class.

Classes

• bsl::vector: STL-compatible vector template

Canonical header: bsl_vector.h

See also

bslstl_deque

Description

This component defines a single class template, bsl::vector, implementing the standard sequential container, std::vector, holding a dynamic array of values of a template parameter type.

An instantiation of vector is an allocator-aware, value-semantic type whose salient attributes are its size (number of values) and the sequence of values the vector contains. If vector is instantiated with a value type that is not value-semantic, then the vector will not retain all of its value-semantic qualities. In particular, if a value type cannot be tested for equality, then a vector containing objects of that type cannot be tested for equality. It is even possible to instantiate vector with a value type that does not have a copy-constructor, in which case the vector will not be copyable.

A vector meets the requirements of a sequential container with random access iterators in the C++ standard [vector]. The vector implemented here adheres to the C++11 standard when compiled with a C++11 compiler, and makes the best approximation when compiled with a C++03 compiler. In particular, for C++03 we emulate move semantics, but limit forwarding (in emplace) to const lvalues, and make no effort to emulate noexcept or initializer lists.

Requirements on VALUE_TYPE

A vector is a fully Value-Semantic Type (see bsldoc_glossary ) only if the supplied VALUE_TYPE template parameter is fully value-semantic. It is possible to instantiate a vector with a VALUE_TYPE parameter that does not have a full set of value-semantic operations, but then some methods of the container may not be instantiable. The following terminology, adopted from the C++11 standard, is used in the function documentation of vector to describe a function's requirements for the VALUE_TYPE template parameter. These terms are also defined in section [17.6.3.1] of the C++11 standard. Note that, in the context of a vector instantiation, the requirements apply specifically to the vector's entry type, value_type, which is an alias for VALUE_TYPE.

Glossary

Legend
------
'X'    - denotes an allocator-aware container type (e.g., 'vector')
'T'    - 'value_type' associated with 'X'
'A'    - type of the allocator used by 'X'
'm'    - lvalue of type 'A' (allocator)
'p'    - address ('T *') of uninitialized storage for a 'T' within an 'X'
'rv'   - rvalue of type (non-'const') 'T'
'v'    - rvalue or lvalue of type (possibly 'const') 'T'
'args' - 0 or more arguments

The following terms are used to more precisely specify the requirements on template parameter types in function-level documentation.

default-insertable: T has a default constructor. More precisely, T is default-insertable into X means that the following expression is well-formed: allocator_traits<A>::construct(m, p)

move-insertable: T provides a constructor that takes an rvalue of type (non-const) T. More precisely, T is move-insertable into X means that the following expression is well-formed: allocator_traits<A>::construct(m, p, rv)

copy-insertable: T provides a constructor that takes an lvalue or rvalue of type (possibly const) T. More precisely, T is copy-insertable into X means that the following expression is well-formed: allocator_traits<A>::construct(m, p, v)

move-assignable: T provides an assignment operator that takes an rvalue of type (non-const) T.

copy-assignable: T provides an assignment operator that takes an lvalue or rvalue of type (possibly const) T.

emplace-constructible: T is emplace-constructible into X from args means that the following expression is well-formed: allocator_traits<A>::construct(m, p, args)

erasable: T provides a destructor. More precisely, T is erasable from X means that the following expression is well-formed: allocator_traits<A>::destroy(m, p)

equality-comparable: The type provides an equality-comparison operator that defines an equivalence relationship and is both reflexive and transitive.

Memory Allocation

The type supplied as a vector's ALLOCATOR template parameter determines how that vector will allocate memory. The vector template supports allocators meeting the requirements of the C++03 standard; in addition, it supports scoped-allocators derived from the bslma::Allocator memory allocation protocol. Clients intending to use bslma-style allocators should use the template's default ALLOCATOR type: The default type for the ALLOCATOR template parameter, bsl::allocator, provides a C++11 standard-compatible adapter for a bslma::Allocator object.

bslma-Style Allocators

If the (template parameter) type ALLOCATOR of a vector instantiation' is bsl::allocator, then objects of that vector type will conform to the standard behavior of a bslma-allocator-enabled type. Such a vector accepts an optional bslma::Allocator argument at construction. If the address of a bslma::Allocator object is explicitly supplied at construction, it is used to supply memory for the vector throughout its lifetime; otherwise, the vector will use the default allocator installed at the time of the vector's construction (see bslma_default ). In addition to directly allocating memory from the indicated bslma::Allocator, a vector supplies that allocator's address to the constructors of contained objects of the (template parameter) type VALUE_TYPE, if it defines the bslma::UsesBslmaAllocator trait.

Operations

This section describes the run-time complexity of operations on instances of vector:

Legend
------
'V'             - (template parameter) 'VALUE_TYPE' of the vector
'a', 'b'        - two distinct objects of type 'vector<V>'
'rv'            - modifiable rvalue of type 'vector<V>'
'n', 'm'        - number of elements in 'a' and 'b', respectively
'k'             - non-negative integer
'al'            - an STL-style memory allocator
'i1', 'i2'      - two iterators defining a sequence of 'V' objects
'il'            - object of type 'std::initializer_list<V>'
'lil'           - length of 'il'
'vt'            - object of type 'VALUE_TYPE'
'rvt'           - modifiable rvalue of type 'VALUE_TYPE'
'p1', 'p2'      - two 'const' iterators belonging to 'a'
distance(i1,i2) - the number of elements in the range [i1, i2)
 
|-----------------------------------------+-------------------------------|
| Operation                               | Complexity                    |
|=========================================+===============================|
| vector<V> a      (default construction) | O[1]                          |
| vector<V> a(al)                         |                               |
|-----------------------------------------+-------------------------------|
| vector<V> a(b)   (copy construction)    | O[n]                          |
| vector<V> a(b, al)                      |                               |
|-----------------------------------------+-------------------------------|
| vector<V> a(rv)  (move construction)    | O[1] if 'a' and 'rv' use the  |
| vector<V> a(rv, al)                     | same allocator; O[n] otherwise|
|-----------------------------------------+-------------------------------|
| vector<V> a(k)                          | O[k]                          |
| vector<V> a(k, al)                      |                               |
| vector<V> a(k, vt)                      |                               |
| vector<V> a(k, vt, al)                  |                               |
|-----------------------------------------+-------------------------------|
| vector<V> a(i1, i2)                     | O[distance(i1, i2)]           |
| vector<V> a(i1, i2, al)                 |                               |
|-----------------------------------------+-------------------------------|
| vector<V> a(il)                         | O[lil]                        |
| vector<V> a(il, al)                     |                               |
|-----------------------------------------+-------------------------------|
| a.~vector<V>()  (destruction)           | O[n]                          |
|-----------------------------------------+-------------------------------|
| a.assign(k, vt)                         | O[k]                          |
| a.assign(k, rvt)                        |                               |
|-----------------------------------------+-------------------------------|
| a.assign(i1, i2)                        | O[distance(i1, i2)]           |
|-----------------------------------------+-------------------------------|
| a.assign(il)                            | O[lil]                        |
|-----------------------------------------+-------------------------------|
| get_allocator()                         | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.begin(), a.end(),                     | O[1]                          |
| a.cbegin(), a.cend(),                   |                               |
| a.rbegin(), a.rend(),                   |                               |
| a.crbegin(), a.crend()                  |                               |
|-----------------------------------------+-------------------------------|
| a.size()                                | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.max_size()                            | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.resize(k)                             | O[k]                          |
| a.resize(k, vt)                         |                               |
|-----------------------------------------+-------------------------------|
| a.empty()                               | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.reserve(k)                            | O[k]                          |
|-----------------------------------------+-------------------------------|
| a.shrink_to_fit()                       | O[n]                          |
|-----------------------------------------+-------------------------------|
| a[k]                                    | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.at(k)                                 | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.front()                               | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.back()                                | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.push_back(vt)                         | O[1]                          |
| a.push_back(rvt)                        |                               |
|-----------------------------------------+-------------------------------|
| a.pop_back()                            | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.emplace_back(args)                    | O[1]                          |
|-----------------------------------------+-------------------------------|
| a.emplace(p1, args)                     | O[1 + distance(p1, a.end())]  |
|-----------------------------------------+-------------------------------|
| a.insert(p1, vt)                        | O[1 + distance(p1, a.end())]  |
| a.insert(p1, rvt)                       |                               |
|-----------------------------------------+-------------------------------|
| a.insert(p1, k, vt)                     | O[k + distance(p1, a.end())]  |
| a.insert(p1, k, rvt)                    |                               |
|-----------------------------------------+-------------------------------|
| a.insert(p1, i1, i2)                    | O[distance(i1, i2)            |
|                                         |      + distance(p1, a.end())] |
|-----------------------------------------+-------------------------------|
| a.insert(p1, il)                        | O[lil                         |
|                                         |      + distance(p1, a.end())] |
|-----------------------------------------+-------------------------------|
| a.erase(p1)                             | O[1 + distance(p1, a.end())]  |
|-----------------------------------------+-------------------------------|
| a.erase(p1, p2)                         | O[distance(p1, p2)            |
|                                         |      + distance(p1, a.end())] |
|-----------------------------------------+-------------------------------|
| a.swap(b), swap(a, b)                   | O[1] if 'a' and 'b' use the   |
|                                         | same allocator; O[n + m]      |
|                                         | otherwise                     |
|-----------------------------------------+-------------------------------|
| a.clear()                               | O[n]                          |
|-----------------------------------------+-------------------------------|
| a = b;           (copy assignment)      | O[n]                          |
|-----------------------------------------+-------------------------------|
| a = rv;          (move assignment)      | O[1] if 'a' and 'rv' use the  |
|                                         | same allocator; O[n] otherwise|
|-----------------------------------------+-------------------------------|
| a = il;                                 | O[lil]                        |
|-----------------------------------------+-------------------------------|
| a == b, a != b                          | O[n]                          |
|-----------------------------------------+-------------------------------|
| a < b, a <= b, a > b, a >= b            | O[n]                          |
|-----------------------------------------+-------------------------------|

Comparing a vector of floating point values

The comparison operator performs a bit-wise comparison for floating point types (float and double), which produces results for NaN, +0, and -0 values that do not meet the guarantees provided by the standard. The bslmf::IsBitwiseEqualityComparable trait for double and float types returns true which is incorrect because a comparison with a NaN value is always false, and -0 and +0 are equal.

  bsl::vector<double> v;
  v.push_back(bsl::numeric_limits<double>::quiet_NaN());
  ASSERT(v == v);   // This assertion will *NOT* fail!

Addressing this issue, i.e., updating bslmf::IsBitwiseEqualityComparable to return false for floating point types, could potentially destabilize production software so the change (for the moment) has not been made.

Usage

In this section we show intended use of this component.

Example 1: Creating a Matrix Type

Suppose we want to define a value-semantic type representing a dynamically resizable two-dimensional matrix.

First, we define the public interface for the MyMatrix class template:

template <class TYPE>
class MyMatrix {
    // This value-semantic type characterizes a two-dimensional matrix of
    // objects of the (template parameter) 'TYPE'.  The numbers of columns
    // and rows of the matrix can be specified at construction and, at any
    // time, via the 'reset', 'insertRow', and 'insertColumn' methods.  The
    // value of each element in the matrix can be set and accessed using
    // the 'theValue', and 'theModifiableValue' methods respectively.
 
  public:
    // PUBLIC TYPES

Here, we create a type alias, RowType, for an instantiation of bsl::vector to represent a row of TYPE objects in the matrix. We create another type alias, MatrixType, for an instantiation of bsl::vector to represent the entire matrix of TYPE objects as a list of rows:

    typedef bsl::vector<TYPE>    RowType;
        // This is an alias representing a row of values of the (template
        // parameter) 'TYPE'.
 
    typedef bsl::vector<RowType> MatrixType;
        // This is an alias representing a two-dimensional matrix of values
        // of the (template parameter) 'TYPE'.
 
  private:
    // DATA
    MatrixType d_matrix;      // matrix of values
    int        d_numColumns;  // number of columns
 
    // FRIENDS
    template <class T>
    friend bool operator==(const MyMatrix<T>&, const MyMatrix<T>&);
 
  public:
    // PUBLIC TYPES
    typedef typename MatrixType::const_iterator ConstRowIterator;
 
    // CREATORS
    MyMatrix(int               numRows,
             int               numColumns,
             bslma::Allocator *basicAllocator = 0);
        // Create a 'MyMatrix' object having the specified 'numRows' and
        // the specified 'numColumns'.  All elements of the (template
        // parameter) 'TYPE' in the matrix will have the
        // default-constructed value.  Optionally specify a
        // 'basicAllocator' used to supply memory.  If 'basicAllocator' is
        // 0, the currently installed default allocator is used.  The
        // behavior is undefined unless '0 <= numRows' and
        // '0 <= numColumns'
 
    MyMatrix(const MyMatrix&   original,
             bslma::Allocator *basicAllocator = 0);
        // Create a 'MyMatrix' 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.
 
    //! ~MyMatrix = default;
        // Destroy this object.
 
    // MANIPULATORS
    MyMatrix& operator=(const MyMatrix& rhs);
        // Assign to this object the value of the specified 'rhs' object,
        // and return a reference providing modifiable access to this
        // object.
 
    void clear();
        // Remove all rows and columns from this object.
 
    void insertColumn(int columnIndex);
        // Insert, into this matrix, an column at the specified
        // 'columnIndex'.  All elements of the (template parameter) 'TYPE'
        // in the column will have the default-constructed value.  The
        // behavior is undefined unless '0 <= columnIndex <= numColumns()'.
 
    void insertRow(int rowIndex);
        // Insert, into this matrix, a row at the specified 'rowIndex'.
        // All elements of the (template parameter) 'TYPE' in the row will
        // have the default-constructed value.  The behavior is undefined
        // unless '0 <= rowIndex <= numRows()'.
 
    TYPE& theModifiableValue(int rowIndex, int columnIndex);
        // Return a reference providing modifiable access to the element at
        // the specified 'rowIndex' and the specified 'columnIndex' in this
        // matrix.  The behavior is undefined unless
        // '0 <= rowIndex < numRows()' and
        // '0 <= columnIndex < numColumns()'.
 
    // ACCESSORS
    int numRows() const;
        // Return the number of rows in this matrix.
 
    int numColumns() const;
        // Return the number of columns in this matrix.
 
    ConstRowIterator beginRow() const;
        // Return an iterator providing non-modifiable access to the
        // 'RowType' objects representing the first row in this matrix.
 
    ConstRowIterator endRow() const;
        // Return an iterator providing non-modifiable access to the
        // 'RowType' objects representing the past-the-end row in this
        // matrix.
 
    const TYPE& theValue(int rowIndex, int columnIndex) const;
        // Return a reference providing non-modifiable access to the
        // element at the specified 'rowIndex' and the specified
        // 'columnIndex' in this matrix.  The behavior is undefined unless
        // '0 <= rowIndex < numRows()' and
        // '0 <= columnIndex < numColumns()'.
};

Then we declare the free operator for MyMatrix:

// FREE OPERATORS
template <class TYPE>
MyMatrix<TYPE> operator==(const MyMatrix<TYPE>& lhs,
                          const MyMatrix<TYPE>& rhs);
    // Return 'true' if the specified 'lhs' and 'rhs' objects have the same
    // value, and 'false' otherwise.  Two 'MyMatrix' objects have the same
    // value if they have the same number of rows and columns and every
    // element in both matrices compare equal.
 
template <class TYPE>
MyMatrix<TYPE> operator!=(const MyMatrix<TYPE>& lhs,
                          const MyMatrix<TYPE>& rhs);
    // Return 'true' if the specified 'lhs' and 'rhs' objects do not have
    // the same value, and 'false' otherwise.  Two 'MyMatrix' objects do
    // not have the same value if they do not have the same number of rows
    // and columns or every element in both matrices do not compare equal.
 
template <class TYPE>
MyMatrix<TYPE> operator*(const MyMatrix<TYPE>& lhs,
                         const MyMatrix<TYPE>& rhs);
    // Return a 'MyMatrix' objects that is the product of the specified
    // 'lhs' and 'rhs'.  The behavior is undefined unless
    // 'lhs.numColumns() == rhs.numRows()'.

Now, we define the methods of MyMatrix:

// CREATORS
template <class TYPE>
MyMatrix<TYPE>::MyMatrix(int numRows,
                         int numColumns,
                         bslma::Allocator *basicAllocator)
: d_matrix(numRows, basicAllocator)
, d_numColumns(numColumns)
{
    BSLS_ASSERT(0 <= numRows);
    BSLS_ASSERT(0 <= numColumns);
 
    for (typename MatrixType::iterator itr = d_matrix.begin();
         itr != d_matrix.end();
         ++itr) {
        itr->resize(d_numColumns);
    }
}
template <class TYPE>
MyMatrix<TYPE>::MyMatrix(const MyMatrix& original,
                         bslma::Allocator *basicAllocator)
: d_matrix(original.d_matrix, basicAllocator)
, d_numColumns(original.d_numColumns)
{
}

Notice that we pass the contained bsl::vector (d_matrix) the allocator specified at construction to supply memory. If the (template parameter) TYPE of the elements has the bslalg_TypeTraitUsesBslmaAllocator trait, this allocator will be passed by the vector to the elements as well.

// MANIPULATORS
template <class TYPE>
MyMatrix<TYPE>& MyMatrix<TYPE>::operator=(const MyMatrix& rhs)
{
    d_matrix = rhs.d_matrix;
    d_numColumns = rhs.d_numColumns;
}
 
template <class TYPE>
void MyMatrix<TYPE>::clear()
{
    d_matrix.clear();
    d_numColumns = 0;
}
 
template <class TYPE>
void MyMatrix<TYPE>::insertColumn(int colIndex) {
    for (typename MatrixType::iterator itr = d_matrix.begin();
         itr != d_matrix.end();
         ++itr) {
        itr->insert(itr->begin() + colIndex, TYPE());
    }
    ++d_numColumns;
}
 
template <class TYPE>
void MyMatrix<TYPE>::insertRow(int rowIndex)
{
    typename MatrixType::iterator itr =
        d_matrix.insert(d_matrix.begin() + rowIndex, RowType());
    itr->resize(d_numColumns);
}
 
template <class TYPE>
TYPE& MyMatrix<TYPE>::theModifiableValue(int rowIndex, int columnIndex)
{
    BSLS_ASSERT(0 <= rowIndex);
    BSLS_ASSERT(rowIndex < d_matrix.size());
    BSLS_ASSERT(0 <= columnIndex);
    BSLS_ASSERT(columnIndex < d_numColumns);
 
    return d_matrix[rowIndex][columnIndex];
}
 
// ACCESSORS
template <class TYPE>
int MyMatrix<TYPE>::numRows() const
{
    return d_matrix.size();
}
 
template <class TYPE>
int MyMatrix<TYPE>::numColumns() const
{
    return d_numColumns;
}
 
template <class TYPE>
typename MyMatrix<TYPE>::ConstRowIterator MyMatrix<TYPE>::beginRow() const
{
    return d_matrix.begin();
}
 
template <class TYPE>
typename MyMatrix<TYPE>::ConstRowIterator MyMatrix<TYPE>::endRow() const
{
    return d_matrix.end();
}
 
template <class TYPE>
const TYPE& MyMatrix<TYPE>::theValue(int rowIndex, int columnIndex) const
{
    BSLS_ASSERT(0 <= rowIndex);
    BSLS_ASSERT(rowIndex < d_matrix.size());
    BSLS_ASSERT(0 <= columnIndex);
    BSLS_ASSERT(columnIndex < d_numColumns);
 
    return d_matrix[rowIndex][columnIndex];
}

Finally, we defines the free operators for MyMatrix:

// FREE OPERATORS
template <class TYPE>
MyMatrix<TYPE> operator==(const MyMatrix<TYPE>& lhs,
                          const MyMatrix<TYPE>& rhs)
{
    return lhs.d_numColumns == rhs.d_numColumns &&
                                              lhs.d_matrix == rhs.d_matrix;
}
 
template <class TYPE>
MyMatrix<TYPE> operator!=(const MyMatrix<TYPE>& lhs,
                          const MyMatrix<TYPE>& rhs)
{
    return !(lhs == rhs);
}