vector

A vector , the simplest kind of STL container, is a sequential container similar to a regular C array, except that it expands to accommodate new items. This section describes vector .

Iterator Type

In Standards<ToolKit>, a vector has a random access iterator that is a regular C pointer. For example, begin() returns a C pointer to the first element in a vector .

Implementation

Most vector implementations store items in contiguous, linear memory space, so index-based access is very quick. When the allocated memory space for a vector is exceeded, its items are copied into a larger memory space and the old space is deallocated. For efficiency, memory is typically allocated in units of the machine's page size.

Insertion Notes

Inserting a single item into a vector is linear in the distance from the insertion point to the end of the vector . When a single item is inserted at the end of a vector , the amortized complexity over the lifetime of the vector is constant.

Inserting multiple items into a vector with a single call is linear in the sum of the number of items plus the distance to the end of the vector . It is much faster to insert multiple items into the middle of a vector at one time, than it is to insert them one at a time.

When inserting an item into a vector , all iterators and references after the insertion point are invalidated. If an insertion causes reallocation of memory space, all iterators and references for the vector are invalidated.

Erasure Notes

When erasing an item from a vector , the destructor is called once for each erased item; the assignment operator is called once for each item left in the vector after the erased item.

Erasing invalidates all of the iterators and references to elements after the point of the erase.

Common Uses

The underlying architecture of vector objects makes them ideal for storing items when order is significant and fast numeric indexing is important. Because inserting items anywhere except at the end of a vector is slow, you should not use vectors when this kind of operation is common; instead, consider using a list or a deque .

Interface

A vector includes functions for accessing its extremities, appending, inserting, erasing, and adjusting its capacity. This section describes each of these functions in detail.

The default constructor for vector (the first constructor in the list below) creates an empty vector with no associated memory storage. A vector has additional constructors for creating a vector with a specified number of initialized items or items within a specified range (the second and third constructors in the list below).

Constructor
vector( size_type n )
Constructs a vector that contains n items set to their default values.
Constructor
vector( size_type n , const T& value )
Constructs a vector that contains n items set to value .
Constructor
vector( iterator first , iterator last )
Constructs a vector that contains copies of all items in the range between first and last , including first but not last .

The following example uses the third form of constructor in the above list to build a vector initialized from a regular C array.

Example <ospace/osstd/examples/vec5.cpp>
#include <iostream>
#include <vector>

int array[] = { 1, 4, 9, 16 };

void
main()
  {
  vector< int > v( array, array + 4 );

  for ( int i = 0; i < v.size(); ++i )
    cout << "v[ " << i << " ] = " << v[ i ] << "\n";
  }

v[ 0 ] = 1
v[ 1 ] = 4
v[ 2 ] = 9
v[ 3 ] = 16

Following is a summary of some of the most basic vector functions.

back
T& back()
Returns a reference to the last item in the vector .
front
T& front()
Returns a reference to the first item in the vector .
push_back
void push_back( const T& value )
Adds value at the end of the vector , expanding the storage to accommodate the new item if necessary.
pop_back
void pop_back()
Erases the last item in the vector .
[]
T& operator[]( int index )
Returns a reference to the item at position index .

There are also const versions of front() , back() , and operator[] . The following example illustrates these functions.

Example <ospace/osstd/examples/vec4.cpp>
#include <iostream>
#include <vector>

void
main()
  {
  vector< int > v( 4 );
  v[ 0 ] = 1;
  v[ 1 ] = 4;
  v[ 2 ] = 9;
  v[ 3 ] = 16;
  cout << "front = " << v.front() << "\n";
  cout << "back = " << v.back() << ", size = " << v.size() << "\n";

  v.push_back( 25 );
  cout << "back = " << v.back() << ", size = " << v.size() << "\n";

  v.pop_back();
  cout << "back = " << v.back() << ", size = " << v.size() << "\n";
  }

front = 1
back = 16, size = 4
back = 25, size = 5
back = 16, size = 4

An STL container always stores copies of items that are added to it. When an STL container is destroyed, it invokes the destructor for each item. If the items are pointers to objects stored on the heap, the heap-based objects are not automatically destroyed.

In this example, the for_each() algorithm is used with a release() function to delete each individual element.

Example <ospace/osstd/examples/release1.cpp>
#include <iostream>
#include <vector>
#include <algorithm>

class X
  {
  public:
    X( int i_ ) : i( i_ ) {}
    ~X() { cout << "Delete X( " << i << " )" << endl; }
    int i;
  };

ostream& operator <<( ostream& stream_, const X& x_ )
  {
  return stream_ << "X( " << x_.i << " )";
  }

void release( X* arg )
  {
  delete arg;
  }

void
main()
  {
  vector< X* > v; // Vector of pointers to X objects.
  v.push_back( new X( 2 ) );
  v.push_back( new X( 1 ) );
  v.push_back( new X( 4 ) );
  vector< X* >::iterator i;
  for ( i = v.begin(); i != v.end(); i++ )
    cout << *(*i) << endl;

  for_each( v.begin(), v.end(), release );
  }

X( 2 )
X( 1 )
X( 4 )
Delete X( 2 )
Delete X( 1 )
Delete X( 4 )

