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.... [ 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
1 3 4 5 42 42 42 42 100 121 123 1024you 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
A more general example
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 [ Heap_sort ] (wikipedia) is an animation, overview, etc.. And [ http://cplusplus.com/reference/algorithm/make_heap/ ] and [ 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 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
bool flag=false;
for( .....; .... && !flag; ....)
{
...
if(event) flag=true;
...
}By-the-way, use a better name than flag!
A 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 [ 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
vector <bool> whatever;but they are faster. However bitsets have a fixed size.
Bitsets provide the same functionality as
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
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
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:
myBitSet[ i/(8*sizeof(int)) ] |= 1<<(i%(8*sizeof(int)));(I've probably got this wrong:-( ) Here [ 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 [ misc.cpp ]
Chapter 22.7 pages -- Function Objects
How are function objects used?
Sample code -- filling and generating a vector... [ testFillGen.cpp ]
Compare this with just using a function [ 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
class Adder{
int c; //a constant to add
public:
int operator()(int x) { return x+c;}
Adder (int c0 =1) : c(c0) {}
} add1;
Then, in the main program I can use "add1" to add one to the value of an expression:
cout << add1(2);I can also create new functions
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:
class Summer{
int total;
public:
Summer():total(0){};
int operator() (int value){ total+=value; }
int result()const{return total;}
void set(int value=0){total=value;}
};
...
Summer odd, even;
Iterator p=container.begin();
for(int i=1; p!=container.end(); i++,p++)
{
if(i & 1) //odd
odd(*p);
else
even(*p);
}//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
#include <vector>
#include <______1________ >
void sort( vector <int> v)
// This is an implementation of _______4_______ Sort
{
for(vector <int>::____2____ k=v.begin ();
k != _______3______(); k++)
{
iter_swap(k, min_element(k, v.end()));
}
}
Resources
[ http://www.cplusplus.com/reference/algorithm/ ]
. . . . . . . . . ( end of section CSci202 Computer Science II, Session 19, STL Algorithms) <<Contents | End>>
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
[ lab10.html ]
Next -- Review course and prepare for final:
[ 20.html ]
(instructions and content).
Abbreviations