```// -*- mode: c++ -*-
// (set-default-font (format "-xos4-terminus-bold-*-*-*-24-*-*-*-*-*-*-*"))

/*

STL Continued
=============

2007.12.06.

http://ortros/~salvi/stl/

Overview
--------
1) Iterator
2) List
3) Priority Queue
4) Associative Containers
5) Choosing the Correct Container
6) Algorithms
7) Hands-on Exercises
8) Bibliography

*/

-------------------------------------------------------------------------------

// 1. Iterator

// In C, we used arrays with pointers.
// In C++, we use containers with iterators.
// Most member functions and algorithms rely on iterators,
// they form the core of STL.

// Iterators are classified into five categories:
// Input < Forward < Bidirectional < Random Access, and Output

// So a Forward iterator is an Input iterator,
// and a Bidirectional iterator is a Forward iterator, and so on.
// Output iterators are like the space between two elements.

// With iterators, you can:
// - read/write the current element (*iterator), if it is Input
// - go to the next element (iterator++), if it is Input
// - go to the previous element (iterator--), if it is Bidirectional
// - go to any element (iterator + n), if it is Random Access
// - insert elements, if it is Output

// Its type is Container::iterator or Container::const_iterator:
std::vector<double> v;
v.push_back(1); v.push_back(2); v.push_back(3);

std::vector<double>::iterator it;
std::vector<double>::const_iterator const_it;

// Every container has two member functions that give us the place (iterator)
// of first element and the place after the last element: begin() and end().

// A loop through the elements of a vector can be written like
for(std::vector<double>::const_iterator i = v.begin(); i != v.end(); ++i) {
std::cout << *i << " ";       // Prints "1 2 3 "
}

-------------------------------------------------------------------------------

// Forward iterators can be moved n times using advance:
std::advance(iterator, 3);      // = ++iterator; ++iterator; ++iterator;

// Random access iterators can also be subtracted, thus we can
// calculate the distance between two elements.

v.end() - v.begin();            // = v.size() = 3

// Some examples:

typedef std::vector<double> DVec;
typedef DVec::iterator DVecIt;
DVecIt i = v.begin();
std::cout << *i;                // prints 1
++i;
std::cout << *i;                // prints 2
std::cout << v.end() - i;       // prints 2
std::cout << i - v.begin();     // prints 1 (we are now at v)
i += 2;
std::cout << *i;                // undefined (we are at v.end())

// There are also other iterator types, e.g.:
// reverse_iterator (goes backwards)
// istream_iterator (input for streams)
// ostream_iterator (output for streams)

// Output iterators are important, because many algorithms use them.
// For a container, they can be created using std::inserter & co:
std::inserter(v, iterator);  // iterator points to an element in v, uses insert
std::front_inserter(v);      // = std::inserter(v, v.begin()), uses push_front
std::back_inserter(v);       // = std::inserter(v, v.end()), uses push_back

// For example, the loop that prints all elements can be written like this:
std::copy(v.begin(), v.end(), ostream_iterator<double>(std::cout, " "));
// (don't worry if you do not understand this yet :)

-------------------------------------------------------------------------------

// 2. List

// List is a doubly linked list, very similar to deque in use, but it has
// no random access operator (operator[] or at()).

#include <list>

std::list<int> l;

// Standard container functions:
l.front(); l.back();            // the first and last element
l.empty();                      // is the list empty?
l.clear();                      // empty the list
l.size();                       // the size of the list
l.push_front(1); l.push_back(2);// put 1 at the start and 2 at the end
l.pop_front(); l.pop_back();    // remove the first / last element
l.swap(another_container);      // swap the contents with another container

// Special member functions:
l.reverse();                    // reverses the order of the elements
l.sort();                       // sorts the list in ascending order
l.sort(&sorting);               // sorts the list by the function sorting()
l.splice(position, other_list); // inserts another list at a given position
l.merge(other_list);            // merges with another list in ascending order
l.merge(other_list, &sorting);  // merges with another list by sorting()
l.unique();                     // leaves only one of consecutive same elements

// For example, if l = [1, 2, 3, 3, 2, 4, 3], unique gives [1, 2, 3, 2, 4, 3].

-------------------------------------------------------------------------------

// 3. Priority Queue

// STL has a few more containers, called "container adapters",
// like stack, queue, ... and priority_queue.
// These are "container adapters", because they use other containers.
// We can even specify (with a template parameter) what container to use.

// Priority queues have their elements sorted by a sorting function-object
// (which is a template parameter as well, defaults to std::less).

#include <queue>

std::priority_queue<int> pq;
std::priority_queue<int, std::vector<int>, std::greater<int> > pq2;

pq.empty();                     // is pq empty? => true
pq.push(4); pq2.push(4);        // put 4 in the queues
pq.push(2); pq2.push(2);        // put 2 in the queues
pq.push(3); pq2.push(3);        // put 3 in the queues
pq.top(); pq2.top();            // the highest priority elements => 4 and 2
pq.pop(); pq2.pop();            // take out one element from both queues
pq.size();                      // the size of pq => 2
pq.top(); pq2.top();            // the highest priority elements => 3 and 3

// For more interesting examples, we must create a struct for comparing.

// Why do we need a struct? Because template arguments cannot be functions.
// They can be values of "simple types" (like 3 or 5.6 or true) and types.

// As a workaround, we can create a type with operator() and it will behave
// as a function, but it still can be passed as a template argument.

-------------------------------------------------------------------------------

// Let's create a simple type and a comparing struct for it:

struct MyType {
int priority;
std::string data;
MyType(int p, std::string d) : priority(p), data(d) { }
};

/*
Constructor(arg1, arg2, ...) : var1(arg1), var2(arg2), ... { ... }

is just another way of saying

Constructor(arg1, arg2, ...)
{
var1 = arg1;
var2 = arg2;
...
}
*/

struct MyTypeLess {
bool operator() (MyType const &a, MyType const &b) const
{
return a.priority < b.priority;
}
};

std::priority_queue<MyType, std::vector<MyType>, MyTypeLess> pq3;

pq3.push(MyType(4, "four"));
pq3.push(MyType(2, "two"));
pq3.push(MyType(3, "three"));
std::cout << pq3.top().data << std::endl; // Prints "four"

-------------------------------------------------------------------------------

// 4. Associative Containers

// Associative containers can be sets or maps, they can be hashed and can have
// multiple values. So we have 8 types (all combinations):
// set/map, multiset/multimap, hash_set/hash_map, hash_multiset/hash_multimap
// (hashing is a way to make element lookup faster, we won't discuss it today)

// Associative containers are always sorted, like priority queues. The sorting
// is based on a key.

// Sets are the simplest associative containers, they only contain a key.
// Sets can only contain one element once. Multisets group the equal values.
// The sorting "function" is a template parameter.

#include <set>
std::set<MyType, MyTypeLess> s;
std::multiset<MyType, MyTypeLess> ms;
s.insert(MyType(1, "one"));  ms.insert(MyType(1, "one"));
s.insert(MyType(1, "ichi")); ms.insert(MyType(1, "ichi"));
s.insert(MyType(2, "two"));  ms.insert(MyType(2, "two"));
s.insert(MyType(1, "one"));  ms.insert(MyType(1, "one"));
//  s = [(1, one), (2, two)]
// ms = [(1, {one, ichi, one}), (2, {two})]

// Maps and multimaps store key/value pairs.
// Maps have a shorthand notation for searching and insertion: operator[]

// std::pair<Type1, Type2> contains two public variables: first and second.
// New pairs can be created with std::make_pair(value1, value2).

#include <map>
std::map<std::string, std::string> m;
m["ichi"] = "one";              // m.insert(std::make_pair("ichi", "one"));
m["ichi"] = "ein";              // m.find("ichi")->second = "ein";

-------------------------------------------------------------------------------

// Associative containers have a different set of "standard operations":
a.empty();                      // is the container empty?
a.clear();                      // empty the container
a.insert(element);              // insert an element
a.erase(position);              // erases an element
a.size();                       // the number of elements
a.count(key);                   // the number of elements with the given key
a.swap(other_container);        // swap the elements with another container
a.find(key);                    // an iterator to the element (or end())
a.lower_bound(key);             // an iterator to the first element that is >=
a.upper_bound(key);             // an iterator to the last element that is <=
a.equal_range(key);             // a pair of iterators: to the first element
// with the given key, and to the next element
// after the last with the given key

typedef std::multiset<MyType, MyTypeLess> MyMSet;
MyMSet ms;
ms.insert(MyType(0, "zero"));
ms.insert(MyType(2, "two1"));
ms.insert(MyType(2, "two2"));
ms.insert(MyType(2, "two3"));
ms.insert(MyType(4, "four"));
// After this, ms = [(0, {"zero"}), (2, {"two2"/"two1"/"two3"}), (4, {"four"})]
// Note that the order of two1, two2 and two3 is implementation-dependent.

ms.upper_bound(MyType(0, ""));  // an iterator to the first "two" ("two2" now)
ms.lower_bound(MyType(2, ""));  // an iterator to the first "two" ("two2" now)
ms.lower_bound(MyType(3, ""));  // an iterator to "four"
ms.upper_bound(MyType(3, ""));  // an iterator to "four"

MyType element(2, "");
std::pair<MyMSet::iterator, MyMSet::iterator> p = ms.equal_range(element);
p.first;                        // an iterator to the first "two" ("two2" now)
p.second;                       // four

-------------------------------------------------------------------------------

// 5. Choosing the Correct Container

/*

First let's do a short review on vectors.

Vector
======
____________________________________|___________________________________
|     |     |     |     |     |     |     |     |     |     |     |     |
|  1  |  2  |  3  |  4  |  5  |  6  |  X  |  X  |  X  |  X  |  X  |  X  |
|_____|_____|_____|_____|_____|_____|_____|_____|_____|_____|_____|_____|
|
Let this be the contents of an std::vector v.
Then v.size() => 6 and v.capacity() => 12 (the length of the reserved memory).

If we insert an element at the back, the next X is replaced with the new
element, and the size grows with 1. New memory is allocated when necessary.

We can change the size/capacity with two functions:
v.reserve(n) => Ensures that v.capacity() >= n. Doesn't change the size.
v.resize(n) => Ensures that v.size() = n (and v.capacity() >= n, of course).

Every change in the capacity requires memory allocation, and may require the
copying of all elements in the vector.

Operation speed
---------------
1) v.push_back() : fast (constant), except when v.size() == v.capacity()
2) v[i]          : fast (constant)
3) v.insert(...) : very slow (linear copying), except at the end
4) v.erase(...)  : very slow (linear copying), except at the end
5) searching     : slow (linear)

Note that deque has the same properties, but it is fast on both ends.

*/

-------------------------------------------------------------------------------

/*

Let's look at the operations of lists now.

List                                _____
====                            .->/     \___
/  _|  7  |   \
| / \_____/<. |
| |         | |
_____       _____       _|_V_       _|_V_       _____       _____
/     \ --> /     \ --> /     \ --> /     \ --> /     \ --> /     \
|  1  |     |  2  |     |  3  |     |  4  |     |  5  |     |  6  |
\_____/ <-- \_____/ <-- \_____/ <-- \_____/ <-- \_____/ <-- \_____/

Operation speed
---------------
1) l.push_back() / l.push_front() : fast (constant)
2) l[i]                           : N/A
3) l.insert(...)                  : slow (linear)
4) l.erase(...)                   : slow (linear)
5) searching                      : slow (linear)

Associative Containers
======================

Operation speed
---------------
1) a.push_back() : N/A
2) a[i]          : N/A
3) a.insert(...) : quite fast
4) a.erase(...)  : quite fast
5) searching     : quite fast (only for keys in maps)

*/

-------------------------------------------------------------------------------

/*

Conclusion
==========

|-------------+-----------------------------------------------------------|
| TYPE        | BEST USAGE                                                |
|-------------+-----------------------------------------------------------|
| Vector      | Random access and inserting mainly at the end             |
|-------------+-----------------------------------------------------------|
| Deque       | Random access and inserting mainly at both ends           |
|-------------+-----------------------------------------------------------|
| List        | Linear handling (e.g. from start to end), many insertions |
|-------------+-----------------------------------------------------------|
| Associative | Searching for values often                                |
|-------------+-----------------------------------------------------------|

*/

-------------------------------------------------------------------------------

// 6. Algorithms

// STL has a lot of algorithms, implemented very efficiently.
// Here I only list the names of the most important ones, details
// can be found in any STL reference (see Bibliography).

// Most functions can have more (optional) parameters as well.
// Ranges are given in the form [first, last)

// Call function for all x in a range:
std::for_each(first, last, &function); // function is a UnaryFunction
// Find a value in the specified range:
std::find(first, last, value);
// Count the number of elements equal to value:
std::count(first, last, value);
// Compare two ranges if they are equal, in an element-to-element sense:
std::equal(first1, last1, first2);
// Copy a range to a specified place:
std::copy(first, last, result); // result is an output iterator
// Swap two values:
std::swap(a, b);
// Remove value from a range:
std::remove(first, last, value);
// Replace old_value with new_value in a range:
std::replace(first, last, old_value, new_value);
// Fill a range with values generated by invoking a function:
std::generate(first, last, &function); // function is a Generator
// Minimum/maximum of two values:
std::min(a, b); std::max(a, b);
// Minimal/maximal element in a range:
std::min_element(first, last); std::max_element(first, last);

// ... and a lot more, e.g.:
// reverse, rotate, sort, lower_bound, upper_bound, equal_range, merge, etc.

-------------------------------------------------------------------------------

// 7. Hands-on Exercises

/*
Do these exercises now (you can ask me if something is not clear)
If there is not enough time, the rest is homework.

A testing C++ file is available at:
http://ortros/~salvi/stl/exercises.html

1) Write a function "add_subtract" that takes a list of int/double
pairs. The first values are all different, they form the order of
application. The function should add/subtract their second values
interchangebly.

Example: [(1, 2.3) (3, 4.1) (5, 5.0) (2, 1.0), (4, 2.9), (9, 7.0)]
Result : 2.3 - 1.0 + 4.1 - 2.9 + 5.0 - 7.0 = 0.5

Hint: You can use a priority queue or std::sort.
(do both for more practice :)

2) Write a function "minimum_value" that takes a multiset of int/std::string
pairs. The function should return a map that maps every int to its
minimal pair.

Example: [(1, {"dog", "cat", "dragon"}) (25, {"tiger", "mouse"})]
Result : [(1 -> "cat") (25 -> "mouse")]

Hint: std::equal_range is your friend.
Also, upper_bound(*iterator) gives the iterator with the next key.

*************************
* That's all for today! *
*************************

*/

-------------------------------------------------------------------------------

// 8. Bibliography

/*

For an extensive function reference, see
- http://www.sgi.com/tech/stl/
- http://cppreference.com/
- http://www.cplusplus.com/reference/
- ... and of course, the include files.

The following books contain very good learning materials:

- N. M. Josuttis: The C++ Standard Library: A Tutorial and Reference,
Addison-Wesley, 1999.
- D. R. Musser, G. J. Derge, A. Saini: The STL Tutorial and Reference Guide:
C++ Programming with the Standard Template Library, Addison-Wesley,
2nd Edition, 2001
- S. Meyers: Effective STL: 50 Specific Ways to Improve Your Use of the
Standard Template Library, Addison-Wesley Professional, 2001.
- B. Karlsson: Beyond the C++ Standard Library: An Introduction to Boost,
Addison-Wesley Professional, 2005.

*/
```