.Open CSci202 Computer Science II, Session 19, STL Algorithms
(previous): STL Containers
.See HTTP://www/dick/cs202/18.html
. Preparation -- 22.5 Algorithms etc
 22.5.1 fill, fill_n, generate and generate_n                 1100
 22.5.2 equal, mismatch and lexicographical_compare           1101
 22.5.3 remove, remove_if, remove_copy and remove_copy_if     1104
 22.5.4 replace, replace_if, replace_copy and replace_copy_if 1106
 22.5.5 Mathematical Algorithms                               1109
 22.5.6 Basic Searching and Sorting Algorithms                1112
	Review
.See ./lab08.html
 22.5.7 swap, tier_swap and swap_ranges                       1114
 22.5.8 copy_backward, merge, unique and reverse              1116
 22.5.9 in place_merge, unique_copy and reverse_copy           1118
 22.5.10 Set Operations                                       1120
 22.5.11 lower_bound, upper_bound and equal_range             1123
 22.5.12 Heapsort                                             1125
 22.5.13 min and max                                          1128
 22.5.14 STL Algorithms Not Covered in This Chapter           1128
 22.6 Class bitset                                                 1130
 22.7 Function Objects                                             1134
	Abstract, more than cs202, sometimes very useful
 22.8 Wrap-Up                                                      1137
 22.9 STL Web Resources                                            1138

. Assigned Work Due -- A Question
. Chapter 22 pages  -- algorithms

Are algorithms basically tools to help us do what we want?

Yes.

Power tools.

. Chapter 22 pages 1085-1086 -- associate containers
what else can associative containers do?

A lot....  luckily, in the final, you don't need to know about them.

In practice you will use and learn some neat things we won't be
talking about.

. Chapter number pages 1099 -- Algorithms
The algorithm definitions in the STL look very helpful, is there anything bad about using <algorithm> than normally creating one?

Just the problem of having too many options!

One catch -- you can not derive new classes from the algorithms, iterators,
or containers.  

. Ch. 22 pg 1099 -- Algorithms
Are the algorithms in the STL by and large the only algorithms that you 
will need?

Sadly, No.

But most of your algorithmic needs are catered for here...

. Chapter 22.5 pages 1100 -- Algorithms
Why does the STL separate the algorithms from the containers?

So that each algorithm can work with several different containers.

Also so that you don't have to pass the complete algorithm library
through the compiler just to declare a simple vector.

. Chapter 22 pages 1100 -- fill, fill_n, generate & generate_n
What is the difference between fill and fill_n and generate and generate_n?

The added "_n" stands for a "number of times" parameter.   Instead of giving the
range [`begin`..`end`) the function expects the `begin` and an `n`=number.

. Chapter 22 pages 1111 -- Accumulate function
Does this function only work for adding numbers. I know it's under a numeric header file, but can it be used under any other?

Good question ... let's use the web to find out....
.See http://www.cplusplus.com/

. Chapter 22.5.8 pages 1116 -- copy_backward, merge, unique and reverse
Why does the copy_backward function require three bidirectional iterator arguments?

The "backward" means that the iterators will have to move in both directions....
be bidirectional.

. Chapter 22 pages 1123 -- upper and lower bound
When is it useful to use lower_bound and upper_bound?

Not very often ... but it will still be better to use it than
reinvent it.

First you must have a sequential container that has been sorted.

Second you must nee to find the range were a particular value lies...
for example in the sequence
.As_is 		1 3 4 5 42 42 42 42 100 121 123 1024
you might want to find out where the '42's are.  Lower_bound will
give you the place where the first 42 is and upper_bound will tell
you where the (in this case) 100 is.

. Chapter 22.5.12 page 1127 -- Heapsort
"The two iterator arguments must be random-access iterators, so this function will work only with arrays, vectors, and deques"

what would happen if the iterator arguments were not random-access iterators, would it not work with arrays, vectors, and deques?

It should fail to compile.


. Chapter 22 pages 1123 -- Set Operations
What does "set_union" do?

It is the result of combining two sets into one.
In math, the union of two sets is made up of the elements in either set.

For example
	{2,4,6,8,10 } \cup {3,6,9,12,15} = {2,3,4,6,8,9,10,12}.

A more general example
	{ n:Nat || n is divisible by 2 } \cup { n:Nat || n is divisible by 3 } = {n:Nat || n is divisible by 2 or 3 }.

In the STL a set is always ordered/sorted and the union merges the two sets.

. Chapter 22 pg 1125-1128 - Heapsort -- High Energy Magic
what is Heapsort can you give an example?  
How does the heapsorting algorithm work?

One of Robert Floyd's cleverest ideas
(Robert W. Floyd. Algorithm 245 - Treesort 3, 1964, Communications of the 
ACM 7(12): 701).  It works by taking the data and placing it into
an intermediate tree-structure called a heap, it then reorganizes
the heap into a sorted sequence.  The tree structure is very clever.
I don't expect you to understand how it works when you do the final.

Here
.See http://en.wikipedia.org/wiki/Heap_sort
(wikipedia) is an animation, overview, etc..  And
.See http://cplusplus.com/reference/algorithm/make_heap/
and
.See http://cplusplus.com/reference/algorithm/sort_heap/
at `cplusplus.com` provides a practical reference.

Please take CS330 for more! 

. Chapter 22 pages 1030 -- bit flag
what is a bit flag?

