Learning materials

Vector

On this page

Vector Definition

A vector is mostly a data structure as it is usually language specific.
A vector can be sometimes be treated as an ADT, when focusing on the data organization and behaviors only. Implementations are ignored.
Vector: A sequential ADT, similar to list ADT with some specific behaviors
Behaviors
- access by index
- insert remove by index
- add remove at the end
- check size/empty

C++ std::vector

A C++ implementation of the Vector ADT
An STL container
#include <vector>
vector is a class template, not a type! vector<int> is a class type
Based on a dynamic array internally
- fast access by indexing
- slow erase/insert in the middle
- may re-allocate memory when out of space (capacity)
  - create a larger array
  - duplicate/move all elements from existing array
  - delete the existing array
- resize
Variable length allowed
Out-of-boundary check with .at(n) method
automatic memory re-allocation
Methods
- Constructors
  - default: empty vector
  - (n): vector of size n, default values
  - (n, v): vector of size n, fill values as v
  - (aVectorOfSameType): copy another vector, must be same base type
  - {item1, item2, ...}: fill items from index 0
- Operator =
  - v1 = {1, 2, 3}: initializer_list assignment
  - v1 = v2: copy assignment
- at()
  - can assign value like v.at(0) = 10;
  - with boundary check. Triggers out_of_boundary exception
  - preferred over [] syntax
- clear() clear the content
- empty() check empty
- size()
- push_back()
  - push the value as the last element
  - does not return value
- pop_back()
  - removes the last element
  - does not return value! Be careful! Many pop methods in other languages returns a value.
- back()
  - returns the value of the last element
- resize()
  - may or may not re-allocate memory
  - does not erase data if downsized
- find() find an element by value, returns an iterator
- insert() requires the use of iterators
- erase() requires the use of iterators

Initialization

When the braces are used, the initialization will use the values as items. Must use parentheses when triggering other constructors.

vector<int> v{1, 2, 3, 4, 5} size 5 vector with values
vector<int> v = {1, 2, 3, 4, 5} size 5 vector with values, preferred for sequence initialization
vector<int> v(5) size 5 vector with 0s, v{5} will make a size 1 vector
vector<int> v(5, 1) size 5 vector with 1s, warning: v{5, 1} will make a size 2 vector instead
vector<int> v1(v) make a copy of v

C++ Iterator Type (Extended reading)

In C++, an iterator is an object that enables traversal through the elements of a container, such as a vector, list, or map, without exposing the underlying implementation of the container. Iterators provide a consistent interface to access and modify the elements of a container, regardless of the specific container type. They allow for efficient manipulation of container elements by providing methods for moving between elements, accessing the value at the current position, and modifying the value at the current position. Iterators are an essential tool for generic programming in C++ and allow for efficient, type-independent algorithms to be written for a variety of container types.

A derived type of STL containers such as vector, list, map, etc.
- e.g. vector<int>::iterator is used to iterate through a vector of int.
- May use auto to simplify the type declaration: auto it = v.begin();
Vector methods using iterator
- begin() returns an iterator pointing to the first element
- end() returns an iterator pointing to the element after the last element
- erase(iterator) removes the element at the iterator position and returns the iterator pointing to the next element
- insert(iterator, value) inserts the value before the iterator position and returns the iterator pointing to the inserted element
Functions using iterators
- find(begin, end, value) returns an iterator pointing to the first element that matches the value in the range defined by a beginning iterator and an ending iterator. It return the end iterator if not found.

Example:

vector<int> v = {1, 2, 3, 4, 5};
vector<int>::iterator it = find(v.begin(), v.end(), 3);
it = v.erase(it);  // remove the element at the iterator position, returns
                  // the iterator pointing to the next element

Passing vector around

As parameter

by-value (object duplication): void func1(vector<int> vec);
read-only reference: void func1(const vector<int> &vec);
by-reference (allow modifications of the actual parameter): void func1(vector<int> &vec);

example:

// Assume that the Patient class is ready for use
// read data from a csv file and create the vector of Patient objects
loadData(vector<Patient> &patients, string filename);

class TextMenuApp {
  vector<Patient> &patients;  // takes a reference to avoid copy overhead
 public:
  TextMenuApp(vector<Patient> &patients): patients(patients) {}
  void run();
  // ...
};

int main() {
  // Only one vector is created in the scope of the main function
  // Its reference is passed around
  vector<Patient> patients;
  loadData(patients, "patients.csv");
  TextMenuApp app(patients);
  app.run();
  return EXIT_SUCCESS;
}

As returned value
- return by value (object not necessary duplicated, some optimization will happen)
- see the filter example

Algorithms

Works with all algorithms on arrays
- change arr[i] to vec.at(i)
- no longer need to pass a separate size variable

Particularly good for out-of-place algorithms with variable length output

filter type of algorithm, i.e. find all positive value in a vector:

vector<int> positiveOnly(const vector<int> &v) {
  vector<int> result;
  for (int i = 0; i < v.size(); ++i)
    if (v.at(i) > 0)
      result.push_back(v.at(i));
  return result;
}

Pitfalls

use [] rather than at()
int a = v.pop_back(); should be int a = v.back(); v.pop_back()
cout << v.length(); Wrong! There is no length() method
if (v.size() == 0) this works but better use if (v.empty())

Extended Readings

Use .emplace_back() with object vector
Use for each loop with vectors