C++ Vector

• The sequence container of choice when the majority of insertions and erasures occur at the end of the sequence
• A dynamically sizing array
• Memory allocation is handled automatically
• Provides random access iterators
• Amortized constant time insert and erase operations at the end
• Insert and erase at any other position (beginning or middle) takes linear time
• Inserts can cause reallocation
  • All elements of a vector are stored in a contiguous block of memory
  • If you insert more items than the current capacity of the vector can handle, a larger block is allocated, the elements of the vector are copied from the old vector to the new vector, and the old block is deallocated.
  • Reallocation invalidates all iterators and references to elements within the vector
• Erasures invalidate all iterators to positions past the point of erasure (those pointing to previous locations remain valid)

#include <vector>
template <typename T>
class vector;

Constructors

• Default Constructor
  • Size: 0
  • Capacity: Usually 0 (Implementation Specific)

  vector <T> v;

• A Vector of Size n

  vector <T> vector1(n);

• A Vector of Size n each initialized to value

  vector <T> v(n, value);

• Copy Constructor

  vector (const vector <T>∓ v);

• Range [first,last)

  vector (InputIterator first, InputIterator last);

Destructor

• Destroy all container elements (calling destructor for each element) and deallocate all storage for the container.

  ~vector()

Member Functions

• begin()
  • Return iterator to beginning of the container (1st element)

  iterator begin();
  const_iterator begin() const;
  

• end()
  • Return iterator to end of the container (i.e. one past last element)

  iterator end();
  const_iterator end() const;
  

• rbegin()
  • Return reverse iterator to reverse beginning (i.e. last element)

  iterator rbegin();
  const_iterator rbegin() const;
  

• rend()
  • Return reverse iterator to reverse end (i.e. one past first element)

  iterator rend();
  const_iterator rend() const;
  

• operator[]
  • returns the nth element from the beginning of the vector
  • Bounds checking is not performed.
  • Undefined behavior if called with an argument n which is out of range

  reference       operator[](size_type n);
  const_reference operator[](size_type n) const;
  

• at
  • returns the nth element from the beginning of the vector
  • Throws std::out_of_range exception if n is out of range

  reference       at (size_type n);
  const_reference at (size_type n) const;
  

• front()
  • Returns a reference to the first element in the container
  • Undefined behavior if called on an empty container

  reference front();
  const_reference front() const;
  

• back()
  • Returns a reference to the last element in the container
  • Undefined behavior if called on an empty container

  reference back();
  const_reference back() const;
  

• size()
  • returns # of elements

  size_type size() const;

• empty()
  • returns true if the vector contains no elements (size == 0 or begin() == end()), false otherwise

  bool empty() const;
  

• capacity()
  • returns largest # of elements the vector can store without reallocation

  size_type capacity() const;

• reserve()
  • Ensures that after the call, the capacity() of the vector is >= n
  • Only allocates memory (which remains uninitialized).
  • Does not increase the size of the vector.
  • See also resize()

  void reserve(n);
  

• resize(size_type count)
  • resize the container to contain count elements
  • If the current size is less than count, additional elements are appended with the approriate constructor called
  • If the current size is greater than count, the container is reduced in size

  void resize(size_type count);
  void resize(size_type count, const value_type& value);
  

• push_back()
  • Add element to end of the vector, increasing the container size by 1.

  void push_back(const T& x);
  

• emplace_back()
  • Construct and insert element to end of the vector, increasing the container size by 1
  • args - the arguments to forward to the element constructor

  void emplace_back(args);
  

• insert()
  • insert single element or range of elements ([first, last)) into the vector at position.
  • returns iterator to position where the element was added

  iterator insert(iterator position, const T& x);
  iterator insert(iterator position, InputIterator first, InputIterator last);
  

• emplace()
  • constuct (in-place) and insert an element into the vector at position.
  • args - the arguments to forward to the element constructor
  • returns iterator to position where the element was added

  iterator emplace(iterator position, args);
  

• pop_back()
  • erase last element from the vector
  • destructor will be called for removed element
  • Undefined behavior if called on an empty container

  void pop_back();
  

• erase()
  • erase single element or range of elements ([first, last)) from the vector
  • returns iterator to 1 position past the last element erased
  • destructor will be called for each removed element

  iterator erase(iterator position);
  iterator erase(iterator first, iterator last);
  

• clear()
  • erase all elements in the vector
  • destructor will be called for each removed element
  • equivalent to vector.erase(vector.begin(), vector.end());

  void clear();
  

C++ Matrix

std::vector <std::vector<int>> m (size);

for (int i=0;i<size;i++)
{
    m[i].resize(size);
}

// now we can access as normal
m[0][0] = ...;
m[0][size-1] = ...;
m[size-1][size-1] = ...;

Vector as a Stack

• A Stack is a linear data structure
• LIFO (Last In, First Out)
• A vector lends itself well as a base data structure for a stack as all additions and deletions occur at the end

// using a vector as a stack
    
#include <cassert>

std::vector<int> stack;

for (int i=0;i<5;i++)
{
    stack.push_back(i);
}

for (int i=4;i>-1;i--)       // 4,3,2,1,0
{
    int x = stack.back();

    assert (x == i);

    stack.pop_back();
}

Binary Search

//
// binary search of sorted vector
//
bool binary_search (const std::vector<int> v, int k)
{
    int first = 0;
    int last = v.size()-1;
    int middle = (first+last) / 2;

    while (first <= last)
    {
        if (k < v[middle])   // reduce to 1st half
        {
            last = middle-1;
        }
        else if (k > v[middle]) // reduce to 2nd half
        {
            first = middle+1;
        }
        else
        {
            return true;
        }

        middle = (first+last) / 2;
    }

    return false;
}

#include <vector>
#include <algorithm> // sort, binary_search

std::vector<int> v { 1, 10, 2, 9, 3, 8, 4, 7, 5, 6 };

std::sort (v.begin(), v.end());

std::cout << binary_search(v, 10) << std::endl;     // true
std::cout << binary_search(v, 12) << std::endl;     // false

// we could also use library method
std::cout << std::binary_search(v.begin(), v.end(), 10) << std::endl;     // true
std::cout << std::binary_search(v.begin(), v.end(), 12) << std::endl;     // false