Lecture notes for SE 598, Data Structures and Algorithms

Lecture Notes for SE 598, Data Structures and Algorithms

7 June 2000, STL Vectors

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. indexed access to vectors can be checked - running off the end
  2. the number of elements in a vector can grow and shrink
  3. relations between vectors are defined over vector elements
a vector is a template class
1. with template <class T, class Allocator = allocator>
2. because the Allocator template parameter has a default, and because we're ignoring allocators in this class, the vector template is just <class T>
3. 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;
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
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
```
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!
```
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 5 June 2000.