[Skip Navigation] [Remove Frame] [CS320] [Text Version] stl.html Sat Dec 23 08:00:56 PST 2006

Contents


    New Data Types in The C++ Standard Template Library

      Background

      The ANSI Standard C++ has a very large collection of libraries. Some of these define some new data types. The jargon name is the STL or Standard Template Library. Some are not in Sebesta's 4th chapter. The details of the implementation of these libraries is covered in CSCI330 (Data Structures). Techniques for choosing and using these libraries are covered in CSCI201 and CS202 [ stl.html ] but here we describe some of the data types in the STL.

      Standard Templates

      Standard for C++ requires there to be special libraries that implement these data types:
      1. <vector> (A dynamic array)
      2. <map> (An associative array)
      3. <list> (A randomly changing sequence of items)
      4. <stack> (A sequence of items with pop and push at one end only)
      5. <queue> (A Sequence of items with pop and push at opposite ends)
      6. <deque> (Double Ended Queue with pop and push at both ends)
      7. <bitset> (A subset of of a fixed and small set of items)
      8. <set> (An unordered collection of items)

      These are designed to be general, efficient, and powerful rather than easy to use. All of them can hold any type of data because they are templates. The data stored in them is described as an argument when the data type is\ used.
      TemplateCommonpush/popitemsExtras
      stackempty(), size()pop(),push(T)top()-
      queueempty(), size()pop(),push(T)front(),back()-
      vectorempty(), size()push_back(T), pop_back()front(), back()[int], at(int), =
      listempty(), size()push_back(), pop_back(), push_front(T), pop_front()front(), back()sort(), clear(), reverse(), merge(l),at(int), =

      Vectors

      Vectors are good when we have an unknown sequence of items to store but we want to access the by their sequence numbers. To be able to use STL vectors add this before you start using them in your source code:
       	#include <vector>

      Suppose that T is any type or class - say an int, a float, a struct, or a class, then

       	vector<T> v;
      declares a new and empty vector called v. Given object v declare like the above:

      Stacks

      Stacks are only accessed at their top. To be able to use STL stacks in a file of C++ source code or a header file add
       	#include <stack>
      at the beginning of the file.

      Suppose that T is any type or class - say an int, a float, a struct, or a class, then

       	stack<T> s;
      declares a new and empty stack called s. Given s you can:

      Queues

      Queues allow data to be added at one end and taken out of the other end. To be able to use STL queues add this before you start using them in your source code:
       	#include <queue>
      Suppose that T is any type or class - say an int, a float, a struct, or a class, then
       	queue<T> q;
      declares a new and empty queue called q. Given an object q:

      Lists

      Lists are good when data needs to be reorganized a lot. To be able to use STL lists add this before you start using them in your source code:
       	#include <list>

      Suppose that T is any type or class - say an int, a float, a struct, or a class, then

       	list<T> l;
      declares a new and empty list called l. Given an object l:

      Containers

      A Container is a data structure that holds a number of object of the same type or class. The oldest example of a Container in C++ is an array. Even in C you had arrays and you would typically write code like this:
       	const int MAX = 10;
       	float a[MAX];
       	...
       	for(int i=0; i<10; ++i)
       		process(a[i]);
       	...
      Lists, Vectors, Stacks, Queues, etc are all Containers.

      C arrays were designed so that they could be accessed by using a variable that stores the address of an item. These variables are called pointers. They are used like this with an array:

       	for(float *p=a; p!=p+MAX; ++p)
       		process(*p);
       	...

      Iterators

      Items in Containers are referred to be special objects called: iterators. They are generalization of C's pointers. With an iterator class Iter you can process each item in a vector or a list by similar code:
       	for( Iter p=c.begin(); p!=c.end(); ++p)
       		process(*p);

      All Containers C in the STL have a number of iterator objects. Container class C has an iterator called

       		C::iterator
      For any type T, list<T> and vector<T> are Containers. So there are iterator classes called
       		list<T>::iterator
      and they are used like this:
       	for( list<T>::iterator p=c.begin(); p!=c.end(); ++p)
       		process(*p);

      Vector iterators have type

       		vector<T>::iterator
      and used like this:
       	for( vector<T>::iterator p=c.begin(); p!=c.end(); ++p)
       		process(*p);

      If you change your choice from a vector to a list then the code is almost identical. This makes your code easier to modify.

      For any container class C of objects type T and any object c of type C:

      Lists and Iterators

      Insertion and deletion of items at the start or inside a List of elements is controlled by an iterator:

      Algorithms

      Iterators are used several useful functions and algorithms in the STL. Suppose you have a type or class of data called T and in a program are working with a vector v of type vector<T> then
       		vector<T>::iterator
      is the class of suitable iterators. Here are two useful values:
      		v.begin()
       		v.end()
      These always form a range of all the items in v from the front up to and including the back. You can sort a vector v simply by writing:
      		sort(c.begin(), c.end());

      More

      These notes only scratch the surface of the STL. It does not mention: For a complete description you need either a copy of the standard or a good book. A computer Science Data Structures (CS2) class like CSUSB's CS330 will teach you how these data structures are implemented. The are many useful resources on the world wide web, see [ c++.html$STL ]

      Glossary

    1. associative::=A type of container that associates a key with a data item when the data is stored and uses the key to retrieve the item.

    2. back::=a special item in a sequential container that has no items after it.

    3. container::=A data structure which contains a number of data items that can gain and lose items as the program runs. Examples include vectors, lists, stacks, ...

    4. contiguous::=a way of implementing data structures so that a continuous block of storage is used and items are found by calculating the address. See Vectors.

    5. front::=a special item in a sequential container that has no other items before it.

    6. generic::code= a function or class that is a template and can be used for data of many different types depending on its parameters.

    7. increment::operation=moving an iterator/pointer/index on to the next iterator/pointer/index value commonly symbolized by ++ in C-like languages.

    8. iterator::=An object that refers to an item in a container and used commonly used in for_loops and generic code. Iterators for sequential containers have two special values: begin and end. The begin value refers to the front item. The end value is a not the back but referee to a nonexistent item after the back of the container. See NULL.

    9. linked::=a way of implementing data structures where storage is allocated and deleted as it is needed item by item and the items are linked together by a pointer. For example see Lists.

    10. list::container=a sequential container that is optimized to all items to be inserted and erased at any point in the container. [ Lists ]

    11. NULL::=the C and C++ standard constant used to indicate that a pointer does not contain an address. In tests this value is converted to the boolean false. It is often used as a sentinel indicating the end of a linked data structure.

    12. operation::=something that can be applied to an object to extract information from it or to change its state.

    13. pop::operation=to add a new item to one or other end of a sequential container.
    14. push::operation=to remove an item from one or other end of a sequential container.

    15. pointer::=a piece of storage that contains either a NULL value or a single address of another piece of storage.

    16. queue::container=a sequential container where pop adds data at the back and push removes data from the front. See Queues. A queue is used in simulations and operating systems when items have to be stored and their order preserved.

    17. random_access::=being able to do things to items in a container in any unpredictable order typically by using an integer as an index or subscript.

    18. range::=a pair of iterators pointing to items in the same sequential container such that a number of steps would move the first iterator to the next one.

    19. sequential::=A type of container that stores data in a particular order and uses this sequence to access them. Sequential containers have a front and back element and a size. You can push and pop items into or from a sequential container.

    20. stack::container=a sequential container where pop and push both act at the front (called the top) and where only the top item is accessible at any time. A Stack is useful when something has to be stored while we do something else that might involve saving some more data and so on. The data is retrieved in the reverse order to which it is inserted. See Stacks.

    21. STL::=The Standard Template Library. [ Standard Templates ]

    22. TBA::=To Be Announced -- I'm working on this piece of text.

    23. vector::container=a vector is a sequential container that is optimized to allow efficient random_access of items by using an index. Vectors are are allocated in a contiguous block of space. Vectors are useful whenever data must be stored in one order accessed in a different one. A vector is a dynamic array - an array that can grow when needed. [ Vectors ]

    . . . . . . . . . ( end of section New Data Types in The C++ Standard Template Library) <<Contents | End>>

End