Discussion topics

Week of Jan 29th

Notion of "iterator" and implications:

This is intented as a very brief presentation of some of the notions you should understand regarding the STLs. Your GSI will develop a lot more on these notions than what this outline does.

1. Iterators: what do we need them for?

Example:
void myFunction(int* i);

int myArray[100];

myFunction(&myArray[12]); //how do I do that, if the data structure is not an array ?

//how do I do the following, if the datastructure is not an array ?
for(int i = 0; i < 100; i++)
myFunction(&myArray[i]);

A way to see iterators: generalized pointers.

2. Not all iterators allow all possible kinds of manipulations

Input Iterator
Output Iterator
Forward Iterator
Bidirectional Iterator
Random Access Iterator

3. Iterators permits to define ranges

a. Concept of sequential container (Forward containers)

In some containers (vectors, lists, deques...) the elements are stored in an order which does not spontaneously evolve.

b. That means, with two iterators, one can delimit a subset of the elements in the container on wich to perform operations

Ex1: 
How would you translate the following example if the structure was not an array but a list from the STLs ?

void myFunction(int* i);
int myArray[100];
for(int i = 12; i<20; i++)
	myFunction(&myArray[12]);

Ex2: One could use the sort function from the STLs to sort a range of data inside a data structure.

3. So, we can easily obtain sorted ranges of data: what next ?

The fact of having the data sorted allow a reduction in the complexity of some useful operations:
Ex: Use Binary Search instead of a dumb Linear Search.

Note that, in the STLs, there is lot of flexibility regarding searches: you could search for an element that has a given value, you could also search for an element that verifies a binary predicate