Lecture Notes for Advanced Programming II

6 February 2003 - STL Vectors

STL Vectors

• STL Vectors

• Vector Definition

• Vector Constructors

• Vector Element Access

• .at() vs. []

• Growing and Shrinking Vectors

• Vector Relation Operators

• Vector Less-Than

• Lexicographic Order

• Vector Type Definitions

• Vector Miscellany

Vector Behavior

• Vectors are like arrays.

  • A sequence of elements, each having type T.

  • Elements have indexes 0 through n - 1.

  • [] reads and writes vector values.

  • Vector accesses via [] are unchecked.

• Vectors are not like arrays.

  • The number of elements in a vector can change.

  • Vector relations are defined over the elements.

  • Vectors are not as time or space efficient as arrays.

• Vectors are dynamic, arrays are static.

  • Match the data characteristics to the data structure.

  • Changing or unknown data amounts: vectors.

  • Static and known data amounts: arrays.

Vector Definition

• A vector is a template class.

  • The template parameter gives the element type.

  • Also the allocator parameter, of which we will not speak.

• Any type can be an element type (almost).

  • C++ base types.

    std::vector<char> cvec;
    

  • STL containers.

    std::vector<std::vector<int> > ivec;
    

    Note the space in > >.

  • Reference types are not allowed..

    std::vector<int &> irefvec;
    

• typedefs help keep things neat and flexible.

  typedef std::vector<int> ivector;
  ivector ivec;
  std::vector<ivector> ivecvec;
  

Vector Constructors

• The default constructor creates an empty vector.

  std::vector<T> tvec;
  

• The size and value constructor creates an n-element vector with each element is equal to v.

  std::vector<T> tvec(n, v);
  

  • The value parameter v is optional if T has a default value.

    std::vector<int> tvec(n);
    

  • The default value is 0.

    std::vector<T> tvec(n);
    

  • T needs a default value (default constructor).

• The copy constructor copies one vector to another.

  std::vector<char> line2(line1);
  

  • The elements are copied, not shared.

• There are other constructors too.

Vector Element Access

• Vectors, like arrays, use operator[] to access elements.

  line2[0] = line1[10];
  

• An n-element vector has valid indices 0 through n-1 inclusive.

• And, like arrays, accessing vector values with [] is unsafe.

  std::vector<T> tvec(10);
  T t1, t2;
  t1 = tvec[100];  // compiles and executes, but is undefined
  t2 = tvec[-1];   // ditto
  

• .at() provides checked index access to vectors.

  • Throws an exception on invalid indices.

    std::vector<T> tvec(10);
    T t1, t2;
    t1 = tvec.at(100);  // run-time exception thrown.
    t2 = tvec.at(-1);   // ditto
    

  • Dealing with the at exception can be a pain.

.at() vs. []

• Prefer .at() to [] unless you're really sure.

  std::cin >> i
  
  // Terrible
  v[i] = ...	
  
  // Good
  v.at(i) = ...   
  
  // Much better.
  if (0 <= i) and (i < v.size())
    v[i] = ...    
  else
    std::cerr << "Invalid index...
  
  // Not a problem.
  for i = 0; i < v.size(); i++
    v[i] = ...
  

Growing and Shrinking Vectors

• The size() member function gives the number of elements in a vector.

  std::vector<T> tvec(10);
  assert(tvec.size() == 10); // it's true!
  

• Unlike arrays, vectors grow to hold more elements.

  • v.push_back(e) sets v[n] to e and n to n + 1.

    std::vector<int> v;
    assert(v.size() == 0); // it's true!
    int i = v[0]           // it's undefined!
    v.push_back(100);
    assert(v.size() == 1); // it's true!
    i = v[0]               // it's defined, and i == 100.
    

• Also unlike arrays, vectors can shrink. hold.

  • v.pop_back() removes v[n - 1] and set n to n - 1.

  • The element removed is not returned; it's lost.

    std::vector<int> v(1, 321);
    assert(v.size() == 1); // it's true!
    int i = v[0]           // it's defined and i == 321
    v.pop_back();
    assert(v.size() == 0); // it's true!
    i = v[0]	       // it's undefined!
    

Vector Storage Management

• What's the best way to add a million elements to an empty vector?

  Is it

  std::vector<int> ivec;
  
  for (i = 0; i < 1000000; i++)
    ivec.push_back(i);
  

• Like all STL containers, vectors manage their own storage.

• Unlike other STL containers, vectors let the programmers help manage storage.

Vector Growth

• A vector typically doubles in size when it's full.

  • Allocate a new, double sized array.

  • Copy the elements from the old to the new array.

  • Delete the old array.

