1. stl components

   1. containers - data structures

   2. generic algorithms - algorithms

   3. iterators - the link between containers and generic algorithms

2. containers

   1. sequence

      1. arrays - ordinary c++ arrays

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

3. generic algorithms

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

   2. lots more

4. iterators

   1. better called accessors

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

5. 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 <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 <

6. iterators

   1. iterators - analogous to pointers

      1. references to values in a sequence

      2. the unary * operator follows an iterator to its value

   2. random iterators

      1. all the operators for bidirectional iterators

      2. iterator-integer addition and subtraction

         1. x = *(itr + 5)

      3. addition- and subtraction-assignment += and -= for jumping around

         1. itr += 5

      4. iterator-iterator subtraction for finding distances between iterators

         1. cnt = end_itr - start_itr - 1;

         2. just as with pointers, the two iterators being subtracted must be from the same container for the subtraction to be meaningful - but the compiler doesn't (can't) check to make sure

      5. the < operator - does one iterator refer to a value earlier in the sequence than another iterator

   3. iterator ranges - (start, end),

      1. the end iterator refers to the value just past the end of the range

         1. standard C-C++ pointer practice

         2. the end iterator may point to a non-existent element

      2. only sensible if start and end refers to values within the same container

   4. from where do iterators come

      1. each container class defines its own iterator type

         1. vector<T>::iterator

         2. vector<T>::const_iterator

         3. there are others

      2. each container class has member functions that return iterators

         1. begin() - return an iterator to the first element in a container

            1. what does this do

                 vector<int> ivec;
                 vector<int>::iterator start = ivec.begin();
                 

         2. end() - return an iterator to the last element in a container

         3. vector<int>::iterator five = find(ivec.start(), ivec.end(), 5);

         4. there are others

This page last modified on 6 April 2001.