Vectors

Abstract Data Types (ADTs) example: Vectors. Also called "collections".

Vector: a data structure for representing lists.

Collection: an object that stores data, a.k.a. "data structure"

the objects stored are called elements
Also known as ADTs (abstract data types)

Standard Template Library (STL): C++ built-in standard library of collections: vector, map, list, ... Powerful but somewhat hard to use for new coders (messy syntax).

Stanford C++ library (SPL): custom library of collections

Vector, Grid, Stack, Queue, Set, Map, ...
Similar to STL, but simpler interface and error messages
Note the capitalized first letter (unlike STL)

Vectors (Lists)

#include "vector.h"

vector (aka list): a collection of elements with 0-based indexes

include the type of elements in <> brackets

//initialize a vector containing 5 integers
//        index   0   1   2   3  4V
Vector<int> nums {42, 17, -6, 0, 28};

Vector<string> names; // {}
names.add("abc"); //{"abc"}
names.add("xyz"); //{"abc", "xyz"}
names.insert(0, "ghi"); //{"ghi", "abc", "xyz"}

Arrays and comparison with vectors

C++ also has the notion of arrays with similar meaning as vectors:

int nums[5];
string names[3];
nums[0] = 32;
names[1] = "hello";

Some problems with C++ arrays:

Arrays have a fixed size and cannot be easily resized
- No way to know the size of the array just from the array variable. (e.g., no num.length())

C++ allows you to index out of the array bounds (garbage memory) without necessarily crashing or warning!

names[7] = "hello"; //this will not crash but will lead to unexpected behaviour
cout << names[7]; //prints garbage or crashes uncermoniously.

An array does not support many operations that you'd want:
- inserting/deleting elements into the front/middle/back of the array, reversing, sorting the elements, searching for a given value, ...

Discuss string vs. Vector<char>

Vector members

Member function name	Description
`v.add(value)` `v += value` `v += v1, v2, ..., vN;`	appends value(s) at end of vector
`v.clear()`	removes all elements
`v[i]` or `v.get(i)`	returns the value at given index
`v.insert(i, value);`	inserts a given value just before the given index, shifting subsequent values to the right.
`v.isEmpty()`	returns true if the vector contains no elements
`v.remove(i)`	removes/returns value at given index, shifting subsequent values to the left.
`v[i] = value` or `v.set(i, value);`	replaces value at given index
`v.subList(start, lentgh);`	returns new vector of subrange of indices
`v.size()`	returns the number of elements in vector
`v.toString()`	returns a string representation of the vector such as "{1, 3, 70, -8}"
`ostr << v`	prints v to given output stream (e.g., `cout << v`)

Example: Iterating over a vector

Vector<string> names {"ab", "cd", ef"};

for (int i = 0; i < names.size(); i++) {
  cout << names[i] << endl; //for loop: ab cd ef
}

for (int i = names.size() - 1; i >= 0; i--) {
  cout << names[i] << endl; //for loop backwards: ef cd ab
}

for (string name : names) {
  cout << name << endl; //"for-each" loop: ab cd ef
}
//cannot edit (insert/delete) in for-each loop.

Another example: insert/remove

v.insert(2, 42);

Shifts elements right to make room for the new element
Old vector

index  0  1  2  3  4
value  3  8  9  7  5

New vector

index  0  1  2  3  4  5
value  3  8 42  9  7  5

Similarly,

v.remove(1);

Shifts elements left to cover the space left by the removed element. Old vector

index  0  1  2  3  4  5
value  3  8 42  9  7  5

New vector

index  0  1  2  3  4
value  3 42  9  7  5

Efficiency? These operations are slower the more elements they need to shift.