• Copying a many-element vector can get expensive.

  • It can get real expensive when elements are classes with non-trivial copy constructors and destructors.

• Putting a million elements in an empty vector requires 20 doublings.

Vector Storage Management Functions

• There are four functions related to vector storage.

  • Two of the functions return information about a vector without changing the vector itself.

    • v.capacity() and v.size().

  • The other two functions change the vector.

    • v.reserve() and v.resize().

• Some of these functions have counter-intuitive meanings.

  • Make sure you understand what they really do.

Vector Storage Query Functions

• The query functions return information about a vector's size.

  • They do not change the vector.

• v.capacity() returns the total number of elements v can hold without resizing.

  • v.capacity() does not return the amount of empty space left in v.

• v.size() returns the number of elements actually in v.

  • size() is supported by all containers.

• v.size() <= v.capacity() is an invariant for any vector v.

  • If v.size() == v.capacity(), the next push back causes a reallocation.

Vector Storage Management Functions

• The management functions change a vector's size, adding or removing elements as necessary.

• v.resize(n) forces v to have n elements.

  • After v.resize(n), v.size() == n.

  • New (default) elements may be added or old elements may be deleted as necessary.

  • If v has n elements, v.resize(n) does nothing.

• v.reserve(n) insures v can hold at least n elements without a reallocation.

  • It may cause a reallocation itself, however.

  • After v.reserve(n), v.capacity() >= n.

  • v.size() remains unchanged.

Vector Relation Operators

• Relational operators on arrays apply to array addresses.

  char str1[14] = "Hello World!";
  char str2[14] = "Hello World!";
  // prints "true" or "false"?
  std::cout << (str1 == str2) << "\n";
  

• Relational operators on vectors apply to the elements.

  std::vector<int> ivec1;
  for (int i = 0; i < 5; i++) ivec1.push_back(i);
  std::vector<int> ivec2(ivec1);
  // prints "true" or "false"?
  std::cout << (ivec1 == ivec2) << "\n";
  

• v1 == v2 is true if and only if

  • Both vectors have the same size,

    v1.size() == v2.size()
    

  • and corresponding elements are equal.

    for (int i = 0; i < v1.size(); i++) 
      v1[i] == v2[i]
    

Vector Less-Than

• < is the lexicographic order over vectors.

  • Also known as dictionary order.

  • Which comes first: "hot" or "hotel"?

  • Which comes first: "boot" or "boat"?

  • Think "WWWD?" (what would Webster do?).

• The other relational operators (<=, !=, >, and >=) can be defined in terms of == and <.

Lexicographic Order

• v1 < v2 if

  • Either

    • An element of v1 is less than the same element of v2,

      v1[i] < v2[i]
      

    • and all previous elements in v1 are equal to the elements in v2.

      for (j = 0; j < i; j++) v1[j] == v2[j]
      

    • "boast" < "boot".

  • or

    • All elements of v1 are equal to the elements of v2,

      for (i = 0; i < v1.size(); i++) v1[i] == v2[i]
      

    • and v1 is shorter than v2.

      v1.size() < v2.size()
      

    • "hot" < "hotel".

Vector Type Definitions

• The vector std::vector<T> defines several types.

  • Essential for template functions and classes.

  • Improves code robustness, flexibility, and portability.

• std::vector<T>::value_type is the type of an element.

  • It's T.

• std::vector<T>::pointer is the type of an element pointer.

  • It's T * (usually).

• std::vector<T>::difference_type is the type of a value holding the distance between any two elements of a vector.

• std::vector<T>::size_type is the type of a value holding a vector's size.

Vector Miscellany

• Assignment v1 = v2 copies elements, it doesn't share them.

  • v1 and v2 sizes need not match.

  • This can be expensive for big vectors.

• v.empty() returns true iff v has no elements.

  • Get in the habit of using c.empty() instead of c.size() == 0.

  • For some containers .empty() is cheaper to call than is .size().

• v.clear() removes all elements from a vector.

• v.front() returns the first element of v.

  • v may be empty; behavior is undefined.

  • v.back() is defined similarly.

• std::swap(v1, v2) exchanges the elements of v1 and v2.

  • A cheaper assignment, assuming you don't need v2.

Points to Remember

• Vectors are like arrays, except when they're not.

  • Vectors are dynamic and expensive, arrays are static and cheap.

• Let the data determine the data structure.

  • dynamic or unknown amounts, or static and known amounts.

• Exploit checked vector access with .at().

  • Optimize with [] when index values are certain.

• Vector operations can be undefined without warning.

  • A proud C++ tradition.

• Vector relations work over elements, not addresses.

• Vector less-then is a lexicographic order.

  • Also known as dictionary order.

This page last modified on 6 February 2003.