Lab 11: Standard Template Library (STL)

Objectives

Download

STL Containers

A container is an STL template class that manages a sequence of elements. Such elements can be of any object type that supplies a default constructor, a destructor, and an assignment operator.

Some Container Classes

vector

It is the STL container that may be regarded as an enhanced array. It is arguably the container used most frequently.

deque

deque provides the same behavior as a vector but is specialized to support efficient insertion and deletion at the beginning and the end of a list. A deque is preferred over a vector, for example, in the implementation of a queue, an abstraction in which the first element is retrieved each time.

list (doubly-linked)

A doubly-linked list represents noncontiguous memory doubly linked through a pair of pointers that address the elements to the front and back allowing for both forward and backward traversal. Insertion and deletion of elements at any position within the list are efficient; the pointers must be reassigned, but no elements need to be moved by copying. Random access, on the other hand, is not well supported: accessing an element requires traversal of intervening elements. In addition, there is space overhead of the two pointers per element.

map

A map is an associative container, possessing a key/value pair: the key is used for lookup, and the value is the actual item. It supports the syntax of "associative array". This means that if we define x by "map<string, Student> x;”, then x["00123456"] refers to the Student object with ID "00123456". If no such Student object exists, a new one is created using the Student default constructor.

set

A set is an associative container that contains an ordered set of objects. The container is represented in a way that permits lookup, insertion, and removal of an arbitrary element with a number of operations proportional to the logarithm of the number of elements in the sequence (logarithmic time).

multimap/multiset

Both map and set can contain only a single occurrence of each key. A multimap is similar to a map, and a multiset is similar to a set, except that multimap and multiset support multiple occurrences of the same key. Note that multimap doesn't support the associative array syntax.

queue and stack are also in STL. Hence, there is no need to re-implement them.

Which Container to Use?

There are so many containers... so which one is appropriate for my program?

Before you decide which container to use, you should first think about what operations you are going to act on the container. You should then choose the container that is most efficient for those operations.

Following are some guidelines for choosing a suitable container:

If you need an array-like container, vector is the choice.

If you need random access (i.e. a[5]) and new items are only inserted/removed at the end, use vector.

If you need random access and new items are inserted/removed at either the start or the end, use deque.

If you need to represent something like "index, item", use map. For example, if you want to use a container storing student records such that you can retrieve the record of a student by his or her student ID, map is the best container. If the index is not unique, use multimap instead.

If you need to do a lot of search, insertion and deletion of items at different positions, set is an efficient container. If an item can occur multiple times, use multiset instead.

Use list when you need a linked list and the functionalities of the containers above are unnecessary.

Example Programs

deque.cpp demonstrates the basic usage of deque

list.cpp demonstrates the basic usage of list

set.cpp demonstrates the basic usage of set

map.cpp demonstrates the basic usage of map and multimap

algorithms.cpp demonstrates the usage of some generic algorithms based on STL containers such as vector, list and deque

map_search.cpp demonstrates how to search for an element via its unique key in a map.

It creates a map from int to string. The mapping is from digits to their string equivalents (1 -> "One", 2 -> "Two", etc.). The program reads in a number from the user, finds the word equivalent for each digit (using the map), and prints the number as a series of words.

For example, if the user enters 25463, the program responds with: Two Five Four Six Three. If the user enters 1a2d34, the program responds with: One [err] Two [err] Three Four.

multimap_search.cpp demonstrates how to search in multimap. Multiple values can be associated with a single key.

This program first defines a class Student, which consists of name, student ID, and department. The student ID field can uniquely represent an individual student, but name or department field can't. So if you want to find a student by specifying his (her) name or department, you will probably get multiple results, which can be implemented by multimap, as demonstrated in this program.

The program accepts the commands of user, and performs the corresponding functions. If the user inputs 'd' and the department name, which means to search students via department, the program will search in the multimap and output the result. If the user inputs 'q', the whole program will quit.

Algorithms

STL also includes a large collection of algorithms that manipulate the data stored in containers.

For example, the following codes reverse the order of elements in a vector by using the reverse algorithm.


vector<int> v(3); // Declare a vector of 3 elements.
v[0] = 7;
v[1] = 3;
v[2] = 10; // v[0] == 7, v[1] == 3, v[2] == 10
reverse(v.begin(), v.end()); // v[0] == 10, v[1] == 3, v[2] == 7

Note that reverse() is a global function, not a member function.

