:: Intro to STL ::

I) What is this?
	A) Standard Template Library: A number of structures and algorithms that implement commonly needed things in programming, designed to work with basic and abstract data types.
	B) Containers: data structures designed to contain multiples of other data structures.  eg: lists, trees, etc.
	C) Algorithms: Various algorithms designed to operate on containers.  Sorting algorithms are the most constantly used of these.
	D) Iterators: A pointer-like structure designed to uniformly access elements inside of a given container.  Can be manipulated just like pointers (dereference, arithmetic, etc.)
	E) Effectively, abstracts the data layer from the control layer.  Allows for greater encapsulation!

II) Why do we want to use it?
	A) Laziness! Programmers are lazy by nature.  We write automated tools to do things that would otherwise take a lot of repetitive labor.
	B) Helps build applications faster.  Don't have to continually rebuild basic ADT's like trees, etc.
	C) Encourages good sofware practices, eg: re-use, portability, readability, and speed.
	D) STL code is optimized heavily for speed, within the parameters of it's use.  eg: you definitely couldn't do better, so why try? ;-)
	E) Does all storage structuring by value, not by reference.  Useful because it keeps people from screwing up memory allocation.
	F) To a lesser degree, complexity guarantees.  eg: with iterators, you can search through a list in constant time, else you need polynomial time to hit all elements.
	G) Written with only best performance in mind.  An operation won't be implemented if it will perform poorly on average.

