(previous): Bits and Pieces [ 17.html ]

Preparation -- 22 Standard Template Library (STL) 1057

1. 22.1 Introduction to the Standard Template Library (STL) 1059
2. 22.1.1 Introduction to Containers 1060
3. 22.1.2 Introduction to Iterators 1064
4. 22.1.3 Introduction to Algorithms 1069
5. 22.2 Sequence Containers 1071
6. 22.2.1 vector Sequence Container 1072
7. 22.2.2 list Sequence Container 1080
8. 22.2.3 deque Sequence Container 1083
9. 22.3 Associative Containers 1085
10. 22.3.1 multiset Associative Container 1086
11. 22.3.2 set Associative Container 1089
12. 22.3.3 multimap Associative Container 1090
13. 22.3.4 map Associative Container 1092
14. 22.4 Container Adapters 1094
15. 22.4.1 stack Adapter 1094
16. 22.4.2 queue Adapter 1096
17. 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 [ 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.

    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 deque (pronounced "deck") is a class in the <deque> library. It provides these member functions with these names:
    

    1. deque ~deque
    2. operator=
    3. begin end
    4. rbegin rend
    5. size max_size empty resize
    6. front back
    7. operator[] at
    8. swap
    9. clear
    10. push_front push_back
    11. pop_front pop_back
    12. assign insert erase
    
    

    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

     		c.front() = whatever;

     		c.back() = whatever;

    or use them in expressions:

     		.....c.front()...

     		.....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:

     	vector< int > integers( array, array + SIZE );

    instead of writing it as:

     	std::vector< int > integers( array, array + SIZE );

    Yes.

18. 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 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:

19. Containers have items of data stored in them.
20. In associative containers the data determines where the items are stored.
21. A set uses the whole value of the item to determine where the item is put.
22. 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 [ stllist.cpp ] [ stlset.cpp ] [ animal2.cpp ] [ animal4.cpp ] [ animal5.cpp ] [ showInsertionSort2.cpp ] [ showInsertionSort3.cpp ] [ showInsertionSort.cpp ] [ timeInsertionSort.cpp ] [ timeMergeSort.cpp ] [ timeMultisetSort.cpp ] [ timeQuickSort.cpp ] [ timeSelectionSort.cpp ] [ front.inserter.cpp ] [ 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?

    [ 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):

     	    template <typename value_type, ...>

     	    class stack {

     	    ...

     	    public:

     	      bool      empty() const             { return c.empty(); }

     	      int       size()  const             { return c.size(); }

     	      value_type&       top()             { return c.back(); }

     	      const value_type& top() const       { return c.back(); }

     	      void push(const value_type& x)      { c.push_back(x); }

     	      void pop()                          { c.pop_back(); }

     	    };

    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.

    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
    1. A sequential container of data, where items can only be accessed, inserted, and deleted at only one end.____________________________
    2. A sequential container of data where the items are inserted at one end but must be deleted at the other end.____________________________
    3. A sequential container of data where items can be accessed, inserted, and deleted at either end but not in the middle.____________________________
    4. A sequential container of data, indexed by number, where any item can be accessed but items can only be inserted at one end only.____________________________
    5. A sequential container of data, that can be accessed in sequence and can have items inserted and deleted at any place in it. ____________________________
    6. A associative container of data with no duplicated items, that keeps its data in increasing order as items are inserted and deleted. _______________________
    7. 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.____________________________
    8. A simulation of a line of students waiting to pay the cashier and enter the commons for lunch. ____________________________
    9. A program that lets you input an algebraic expression and calculates and print its values.____________________________

    Resources

    [ Standard_Template_Library ] (Wikipedia) [ http://www.cplusplus.com/reference/stl/ ] (cplusplus.com)

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

Next -- STL Algorithms

Abbreviations