.Open CSci202 Computer Science II, Session 18 Standard Containers
(previous): Bits and Pieces
.See http://www/dick/cs202/17.html
. Preparation -- 22   Standard Template Library (STL)                     1057
 22.1 Introduction to the Standard Template Library (STL)  1059
     22.1.1 Introduction to Containers                    1060
     22.1.2 Introduction to Iterators                     1064
     22.1.3 Introduction to Algorithms     1069
 22.2 Sequence Containers                   1071
     22.2.1 vector Sequence Container      1072
     22.2.2 list Sequence Container        1080
     22.2.3 deque Sequence Container       1083
 22.3 Associative Containers                1085
     22.3.1 multiset Associative Container 1086
     22.3.2 set Associative Container      1089
     22.3.3 multimap Associative Container 1090
     22.3.4 map Associative Container      1092
 22.4 Container Adapters                    1094
     22.4.1 stack Adapter                  1094
     22.4.2 queue Adapter                  1096
     22.4.3 priority_queue Adapter         1098
. CSCI330 in a Box
When they designed C++ they took just about every data structure and algorithm
that is taught in undergraduate Computer Science and programmed it
for us.   There are a lot of goodies in the Standard Library.  I'm not sure that
anybody has memorized them all, and I don't know which will be
most useful to you.  We almost have an embarrassment of riches.
. Advice
I prepared a page describing the Standard Library
.See http://www/dick/cs202/stl.html
that is a good quick introduction.  The book is a much better
reference.  On line you can look at Silicon Graphics documentation
.See http://www.sgi.com/tech/stl/
however this is very technical and includes non-standard functions
and data types.

Don't get to bogged down in the early sections.   Do a fast scan
of the whole chapter and make a list of all the different types
of containers that the C++ Standard Library provides.  Then drill down
for the details.

. Assigned Work Due --A Question
Chapter 22, session 18,  Tyler Lentz


Which of the containers is more secure?  Does having less functionality tend to make a container more secure?

Not really.  As far as I know, they are all equally secure.

They can all become insecure if you are stupid.

. Chapter 22 pages  -- standard library
what can we do with the standard library?

Lots.  Input, output, computation, storing and retrieving data, and so on.

. Chapter 22 pages 1059-1098 -- STL
What is the biggest disadvantage to using the Standard Template Library?
Are there any downsides to using the stl

It is too big.

You need to learn about it.   And until you are familiar with it
you have to check the documentation.

Competent engineers have always standard
ready-made components that fit the problem in hand.

. Chapter 22 pages 1063 -- container header files
Which of the new container header files introduced in this chapter should we know?

You need to know a little about all of them.   Any of them might appear on the final.
Except `bitset`.

However I don't expect you to be an expert on them.   The final will focus
most on vector, list, stack, queue, deque, map, multimap, 


. Chapter 22 pages 1060 -- typedef
What exactly does typedef do besides create a similar name for other data types?

Nothing.

. Chapter 22 pages 1059 -- Standard Template Library
can you explain further the member function  deque?

A 
.Key deque
(pronounced "deck")
is a class in the <deque> library. It provides these member functions
with these names:
.List
 deque ~deque
 operator=
 begin end
 rbegin rend
 size max_size empty resize
 front back
 operator[] at
 swap
 clear
 push_front push_back
 pop_front pop_back
 assign insert erase
.Close.List

. Chapter 22 pages  -- Deques vs. Vectors
When would you prefer to use a deque over a vector and vice versa?

Use a deque only when you hve to add and remove data from opposite ends of a sequence, AND
also need to use a subscript/index to access the items in the "middle" of the container.

. Chapter 22.2 pages  -- Front  and Back
What does the "front" and "back" of a list mean?

They are functions that give you the first and last items in a sequential container.

If you have a contianer c then you can write
.As_is 		c.front() = whatever;
.As_is 		c.back() = whatever;
or use them in expressions:
.As_is 		.....c.front()...
.As_is 		.....c.back()...

The parenthesis are vital.

Not do not confuse these with `c.begin()` and `c.end()` which are not items.  They are
iterator values.


. Chapter 22 pages 1083 -- pop
what does the pop function do to a program?

It doesn't do anything to the program.  It removes an item of data from a sequential container.

. Chapter 22 pages 1077 -- namespace std
. Chapter 22 pages 1066 -- STL
Fig. 22.5 lines 4 - 5.  the iostream header file is used but then there are three using statements.  Are these using statements necessary and if not then why are they used?


In fig. 22.15, if we where to include 'using namespace std;',
would it be OK to write line 17 as:
.As_is 	vector< int > integers( array, array + SIZE );
instead of writing it as:
.As_is 	std::vector< int > integers( array, array + SIZE );

Yes.

Is there a reason why the book decided to add std::?

It is better style in large programs to avoid "using namespace std;".

. Chapter 22 pages 1076 -- Vector Sequence Container
Can you explain the const_reverse_iterator process in c++ 

They are not processes.  They are a special kind of iterator.  They start at the last item
in the container and move towards the front.  The "const" stops you from changing the
items the iterator refers to.

. Chapter 22 pg 1071-1094 Subject - Sequence and Associative Containers
What's the main difference between Sequence Containers and Associative Containers?

The data in a sequential container is in an sequence  that is determined by how you store
it, and if you have sorted it.

The associative containers use the data in the items to determine where they are put in
the data structure.  

. elaborate more on this please :D

$TBA