III) STL Basics
	A) Before we get started...
		1) Conventions
			a) 'using namespace std;' 
				i) Some people dislike this because "it pollutes the global namespace".  However, I will not bore you with semantics, and for simplicities sake, we'll avoid such pedantry.  In the code examples, assume we have 'using namespace std;'
			b) Brace standards
				i) I don't have any real opinion on this, except that the default emacs bracing sucks.
			c) Comments
				i) I'm going to use this moment to harp on you about writing USEFUL comments.  Try reading code you wrote last year.  If your comments still make sense and you can figure out what your program is doing, you're on the right track.
			d) Pre vs post increment
				i) When working with iterators and pointers, using pre-increment (eg: --Itr or ++Itr) is preferred.
				ii) Why: post-increment involves creating a copy of the original object, so preincrement might yield better performance, compiler dependent of course.
			e) Use of typedef
				i) When making frequent use of a data type or iterator declaration, typedef's create more readable code.
				ii) instead of writing priority_queue<string, dequeue>::iterator Itr; everywhere, try: typedef priority_queue<string, dequeue>::iterator StrPriQItr; and make your iterators with StrPriQItr itr1; for example.
		
		2) Scoping operator '::'
			a) example: std::string::iterator Itr;
				i) 'std' tells us the base namespace for the iterator
				ii) '::' indicates the next identifier will reference the 'std' namespace
				iii) 'string' is the container type
				iv) '::' tells us the next identifier will reference the 'string' container class
				v) 'iterator' says we're creating an STL 'string' iterator
				vi) 'Itr' is the identifier we'd use to reference the iterator
				
		3) Template Syntax: <template identifier>
			a) Special note: The use of white-space is incredibly important in template declarations!  Improper whitespace could confuse the parser, since >> and << are operators!
				i) set<int, greater<>> is a syntax error, but set<int, greater<> > is not.  ;-)
			b) example: int foo(<template T>) {};
				i) 'int' specifies the return type of the function
				ii) 'foo' is the function name
				iii) '<template T bar>' tells the compiler that it will generate a template function, with 'T' to be used as the type declaration, and 'bar' as the identifier.
				
		4) Note that STL works ENTIRELY in pass by value for inserts and assignments.
			a) What this means: make a functional copy constructor! (See CS12/CS14 lectures! :))
			b) Uses more memory than pointer manipulation.
			c) Significantly easier/safer than pointer manipulation however.
				
	B) Introduction to STL containers, adapters, iterators and algorithms

		1) Containers
			a) C++ string (yes, this is part of the STL!)
				i) include: <string>
				ii) declaration: [std::]string identifier;
				iii) Basic functions & operators
					1) stream I/O: <<, >>
					2) Arithmetic: + (note the lack of subtraction.  Special functions are provided for removal/replacement)
					3) Logical: == (can compare strings, '<' and '>' useful primarily with single characters.  '==' works with any length string)
					5) Access: [], go to a specific character in the string.
					6) Assignment: =, += (the latter useful for string concatenation)
					6) Compatability: c_str(), returns a const char * pointer
						*) used to work with all the old-school C libraries (except strtok(), which modifes the original string)
						*) Warning: do NOT deallocate memory using the pointer returned by c_str().
				iv) Performance:
					1) Simmilar to vector (Below).
				v) Works like a regular array of characters!
					1) Access to elements using subscript.
					2) Overloaded insertion and extraction operators.
					
			b) vector
				i) include: <vector>
				ii) declaration: vector<type[, allocator]> identifier[(int)]
				iii) type is the base/AD type you want to store.
				iv) Optional: allocator is the method of internal memory management. (Beyond our scope, see http://www.sgi.com/tech/stl/Allocators.html)
				v) Optional: passing in an int to the constructor tells the class how many elements to make space for during initial allocation.
				vi) Basic functions & operators
					1) 'push_back(identifier)' makes a copy of the data, and pushes it onto the back of the vector.
						note: It would be wize then to call 'delete' on any dynamically created memory after it's pushed.
					2) '[int]' operates just like standard C arrays.
					3) at(int), the functional equivalent of subscript [].
					4) capacity(), returns how many elements have been pre-allocated.
					5) reserve(int), pre-allocates memory for n number of elements.  Affects only capacity(), not size().
						i) useful to prevent the first few (hundred) resizes of adding a large number of elements to a vector
 
				vii) Performance
					1) For insert()'s/erase()'s at the end, fast. (constant time)
					2) For inner elements, linear time. (slower)
					3) Vector's allocate 2x the amount of memory they're currently using on an insert to reduce the overhead of constant assignments. (See reserve() above)
						*) because vectors are kept in linear memory segments (like arrays), on expanding capacity, a suitable contiguous block of memory must be available.  Slows insertion on already slow architectures.
					
			c) deqeue
				i) Pronounced "Deck", like the wood flooring outside your mom's house
				ii) Short for "Double Ended Queue"
				iii) It's internal structures are designed to facillitate fast addition/removal to either end of the queue (hence the "double ended").
				iv) include: <dequeue>
				v) declaration: dequeue<type> identifier;
				vi) Basic functions
					1) push_back(identifier), adds an element to the back of the dequeue
					2) push_front(identifier), adds an element to the front of the dequeue
					3) [int], accesses a specific random element in the dequeue (like vectors and arrays)
					4) pop_front(), removes an element from the front of the deqeue (note: does NOT return that element!)
					5) pop_back(), removes from back of deqeue
				vii) Performance
					1) same as a vector, but insert()'s/erase()'s at beginning are also constant time.
				viii) unlike vector, no reserve() or capacity() function, and no subscript [].
					
		
			d) [s]list
				i) a simple linked list
				ii) doubly linked, unless using slist
					1) slist isn't very useful: doesn't save memory on modern compilers anyhow.
				iii) declaration: list<type> identifier;
				iv) Basic functions
					1) push_back(identifier), pushes an element onto the back of the list
					2) pop_front(), removes the front element
					3) pop_back(), removes the back element
					4) front(), returns a reference to the element at the front of the list
					5) back(), returns a reference to the element at the back of the list.

			e) Common Functions
				i) size(), returns number of elements in a container/adapter.
				ii) empty(), returns a bool true if it's empty, and bool false if it's not.
				iii) insert(iterator, identifier), inserts value in identifier at the iterator position.
				iv) erase(iterator), removes the value at the iterator position, and compacts the structure.
				v) clear(), removes all elements in a container/adapter.
			
		2) Container adapters
			a) Adapters are an abstraction designed to store/access elements in a manner other than linearly.
				i) They use STL containers as the underlying storage method
				ii) Generally used to organize data in a more logical manner for a particular application.
					1) eg: use of multimaps as dictionaries
					2) priority queues for time-critical applications
			b) [multi-]map
				i) Has 2 members: key and value.
					1) accessed by: identifier->first, and identifier->second (respectively).
				ii) stores the "mapping" of a given key to a given value.
				iii) Multimaps can have >1 value mapped to for a given key. (think dictionary!)
					1) Still, does not declare more than one value for a given key
					2) creates another pair with an identical key.
				iv) Declaration: [multi]map<key-type, value-type>;
				v) Basic functions
					1) insert(identifier), inserts a specially formed data pair into the list.
					2) pair(identifier, identifier), auxilliary function that returns a proper pair for insert().
					3) [identifier] = identifier, will insert the left-most ident. as the key to the right-most ident.
					
			c) [priority]queue
				i) A container that processes data elements in LIFO order (except priority queue), aka: a buffer
				ii) Priority queue: orders elements inserted into it via a priority rating scheme.
				iii) By default uses a vector as it's underlying storage, but could use others.
				iv) declaration: [priority_]queue<type[, container[, compare_func()]]> identifier;
					1) type is the data type to be stored (base or ADT)
					2) optional: container is the underlying type used to store.  A vector by default.
					3) optional: compare_func() is the funtional object (aka functor) by which comparison will be done. (only available for priority queue)
						*) functors are beyond the scope of this talk!
				v) Warning: You can't iterate over the elements, as it would defeat the purpose.  Use a sorted vector instead, or a heap.
				vi) Basic functions:
					1) push(identifier), pushes an element into the queue.
					2) pop(), removes the item at the front of the queue.
					3) front(), returns a refernce to the element at the front of the queue.
					4) back(), returns a refernce to the element at the back of the queue.
				
			d) [multi]set
				i) Only one value is stored for each element. (unlike a map)
				ii) declaration: [multi_]set<type> identifier;
				iii) Basic functions:
					1) insert(identifer), inserts an element into the set
					2) find(identifier), looks for an element in the list.  Returns an iterator position. (end() if not found)
				
			e) stack
				i) Simple stack.  Data handled in LIFO order
				ii) declaration: stack<type[,sequence_type]>;
				iii) type is the base/adt you expect to store, and sequence_type is the container you'd like to use for the internal structure.
					1) sequence_type is optional, and it defaults to dequeue.  You can use vector or list.
				iv) Basic functions:
					1) push(identifier), pushes an element onto the stack.
					2) top(), returns a refernce to the element on top of the stack.
					3) pop(), removes the top element from the stack.
				v) Warning: stacks do NOT allow iteration through elements, as this violates the function of a stack.
				
		3) Iterators
			a) What are they?
				i) A "smart" pointer
				ii) Despite the complexity of the structure contained, the iterator still knows how to go from one to the next with a common interface. (See operators)
				iii) Can be referenced just like a pointer, and manipulated via pointer arithmetic (depends on iterator type)
			
			b) Why do we use 'em?
				i) An easy interface to elements in your container.  Generally, you can change the container and not change the traversal code.
				ii) Can provide massive speed-ups on certain things, like random access to a known position in a linked-list.
				iii) Generic programming / code re-use!
				iv) The <algorithm> class is built off of it.
			
			c) Declarations
				i) <type>::iterator is a read/modify type iterator
				ii) <type>::const_iterator is a read-only type iterator
				iii) Q: Why the distinction?  A: Principle of Least Priviledge!  Don't give a program/function/user/yourmom any more access to something than they need.
				
			d) Classes
				i) Ranom Access: Can point to any element in a container w/o linearly searching through the others.
					1) Used in vectors, deqeues, and strings as these are random-access capable containers/adapters.
					2) Can do comparison via < & >.

				ii) BiDirectional (aka Sequential) Access: Can point to any element, but must go through each element in sequence prior.
					1) Seen in [multi][set|map], and [s]list.
					2) Only can use -- and ++ operators.
			
			e) Operators
				i) Arithmetic: ++, -- (+, - available to random access iterators only!)
				ii) comparison: ==, != (< and > available to random access iterators only!)
				iii) Assignment: =
				iv) Reference: *
				v) Obviously, '.' and '->' work as well if you're accessing a pointer member that the iterator points to.
			
			f) Common iterator functions of STL containers/adapters (all have them!)
				i) begin(), returns first element in the container/adapter
				ii) end(), returns the location PAST the last element.  I repeat, PAST the last element!
					1) Why?  So you have an easy loop-control sentinel, eg: Itr != <cont/adap>.end(), apply to your favorite loop!
					2) note: avoid using < and > for loop control, since bidirectional iterators don't support that kind of comparison.

			g) Iterator Adapters
				i) reverse iterators
					1) Simply put, they swap + for - and vice versa internally.
					2) useful for quickly accessing elements in reverse order w/o calling reverse() on a container.
					3) Created via rbegin() and rend() functions, available from all containers/adapters.
						1) these adapters return iterators at the opposite location from their forward counterparts.
						2) rend() returns the iterator starting at the element BEFORE The first element in sequence.
						3) rbegin() returns the iterator starting at the last element in sequence.
				
				ii) insert iterators
					1) 
		4) Algorithms
			a) Generic algorithms that operate on STL containers/adapters.
			b) designed to use iterators to abstract the class type from the algorithm, eg: functional, not object, oriented programming.
			c) include: <algorithm>
			d) Warning about "ranges"
				i) STL Algorithms use half-open ranges. (recall math notation: '[start, end)')  eg: The element pointed to as the end of the range will not be included in any operation.
				ii) Be sure the iterator ranges are actually defined (eg: not starting at 55 and going to say 2).
					*) Check by using < operator (defined for random access iterators only!), eg: if (itr1 < itr2) { sort (itr1, itr2); }
				iii) the iterators belong to the same container/adapter
				iv) Be sure that the container has elements, eg: begin() != end().
				v) Not following these guidelines results in "undefined" behavior, eg: segfaults.  ;-)
			e) sort()
				i) Prototype: sort(iterator, iterator);
				ii) the iterators given usually define begin to end of a container/adapter, but can specify any closed-form range.
				iii) returns nothing.
				iv) Generally sorts in increasing order, but can sort on other orderings.
				v) comparisons use the < operator.
				
			f) find()
				i) Prototype: iterator = find(iterator, iterator, value);
				ii) value can be any data type you're looking for thats in that class.
				iii) returns an iterator for the first element found.
			
			g) reverse()
				i) Prototype: reverse(iterator, iterator);
				ii) Simply reverses the order of the elements in the container
				iii) Again, comparisons done using < operator.
				iv) returns nothing.
				
			h) resize()
				i) prototype: container.resize(sizeValue);
				ii) Adds space for more elements
				iii) sizeValue is usually the output from the size() function of another container.
				
			i) copy()
				i) prototype: copy(iterator1, iterator2, iterator3);
				ii) Copies a range of elements from one container to another
				iii) first two parameters are iterators that define the range of elements to copy, third parameter is the starting position iterator for the destination container.
				iv) you must have enough space to use this.  Otherwise the behavior is "undefined", eg: crash.
					1) Generally, use size() and resize() to ensure enough space in the destination container.
				v) returns nothing.

IV) Code Examples ... or, I'm not crazy, this shit really works!
	A) string2cstring.cc
		1) shows how to convert C++ style strings to character arrays for use in s
	
IV) Wheredo I find more? (aka: further resources)
	A) Phil Ottewell's STL tutorial, http://www.yrl.co.uk/~phil/stl/stl.htmlx
	B) SGI's STL Reference pages, http://www.sgi.com/tech/stl/
	C) "The C++ Standard Library: A Tutorial & Reference" N.M. Josuttis, Addison Wesley (chapters 5 and on) 
	D) "How to Program C++", Dietel & Dietel, http://www.deitel.com/books/cppHTP4/
	E) "Effective STL", Meyers, Addison Wesley