In the computer world a 
.Key flag
is a variable that has two values: up and down, that indicate
whether some event has occurred or not.   For example
they are a way of terminating a loop, inside the loop
.As_is 		bool flag=false;
.As_is 		for( .....;  .... && !flag; ....)
.As_is 		{
.As_is 			...
.As_is 			if(event) flag=true;
.As_is 			...
.As_is		}
By-the-way, use a better name than `flag`!

A 
.Key bit flag
is a flag that is squeezed into a single bit of storage.  It can have
precisely two values: 0 and 1.
These days it takes up 1/16th of an int at most.

. Chapter 22 pages 1130-1134 -- Class bitset
what are the advantages of Class bitset?
Can you elaborate on the functionality of class bitset?

Bitsets are not going to be on the final.

Here is the
.See ./bitset.cpp
for the STL way of converting numbers to binary.

But suppose we have defined a const SIZE and we want
to keep track of `SIZE` bits of information. Each one
a single up/down decision or state.  Then we have 4 or 5
different ways to do it including bitsets.  Each have different advantages.

Bitsets provide the almost the same functionality as
.As_is 	vector <bool> whatever;
but they are faster.  However bitsets have a fixed size.

Bitsets provide the same functionality as
.As_is 	bool whatever[SIZE];
but they use a lot less storage -- a "bool" can take up 16 bits
to store one bit of information.  So the array will be at least 16
time larger than
.As_is 	bitset <SIZE> whatever;
but only provide the same facilities.

You can do nearly all the operations for `bitset<SIZE>` yourself
by using the bit wise operators and allocating 
.As_is  int myBitSet [1+SIZE/(8*sizeof(int))];
This takes a lot of thinking and coding. For example
to set bit "i" you write something like this:
.As_is 	myBitSet[ i/(8*sizeof(int)) ] |= 1<<(i%(8*sizeof(int)));
(I've probably got this wrong:-( )
Here
.See ./bitzi.cpp
is an example of use bitwise operators to extract bits.

The final alternative is to declare a structure with `SIZE` bit fields
but this does not provide you with the an indexed/subscripted
array of bits.  For an example see
.See ./misc.cpp

. Chapter 22.7 pages  -- Function Objects
How are function objects used?

.List
 Define a class F.
 Declare an object -- say f that instantiates F.
 Call the function -- f(argument)
.Close.List

Sample code -- filling and generating a vector...
.See ./testFillGen.cpp

Compare this with just using a function
.See ./testFillGen2.cpp
where you can not get a new generator that starts at zero again,
because it doesn't use a function object.

. Chapter 22 pages 1134 -- Function Objects -- Optional enrichment
What are function objects?
Can you give a clearer explanation on Function Objects and what they do?

A function object is any object whose class describes what happens if you
treat it like a function.  If the class defines `operator()` then the
object will act precisely like a function.   It also has all the
normal possibilities for an object -- so it will be more powerful
than a normal function.

Suppose you wrote
.As_is 		class Adder{
.As_is 			int c; //a constant to add
.As_is 		   public:
.As_is 			int operator()(int x) { return x+c;}
.As_is 			Adder (int c0 =1) : c(c0) {}
.As_is 		} add1;

Then, in the main program I can use "add1" to add one to the value
of an expression:
.As_is 		cout << add1(2);
I can also create new functions
.As_is 		Adder myAdder(17);
which adds 17 to its argument.

Clever programmers can do some neat things with function objects.
For example objects in this class can be used to add up a sequence of ints
and maintains a running total:

For example objects in this class can be used to add up a sequence of ints
and maintains a running total:
.As_is 		class Summer{
.As_is 			int total;
.As_is 		   public:
.As_is 			Summer():total(0){};
.As_is 			int operator() (int value){ total+=value; }
.As_is 			int result()const{return total;}
.As_is 			void set(int value=0){total=value;}
.As_is 		};
.As_is 	...
.As_is 	Summer odd, even;
.As_is 	Iterator p=container.begin();
.As_is 	for(int i=1; p!=container.end(); i++,p++)
.As_is  {
.As_is 		if(i & 1) //odd
.As_is 			odd(*p);
.As_is 		else
.As_is			even(*p);
.As_is 	}
//Unchecked code above.

It is a pity that C++/Java makes it so long winded to construct one:
first declare a class, then construct an instance.

Several STL algorithms accept function objects that describe what
the program want to be done to the items in a container.

. Chapter 22.5 Function Objects
What other uses are there for function objects?

Depends how creative you are.   Any examples I would give would limit
what you might imagine.  But consider this -- several languages
(including Ruby and Python) rely on function objects (or equivalent) to
do just about anything interesting.

. Exercises
Fill in the blanks below
.As_is 	#include <vector>
.As_is 	#include <______1________ >
.As_is 	void sort( vector <int> v)
.As_is 	// This is an implementation of _______4_______ Sort
.As_is 	 {
.As_is 	   for(vector <int>::____2____  k=v.begin (); 
.As_is 				k != _______3______(); k++)
.As_is 	    {
.As_is 	          iter_swap(k, min_element(k, v.end())); 
.As_is 	    }
.As_is 	 } 

. Resources
.See http://www.cplusplus.com/reference/algorithm/

.Close CSci202 Computer Science II, Session  19, STL Algorithms
. Chapter 23 pages 1163 -- Light
In the book it implies that an ogre has three types of Lights; POINT, SPOT, DIRECTIONAL. Can you further explain these types?

You are on your own -- CS202 stops at the end of chapter 22.

Have fun -- and take our computer graphic options when you are ready for them.

. Lab10 on Stacks and Evaluating expressions
.See http://www/dick/cs202/lab10.html

. Next -- Review course and prepare for final:
.See http://www/dick/cs202/20.html
(instructions and content).