STL Iterators

Iterators are classes defined by STL for indexing items. It is an object that works like pointer.

Declaration

/*
specify container, type, followd by scope resolution operator (::)
means "declaring an iterator which belongs to vector of a type"
*/
vector<type>::iterator itr;

Usage

/*
container.begin() returns an iterator pointing to the beginning of container
*/
vector<int> v;
// our iterator "itr" points to the beginning of v
vector<int>::iterator itr = v.begin();

Traversal

List & Vector

suppose we have a vector v: [1, 2, 3, 4] and we want to print out its content

vector<int>::iterator itr = v.begin();
for (int i = 0; i < v.size(); i++) {
  cout << *itr << ' ';
  itr++;
}

OR

vector<int>::iterator itr;
for (itr = v.begin(); itr != v.end(); itr++) {
  cout << *itr << ' '; 
}

Map

map<int, int>::iterator itr;
for (itr = m.begin(); itr != m.end(); itr++) {
  cout << (*itr).first << ' ' << (*itr).second << endl; // prints key and then value
}

Types of Iterator

Type of iterator depends on which the iterator is pointing to

Forward Iterator

features	example
Assignment	a = b
Increment	a++
Dereference	*a
Equality test	a == b

Bidirectional Iterator (list or map)

features	example
All features of forward iterator
Decrement	a--

Random Access Iterator (vector)

features	example
All features of bidirectional iterator
Arithmetics	a + 5; a - 5
Inequality test	a < b;
Compound	a += 5;
Offset dereference	a[5] i.e. *(a + 5)

Iterators VS Pointers

Pointer is the memory address, iterator is not an address but an object

When we increment pointer, increase the memory adress by one item; When we increment iterator, it move to next item in the container

Sorting Vectors

Sort Class

STL sort only works with items with random access - i.e. array & vector (which is array based)

void sort (RandomAccessIterator first, RandomAccessIterator last);

Usage

#include <vector>
#include <iostream>
// include the algorithm lib
#include <algorithm>
using namespace std;
int main() {
  vector<int> nums;
  for (int i = 10; i > 0; i--) {
    nums.push_back(i);
  }
  sort(nums.begin(), nums.end());
  // we can also sort particular range
  // sort(nums.begin() + 1, nums.end() - 1);  
  vector<int>::iterator itr;
  for (itr = nums.begin(); itr != nums.end(); itr++) {
    cout << *itr << endl;
  }
}

Custom Comparator

use custom comparator for custom class/ struct to let the compiler know what to compare

bool operator <(const obj& a, const obj& b) {
  return a.price < b.price;
}

Sorting Arrays

#include <algorithm>
#include <iostream>
/*
STL converts integer pointer to random access iterator
Sort only works with random acess iterator
*/
using namespace std;
int main() {
  int nums[] = {5, 4, 3, 2, 1};
  sort(nums, nums + 5);
}