(previous): Random access and memory access [ 11.html ]

Preparation

Study this page and chapter 12 on the containers in the Standard Library and write down the questions, doubts, and surprises that you have on a piece of paper.

Assigned Work Due

Hand in your questions, doubts and surprises.

Input

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 [ stl.html ] that is a good quick introduction. The book is a much better reference. On line you can look at Silicon Graphics documentation [ 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.

You can skip examples that use the author's alpha class. These are set up to work in Europe as well as the USA.

Don't panic: We will look at algorithms in general next time [ 13.html ] , and then return and study C++ algorithms and iterators [ 14.html ] after that. Then we will study how the <list> data structure is implemented.

Then there will be a quiz that tests your knowledge of the standard containers: deque, list, map, multimap, queue, set, multiset, stack, vector,... I will describe a situation or property and expect you to select a suitable container. For example

• What standard container is good for simulating a line of people waiting for a tell in a bank?
• What standard container only lets your add items at one end and remove at the other end and does not let you access them in the middle?
• What standard container could be used to store a many-to-one relation between two classes?

Questions

What Data Structures are mentioned in this chapter?

Name	Library	Notes
vector	<vector>	indexed contiguous sequence
deque	<deque>	vector grows at both ends
stack	<stack>	LIFO, push, pop, top, empty, size
queue	<queue>	FIFO, push, pop, first, last, size, empty
priority_queue	<queue>	Biggest floats to top, push, pop, first, last, size, empty
list	<list>	slice, dice, insert, sort, ...
set	<set>	ordered collection of unique items, intersections, union, etc
multiset	<set>	ordered collection of items, intersections, union, etc
map	<map>	ordered set of pairs, first key to unique items,..., general array
multimap	<map>	ordered set of pairs, first key to items,..., general array
functions	various	Yes, functions are also objects. There are functions that have functions as data and produce functions!
streams	<iterator>	Access files, cin, cout using iterators and algorithms

Which parts of Chapter 12 are most important?

I am planning laboratories that involve: vectors, lists, and multisets plus sorting large amount of data. You will also be doing a project that involves at least one of the containers. In quizzes/finals I tend to ask fill in the blank questions where each answer is one of the container types. I also can give you code using any of them and expect to fill in some blanked out parts /*__________________*/. One will be answered, at least, from each person.

In your future career you may need any of the containers or algorithms:-(

In our degrees knowing these containers and iterators can make many classes easier.

Are containers, iterators, and algorithms used in internet applications?

Yes. Internet applciations should have a specialized fron end that interacts with the user and sends them pages to view. Each internet technology has different ways of handling this.

Inside each application are search engines, data bases, containers, iterators, and algorithms -- and nearly all of them come from computer science.

What does an fstream do?

It allows input and out of data from and to a file.

Can I explain how iterators work?

Later. We will design and implement some in CS202.

Is it beneficial to write algorithms out instead of using the library?

Onely in a class like CS330!

What are the associative containers?

Set, map, multiset, multimap. See questions below.

What is a set?

A collection of objects. You can insert and remove them. You can test if an object (or another set) is in a set. C++ sets are kept in order and you can visit each member in turn. However you can not have duplicate elements.

Example: The set of students on my roster.

What is a multiset?

It is just like a set accept an item can appear zero or more times.

What is a map?

A mathematical map is a relation between two sets of objects called the domain and codomain. It is a map because each element in the domain has no more than one element in the codomain. It is well known that any relationship can be seen as a set of pairs. So, in C++, a map is a set of pairs like this

 		pair(x,y)

and each x has no more than one y. WHat is cool is that if m is a map associating each X with a Y, then

 		m [x]

is the y. More you can use assignment to add and modify the pairs:

 		m[x]=y;

What is a multimap?

It is like a map only each x can have many ys.

What is styp, ctyp, and etyp on Page 458?

These are abbreviations defined on page 457. styp for example is a type name of either a set or a multiset and etyp is the name of its elements. For example. if we declare

 		set<Phone> directory;

then s is set, styp is "set<Phone>", the etyp is "Phone", and the comparator type (ctyp) is "less<Phone>". So "directory" has type "set<Phone>" and directory[3], if it exists, has type "Phone", and we compare "Phone" items like this

 		phone1.less<Phone>(phone2)

Can you explain function objects a bit more?

A function object is an object that can work like a function. In other words it is an object that can appear in C++ code like this

 		function_object(arguments)

In other words

1. Any function is a function object!
2. Any class that has the operation() defined is a function object.

    			T operator () (arguments){....}


Function objects are the modern OO way of communicating a calculation or test to another function. That function knows how to use it, and doesn't worry about what it does.

Here is a dumb example [ testFillGen.cpp ] of using function objects.

What are function adapters?

A function adapter is a special kind of function that takes another function and returns a new adapted function that uses the original one.

THink of a the pwer adapters you use when you visit a foreign country.

We won't use them any quizzes or the final but I may be forced to use one in a lab. You may find them helpful after you graduate.

Why are random access iterators most powerful?

A random access iterator can do everything that a bidirectional iterator can. And a bidirectional iterator can do everything that a normal iterator can do:

Type of Iterator	Operations
Random access	*, =, ==, ++, --, +=, -=, [], ...
bidirectional	*, =, ==, ++, --
Random access	*, =, ==, ++

Why can't you us pointers with containers?

They are dangerous and iterators do the same job better.

What are the advantages and disadvantages of using library container classes?

As a rule the only downside to using container classes is that you have to know them well enough to find one that helps you solve a problem. You use the pleasure of reinventing the wheel.

Often, you can find a predefined container/algorithm that does what you want better than you could. It is likely to be faster and cleverer than anything you could do quickly.

What are function adapters?

Function adapters allow us to construct function objects with complicated behavior without declaring a class or function. They are operators that manipulate functions rather than numbers or characters.

You shouldn't need to use them in CSci202, but you may find a use for them in your future career. For example, do rapidly develop a version of the quicksort algorithm I needed to use the partition algorithm and that needed me to define a predicate that was true for all items less than or equal to a particular value. To do that I used a function adapter to convert the predefined less_equal function object into the predicate I wanted:

 		bind2nd(less_equal<int>(), value)

Key point: I didn't expect to ever use this clever feature of C++, but did so this week.

Can you go over maps and sets?

Check out my stl.html notes (see above).

Key points?


1. Both are ordered collections of data.
2. You can new data to the collections, remove items, found out if they are there, modify their contents, etc
3. Maps associate a key value to a data item.... and act like an array:

    		map<string, int> directory;

    		directory["Dick"] = 5327;

4. C++ has implemented the mathematical set theory operations! [ Set Operators in logic_30_Sets ]

   Math	C++ example
   Subset	includes(A1,A2,B1,B2)
   Union	set_union(A1,A2,B1,B2, C);
   Intersection	set_intersection(A1,A2,B1,B2, C);
   Difference	set_difference(A1,A2,B1,B2, C);

   Note: A1,A2 and B1, B2 define ranges in two sets. C is an inserter for a set.



When to use an iterator vs a pointer?

Use an iterator to refer to items in containers. Pointers for items in an array, or items on the run time heap.

Explain namespace std!

Names are placed in namespaces. The namespace std is where standard names are put. Officially we must prefix names with their namespace like this

 		namespace::name

but this gets old quickly. Instead we can write

 		using namespace whatever;

1. and the C++ compiler will assume that we wanted "whatever::" in front of names that are in the "whatever" namespace.

   Some older compilers let you be lazy and leave out the using namespace.

   How does a priority queue work?

   Magic! Take CSCI330 to get the answers!

   Do stream iterators really handle input and output?

   Yes. Here is some code I found in a sample program

     copy(v.begin(), v.end(), ostream_iterator<int>(cout, "\t"));

   It outputs every int in the container v with a Tab between them.

   See [ ostream_iterator.cpp ] for a complete working example of both io-iterators.

   Compare four kinds of iterator?

   iterator	The normal way to move across container and change things in it.
   const_iterator	The normal way to move across a container. Can not change items!
   reverse_iterator	The other way to move across container and change things in it.
   const_reverse_iterator	The other way to move across a container. Can not change items!

Exercises

Make a list of all the containers mentioned in this chapter. Target: 6.

. . . . . . . . . ( end of section CSci202 Computer Science II, Session 12 Containers) <<Contents | End>>

Laboratory 6 Information Security

Special Preparation for Next Class

Abbreviations