Skip to main content

STL Containers

Focuses on Vector, List, Map

Template class means that the class can store item of any type

How to use ?​

#include <vector>
using namespace std;
int main() {
  vector<string> v;        // instantiate an STL container object
  v.pushback("hi");
}

Copying STL Containers​

/*
set v1.size() = v2.size()
copy the content from one to another
therefore, change in v1 later won't affect v2
same for list/ map/ vector
*/
int main() {
  vector<string> v1;
  vector<string> v2;
  v1.append("hello");
  v2 = v1;
}

Vectors​

linear array of items (implemented using array)

Main features​

void push_back(item);      // append to the back
int size();                // get the size
item operator[int index];  // access item 
void pop_back();           // remove last item in vector

Lists​

Doubly Linked List

Main features​

void push_back(item);         // insert item to the back
void pop_back();              // remove item from the back
void push_front(item);        // insert item to the front
void pop_front();             // remove item to the front
reference front();            // access the first item
reference back();             // access the last item
int size();                   // get size

Maps​

Balanced BST, stores a set of <key, value> pairs

Main Features​

map<k, v> m;
m[k1];       // return item with key k1, if not exist return 0
m.count(k1); // return 0 if no item with key k1, else 1
m.size();    // return the size
m1 = m2;     // copy the map

In a BST, the value of each node have to be different for searching. Custom comparator is needed when we use custom classes as the compiler do not know how to compare user-defined classes.

Using User-defined Classes as KEY​

  • custom comparator required 
// Overloading before main()
// const - value won't change in the function
// & - pass by ref is faster
bool operator<(const Obj& a, const Obj& b) {
  return a.data < b.data;
}