Lecture Notes for Advanced Programming II

5 February 2002 - STL Vectors

1. the standard template library - stl

2. stl components

   1. containers - data structures

   2. generic algorithms - algorithms

   3. iterators - the link between containers and generic algorithms

3. containers - sequential and sorted associative

   1. sequence

      1. arrays - ordinary c++ arrays

      2. vector - an array that can grow on one end

4. generic algorithms

   1. find(start, end, item) - look for item in the container part delimited by start and end.

   2. lots more

5. iterators

   1. better called accessors

   2. how do algorithms get at the contents of a container - via the iterators provided by each container

6. stl vectors

   1. behavior

      1. vectors are like arrays

         1. a sequence values, each value having type T

         2. values are indexed by the number 0 through n - 1 using []

         3. values can be read from and stored into vectors

         4. vector accesses are unchecked

      2. vectors are not like arrays

         1. the number of elements in a vector can grow and shrink

         2. relations between vectors are defined over vector elements

   2. a vector is a template class

      1. with template tmplt(class T)

      2. the template parameter T gives the type of the values stored in the vector

         1. for example

            1. vector<char> cvec;

            2. vector<vector<char> > cvecs;

         2. typedefs are helpful

            1. typedef vector<char> cvector;

            2. cvector cvec;

            3. vector<cvector> cvecs;

   3. vector constructors

      1. the default constructor - creates an vector containing no values

         1. vector<T> tvec;

      2. the size and value constructor - build an n-value vector, each value is equal to v

         1. vector<T> tvec(n, v);

      3. the value parameter v is an optional parameter - the default value is the constructor for v's type

         1. vector<T> tvec(n);

         2. vector<int> tvec(n);

      4. the copy constructor - copies one vector to another

         1. vector<char> line2(line1);

      5. there are other constructors too

   4. reading and writing values

      1. vectors are like arrays - use [] to access vector values

         1. line2[0] = line1[10]

         2. for an n-element vector, the valid indices are 0 through n-1 inclusive

      2. but, like arrays, accessing vector values with [] is unsafe

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

   5. growing and shrinking vectors

      1. the size() member function gives the number of values held by a vector

           vector tvec(10);
           assert(tvec.size() == 10); // it's true!
           

      2. unlike arrays, vectors can hold an unlimited number of values

         1. given an n-element vector v, the call v.push_back(e) adds the element e as the n+1-element of v

              vector<int> tvec(10);
              assert(tvec.size() == 10); // it's true!
              tvec.push_back(100);
              assert(tvec.size() == 11); // it's true!
              

      3. also unlike arrays, vectors can decrease the number of values they hold

         1. given an n-element vector v, n > 0, the call v.pop_back() removes and throws away the nth element of v

              vector<int> tvec(10);
              assert(tvec.size() == 10); // it's true!
              tvec.pop_back();
              assert(tvec.size() == 9); // it's true!
              

   6. vector relation operators

      1. relational operators applied to arrays are usually unhelpful because the operators apply to array addresses

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

      2. unlike arrays, relational operators applied to vectors apply to the contents of the vectors, which is usually what is wanted

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

      3. the vector member operator == is defined as: v1 == v2 is true if and only if

         1. v1.size() == v2.size() and

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

      4. the vector member operator < is defined as: v1 < v2 is true if and only if

         1. v1.size() < v2.size() and

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

         3. this is known as lexicographic order

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

This page last modified on 21 February 2002.