STL provides the following functions for inserting an item into a container.

insert
iterator insert( iterator pos , const T& value )
Inserts value at pos and returns an iterator pointing to the new position.
insert
void insert( iterator pos , size_type n , const T& value )
Inserts n copies of value at pos .
insert
void insert( iterator pos , const_iterator first , const_iterator last )
Inserts copies of the items in the range between first and last , including first but not last , before pos .

Inserting an item into a vector shifts all items right of the pointer one place to the right. If necessary, more storage is allocated. Specify end() as the insertion point to insert an item after the last item; specify begin() as the insertion point to insert an item before the first item. The following example inserts an item into a vector .

Example <ospace/osstd/examples/vec7.cpp>
#include <iostream>
#include <vector>

int array1[] = { 1, 4, 25 };
int array2[] = { 9, 16 };

void
main()
  {
  vector< int > v( array1, array1 + 3 );

  v.insert( v.begin(), 0 ); // Insert before first element.
  v.insert( v.end(), 36 ); // Insert after last element.

  int i;
  for ( i = 0; i < v.size(); ++i )
    cout << "v[ " << i << " ] = " << v[ i ] << "\n";
  cout << "\n";

  // Insert contents of array2 before fourth element.
  v.insert( v.begin() + 3, array2, array2 + 2 );

  for ( i = 0; i < v.size(); ++i )
    cout << "v[ " << i << " ] = " << v[ i ] << "\n";
  cout << "\n";
  }
v[ 0 ] = 0
v[ 1 ] = 1
v[ 2 ] = 4
v[ 3 ] = 25
v[ 4 ] = 36

v[ 0 ] = 0
v[ 1 ] = 1
v[ 2 ] = 4
v[ 3 ] = 9
v[ 4 ] = 16
v[ 5 ] = 25
v[ 6 ] = 36

STL provides a comprehensive set of functions for erasing an item from a container.

clear
void clear()
Erases all items from a container.
erase
void erase( iterator pos )
Erases the item at pos .
erase
void erase( iterator first , iterator last )
Erases the items between first and last , including first but not last .

When an item is erased, it is removed from the container and then its destructor is called. When an item is erased from a vector , the remaining items shift to the left to fill the space, and its size decrements by one.

Be careful when supplying the iterator arguments to erase() . For example, it is a common mistake to think v.erase( v.end() ) erases the last item of v . Because v.end() positions the pointer immediately after the last item, the correct way to erase the last item of v is to write v.erase( v.end() - 1 ) . Following are some examples of the erase() family.

Example <ospace/osstd/examples/vec6.cpp>
#include <iostream>
#include <vector>

int array[] = { 1, 4, 9, 16, 25, 36 };

void
main()
  {
  vector< int > v( array, array + 6 );
  int i;
  for ( i = 0; i < v.size(); ++i )
    cout << "v[ " << i << " ] = " << v[ i ] << "\n";
  cout << "\n";

  v.erase( v.begin() ); // Erase first element.

  for ( i = 0; i < v.size(); ++i )
    cout << "v[ " << i << " ] = " << v[ i ] << "\n";
  cout << "\n";

  v.erase( v.end() - 1 ); // Erase last element.

   for ( i = 0; i < v.size(); ++i )
    cout << "v[ " << i << " ] = " << v[ i ] << "\n";
  cout << "\n";

  v.erase( v.begin() + 1, v.end() - 1 ); // Erase all but first, last.

  for ( i = 0; i < v.size(); ++i )
    cout << "v[ " << i << " ] = " << v[ i ] << "\n";
  cout << "\n";

  v.clear(); // Erase all.
  }

v[ 0 ] = 1
v[ 1 ] = 4
v[ 2 ] = 9
v[ 3 ] = 16
v[ 4 ] = 25
v[ 5 ] = 36

v[ 0 ] = 4
v[ 1 ] = 9
v[ 2 ] = 16
v[ 3 ] = 25
v[ 4 ] = 36

v[ 0 ] = 4
v[ 1 ] = 9
v[ 2 ] = 16
v[ 3 ] = 25

v[ 0 ] = 4
v[ 2 ] = 25

None of the preceding functions are unique to vector . However, the following functions apply only to vector . These functions directly access and modify the amount of underlying storage in a vector.

capacity
size_type capacity() const
Returns the maximum number of items the vector can contain without allocating more memory.
reserve
void reserve( size_type n )
Preallocates enough space to hold up to n items. This operation does not change the value returned by size() .

The reserve() function is particularly useful if you know how large a vector will grow and you want to avoid the overhead of memory reallocations. The following example uses reserve() to boost the underlying capacity of a vector to 5000 items. The memory allocation scheme allocates 1K of memory when the first item is added.

Example <ospace/osstd/examples/vec8.cpp>
#include <iostream>
#include <vector>

void
main()
  {
  vector< int > v;
  cout << "capacity = " << v.capacity() << "\n";
  v.push_back( 42 );
  cout << "capacity = " << v.capacity() << "\n";
  v.reserve( 5000 );
  cout << "capacity = " << v.capacity() << "\n";
  }

capacity = 0
capacity = 1024
capacity = 5000

Copyright©1994-2026 Recursion Software LLC
All Rights Reserved - For use by licensed users only.