Iterators

In the example above, the arguments to reverse are iterators, which are a generalization of pointers. Pointers themselves are iterators, which is why it is possible to reverse the elements of a C array like the following.

double A[6] = { 1.2, 1.3, 1.4, 1.5, 1.6, 1.7 };
reverse(A, A + 6);

Similarly, vector declares the nested types iterator and const_iterator. In the example at the beginning, the type returned by v.begin() and v.end() is vector<int>::iterator. There are also some iterators, such as istream_iterator and ostream_iterator, that aren't associated with containers at all.

Iterators are the mechanism that makes it possible to decouple algorithms from containers: algorithms are templates, and are parameterized by the type of iterator, so they are not restricted to a single type of container.

Function Objects

The STL includes a large collection of function objects, also known as functors. A function object is simply any object that can be called as if it is a function. An ordinary function is a function object, and so is a function pointer; more generally, so is an object of a class that defines operator().

The find_if example includes a function object Greater_Than(350), which is an object of the class Greater_Than that defines operator().

Lab Task

building.h, building.cpp, CheckBuilding.cpp are sources of an incomplete program for creating a building (you may think of it as a hotel) with certain numbers of floors and rooms. Then you can put persons identified by their names and IDs into the rooms, or move persons out of their rooms. You need to store the names and IDs in string vectors.

There are two member variables in class building: names and ids. They are 2D arrays (vector class is used for implementation). names[i] is an array/vector of class string (i.e. vector<string>), which contains all the occupants' name at floor i. names[i][j] refers to the occupant name at the floor i in room j. The type is class string. And ids is the corresponding identity number of that occupant. The type of ids is the same as that of names.

Your task:
Complete the missing code marked with "//..." in building.cpp.  Do NOT modify the other files.

Specifically, you need to implement:

Following is the sample output that your program should produce:

Number of vacancies in Mine is 9
The building is empty
Number of vacancies in Mine is now 6

Display()
Occupant of Room 1 on floor 0 is John, Identity number 234567
Occupant of Room 2 on floor 0 is Dora, Identity number 123456
Occupant of Room 2 on floor 1 is Daisy, Identity number 345678

Display(0)
Occupant of Room 1 on floor 0 is John, Identity number 234567
Occupant of Room 2 on floor 0 is Dora, Identity number 123456

Display(1)
Occupant of Room 2 on floor 1 is Daisy, Identity number 345678

Display(2)
Floor 2 is empty

Put Jane
Occupant of Room 1 on floor 0 is Jane, Identity number 4567891
Occupant of Room 2 on floor 0 is Dora, Identity number 123456
Occupant of Room 2 on floor 1 is Daisy, Identity number 345678

Put Maple
Floor 3 is out of range!
Room 1 on floor 3 is out of range!
Occupant of Room 1 on floor 0 is Jane, Identity number 4567891
Occupant of Room 2 on floor 0 is Dora, Identity number 123456
Occupant of Room 2 on floor 1 is Daisy, Identity number 345678

Put Maple Again
Occupant of Room 1 on floor 0 is Jane, Identity number 4567891
Occupant of Room 2 on floor 0 is Dora, Identity number 123456
Occupant of Room 2 on floor 1 is Daisy, Identity number 345678
Occupant of Room 1 on floor 3 is Maple, Identity number 5678912

Remove Room 2 on Floor 1
Occupant of Room 1 on floor 0 is Jane, Identity number 4567891
Occupant of Room 2 on floor 0 is Dora, Identity number 123456
Occupant of Room 1 on floor 3 is Maple, Identity number 5678912

Add Room 3 on Floor 0
Occupant of Room 1 on floor 0 is Jane, Identity number 4567891
Occupant of Room 2 on floor 0 is Dora, Identity number 123456
Occupant of Room 3 on floor 0 is Beryl, Identity number 6789123
Occupant of Room 1 on floor 3 is Maple, Identity number 5678912

Switching to Yours:
Occupant of Room 0 on floor 0 is Lisa, Identity number 333333

Occupant of Room 0 on floor 0 is Lisa, Identity number 333333
Occupant of Room 1 on floor 1 is Paul, Identity number 24987
Occupant of Room 2 on floor 1 is Harry, Identity number 543216
Occupant of Room 3 on floor 2 is Bryce, Identity number 876543

Names of all occupants of Yours:
Bryce Harry Lisa Paul

References