Advanced Programming II CS 509 Class Notes

Lecture Notes for Advanced Programming II

Outline

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

.size() returns 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.

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!

But shrinking's a bit more complicated than this.

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

And the Winner Is

Compiled on a Sparc Ultra10, 333 Mhz, 128 Mbytes.
Compiled with g++ version 3.2.3, no options.

Each code fragment iterated 10 times for an average.

Sub microsecond standard deviations in all cases

struct shred
  std::vector<int> edge1, edge2

int shred

vector<T> tvec for j = 0; j < vsz; j++ tvec.push_back(tval)
73 5534

vector<T> tvec(vsz) for j = 0; j < vsz; j++ tvec[j] = tval
509 4734

vector<T> tvec tvec.reserve(vsz) for j = 0; j < vsz; j++ tvec.push_back(tval)
71 3379

msec/iter

See the code.

	`int`	`shred`
vector<T> tvec for j = 0; j < vsz; j++ tvec.push_back(tval)	73	5534
vector<T> tvec(vsz) for j = 0; j < vsz; j++ tvec[j] = tval	509	4734
vector<T> tvec tvec.reserve(vsz) for j = 0; j < vsz; j++ tvec.push_back(tval)	71	3379
	msec/iter

Vector Shrinking, Revisited

Resizing a vector does not necessarily mean space is recovered.

std::vector<int> iv(10000, 0)
print(iv)
iv.clear()
print(iv)

iv.capacity() = 10000, iv.size() = 10000
iv.capacity() = 10000, iv.size() = 0

std::vector<int> iv(10000, 0)
print(iv)
iv.resize(0)
print(iv)

iv.capacity() = 10000, iv.size() = 10000
iv.capacity() = 10000, iv.size() = 0

The standard requires that .size() change, but .capacity() need not change.

Shrinking via Swapping

If you must, you can try the swap trick .
- c1.swap(c2) swaps the contents of containers c1 and c2.
- This is fast, due to pointer manipulation (mostly).

std::vector<int> iv(10000, 0)
print(iv)

{ std::vector<int> lamb
  print(lamb)
  lamb.swap(iv)    // or iv.swap(lamb)
  print(lamb)
  }

print(iv)

iv.capacity() = 10000, iv.size() = 10000

lamb.capacity() = 0, lamb.size() = 0

lamb.capacity() = 10000, lamb.size() = 10000

iv.capacity() = 0, iv.size() = 0

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 9 February 2004.