. Chapter 22 pages 1085 -- Associative Containers
Are associative containers simple databases?

They are a data structure.  A similar one is used in dat bases to speed up
access to items using a key.

A
.Key Data Base
stores data on disks or other permanent (and slower) storage.  The simplest data base
is a file that stores records.  Modern data bases store the data in files called
tables and organize them so that data in different tables are linked together using the
values in the records.


. Chapter 22 pages 1086 -- mutliset Associative container
Can you expalin what are multiset Associative containers?

Take one word at a time:
	Containers have items of data stored in them.
	In associative containers the data determines where the items are stored.
	A set uses the whole value of the item to determine where the item is put.
	A multiset is a set where an item may be stored several times.

Sets and multisets are a part of 20th century mathematics -- and still going strong.
	
. Chapter 22 pages ppp-ppp -- STL algorithms
Which algorithm did you find yourself using the most?

The STL algorithms arrived late.  These days I program mostly in PHP+HTML and
the Unix Shell Scripts.  Nether have the STL.  So I have no data about which I've
used most.

. Can you please explain iterators with an example?

Iterators mark places in a container.  Just like pointers, only special purpose.

Key fact:  if `p` is an iterator for container `c`, and `p`!=c.end() then `*p` is an item in the container.

They were used in the sort timing programs.... and many more
.See ./stllist.cpp
.See ./stlset.cpp
.See ./animal2.cpp
.See ./animal4.cpp
.See ./animal5.cpp
.See ./showInsertionSort2.cpp
.See ./showInsertionSort3.cpp
.See ./showInsertionSort.cpp
.See ./timeInsertionSort.cpp
.See ./timeMergeSort.cpp
.See ./timeMultisetSort.cpp
.See ./timeQuickSort.cpp
.See ./timeSelectionSort.cpp
.See ./front.inserter.cpp
.See ./inserter.cpp

. Chapter 22 pages online notes -- iterators 
int your online notes, you mention iterators. i dont quite understand the implementation of these.

We won't be talking about how to implement them in CSCI202 this quarter -- not in the book.

We will talk about using them.

. Chapter 22 pages 1086 -- multiset
does multiset only support bidirectional iterators?

First, it does provide bidirectional iterators -- you can do both ++ and -- on them
(and some other things).

Second, a bidirectional iterator `is` already a forward iterator.

Third it defines a `reverse_iterator` that starts at rend() and goes to `rbegin`.

So multiset gives an almost complete set of iterators.

. Chapter 22 pages 1090-1094 -- Map
Can you give an example of how to use a map associated container?

.See ./scoring.cpp

. Chapter 22 pages 1094-1095 -- standard template library
what does are container adapters and how can they help me when i am programing

An adapter is a class that changes the names of the member functions to a more familiar
form.

Analogy -- when I go to England I carry an adapter so that I can recharge my shaver
and PDAs.  It adapts the USA blugs to UK sockets.  It converts the voltages.
My razor and PDA think they are using USA electricity.

Similarly: container adapters lets you and your program  think it is using a different
container to what it is actually using.

Two examples: stack and queue in the STL.

A stack provides: empty, push, pop, and top.

This was defined in the 1960's when we discovered how useful stacks were in
compiling and interpretting languages.

A vector or a deque provides you with: empty, push_back, pop_back, back, ...

The STL implements stack be changing the names of these operations and hding the rest.

Here is how it does it (editted from a draft standard):
.As_is 	    template <typename value_type, ...>
.As_is 	    class stack {
.As_is 	    ...
.As_is 	    public:
.As_is 	      bool      empty() const             { return c.empty(); }
.As_is 	      int       size()  const             { return c.size(); }
.As_is 	      value_type&       top()             { return c.back(); }
.As_is 	      const value_type& top() const       { return c.back(); }
.As_is 	      void push(const value_type& x)      { c.push_back(x); }
.As_is 	      void pop()                          { c.pop_back(); }
.As_is 	    };


Similarly with a queue.

. Chapter 22 pages 1134 -- Function Objects.
Can you give a clearer explanation on Function Objects and what they do?

Next time.
.Open Review questions -- from a previous quiz or final
For each situation below write down the single answer that fits the situation or description best: Answers: deque, list, map, queue, set,  stack, vector

    A sequential container of data, where items can only be accessed, inserted, and deleted at only one end.____________________________
    A sequential container of data where the items are inserted at one end but must be deleted at the other end.____________________________
    A  sequential container of data where items can be accessed, inserted, and deleted at either end but not in the middle.____________________________
    A  sequential container of data, indexed by number, where any item can be accessed but items can only be inserted at one end only.____________________________
    A  sequential container of data, that can be accessed in sequence and can have items inserted and deleted at any place in it.	____________________________
    A associative container of data with no duplicated items, that keeps its data in increasing order as items are inserted and deleted.	_______________________
   A associative container of pairs of items that given a value for the first item in a pair tells you the value paired  with it.____________________________
  A simulation of a line of students waiting to pay the cashier and enter the commons for lunch.	____________________________
   A program that lets you input an algebraic expression and calculates and print its values.____________________________
.Close



. Resources
.See http://en.wikipedia.org/wiki/Standard_Template_Library
(Wikipedia)
.See http://www.cplusplus.com/reference/stl/
(cplusplus.com)

.Close CSci202 Computer Science II, Session 12 Containers
. Next -- STL  Algorithms
.See http://www/dick/cs202/19.html