www.gibmonks.com

Main Page




Previous Page
Next Page

[Page 1192 (continued)]

Summary

  • The Standard Template Library defines powerful, template-based, reusable components that implement many common data structures, and algorithms used to process those data structures.

  • The STL has three key componentscontainers, iterators and algorithms.

  • The STL containers are data structures capable of storing objects of any data type. There are three container categoriesfirst-class containers, adapters and near containers.

  • STL algorithms are functions that perform such common data manipulations as searching, sorting and comparing elements or entire containers.

  • The containers are divided into three major categoriessequence containers, associative containers and container adapters.

  • The sequence containers represent linear data structures, such as vectors and linked lists.

  • Associative containers are nonlinear containers that quickly locate elements stored in them, such as sets of values or key/value pairs.

  • Sequence containers and associative containers are collectively referred to as first-class containers.

  • First-class container function begin returns an iterator pointing to the first element of a container. Function end returns an iterator pointing to the first element past the end of the container (an element that doesn't exist and is typically used in a loop to indicate when to terminate processing of the container's elements).

  • An istream_iterator is capable of extracting values in a type-safe manner from an input stream. An ostream_iterator is capable of inserting values in an output stream.

  • Input and output iterators can move only in the forward direction (i.e., from the beginning of the container to the end) one element at a time.

  • A forward iterator combines the capabilities of input and output iterators.

  • A bidirectional iterator has the capabilities of a forward iterator and the ability to move in the backward direction (i.e., from the end of the container toward the beginning).

  • A random-access iterator has the capabilities of a bidirectional iterator and the ability to directly access any element of the container.

  • Containers that support random-access iterators, such as vector, can be used with all algorithms in the STL.

  • The STL provides three sequence containersvector, list and deque. Class template vector and class template deque both are based on arrays. Class template list implements a linked-list data structure.

  • Function capacity returns the number of elements that can be stored in a vector before the vector dynamically resizes itself to accommodate more elements.

  • Sequence container function push_back adds an element to the end of a container.


  • [Page 1193]
  • To use the algorithms of the STL, you must include the header file <algorithm>.

  • Algorithm copy copies each element in a container starting with the location specified by the iterator in its first argument and up tobut not includingthe location specified by the iterator in its second argument.

  • Function front returns a reference to the first element in a sequence container. Function begin returns an iterator pointing to the beginning of a sequence container.

  • Function back returns a reference to the last element in a sequence container. Function end returns an iterator pointing to the element one past the end of a sequence container.

  • Sequence container function insert inserts value(s) before the element at a specific location.

  • Function erase (available in all first-class containers) removes specific element(s) from the container.

  • Function empty (available in all containers and adapters) returns true if the container is empty.

  • Function clear (available in all first-class containers) empties the container.

  • The list sequence container provides an efficient implementation for insertion and deletion operations at any location in the container. Header file <list> must be included to use class template list.

  • The list member function push_front inserts values at the beginning of a list.

  • The list member function sort arranges the elements in the list in ascending order.

  • The list member function splice removes elements in one list and inserts them into another list at a specific position.

  • The list member function unique removes duplicate elements in a list.

  • The list member function assign replaces the contents of one list with the contents of another.

  • The list member function remove deletes all copies of a specified value from a list.

  • Class template deque provides the same operations as vector, but adds member functions push_front and pop_front to allow insertion and deletion at the beginning of a deque, respectively. Header file <deque> must be included to use class template deque.

  • The STL's associative containers provide direct access to store and retrieve elements via keys.

  • The four associative containers are multiset, set, multimap and map.

  • Class templates multiset and set provide operations for manipulating sets of values where the values are the keysthere is not a separate value associated with each key. Header file <set> must be included to use class templates set and multiset.

  • The primary difference between a multiset and a set is that a multiset allows duplicate keys and a set does not.

  • Class templates multimap and map provide operations for manipulating values associated with keys.

  • The primary difference between a multimap and a map is that a multimap allows duplicate keys with associated values to be stored and a map allows only unique keys with associated values.

  • Function count (available to all associative containers) counts the number of occurrences of the specified value currently in a container.

  • Function find (available to all associative containers) locates a specified value in a container.

  • Functions lower_bound and upper_bond (available in all associative containers) locate the earliest occurrence of the specified value in a container and the element after the last occurrence of the specified value in a container, respectively.

  • Function equal_range (available in all associative containers) returns a pair containing the results of both a lower_bound and an upper_bound operation.


  • [Page 1194]
  • The multimap associative container is used for fast storage and retrieval of keys and associated values (often called key/value pairs).

  • Duplicate keys are allowed in a multimap, so multiple values can be associated with a single key. This is called a one-to-many relationship.

  • Header file <map> must be included to use class templates map and multimap.

  • Duplicate keys are not allowed in a map, so only a single value can be associated with each key. This is called a one-to-one mapping.

  • A map is commonly called an associative array.

  • The STL provides three container adaptersstack, queue and priority_queue.

  • Adapters are not first-class containers, because they do not provide the actual data structure implementation in which elements can be stored and they do not support iterators.

  • All three adapter class templates provide member functions push and pop that properly insert an element into and remove an element from each adapter data structure, respectively.

  • Class template stack enables insertions into and deletions from the underlying data structure at one end (commonly referred to as a last-in, first-out data structure). Header file <stack> must be included to use class template stack.

  • The stack member function top returns a reference to the top element of the stack (implemented by calling function back of the underlying container).

  • The stack member function empty determines whether the stack is empty (implemented by calling function empty of the underlying container).

  • The stack member function size returns get the number of elements in the stack (implemented by calling function size of the underlying container).

  • Class template queue enables insertions at the back of the underlying data structure and deletions from the front of the underlying data structure (commonly referred to as a first-in, first-out data structure). Header file <queue> must be included to use a queue or a priority_queue.

  • The queue member function front returns a reference to the first element in the queue (implemented by calling function front of the underlying container).

  • The queue member function back returns a reference to the last element in the queue (implemented by calling function back of the underlying container).

  • The queue member function empty determines whether the queue is empty (implemented by calling function empty of the underlying container).

  • The queue member function size returns get the number of elements in the queue (implemented by calling function size of the underlying container).

  • Class template priority_queue provides functionality that enables insertions in sorted order into the underlying data structure and deletions from the front of the underlying data structure.

  • The common priority_queue operations are push, pop, top, empty and size.

  • Algorithms fill and fill_n set every element in a range of container elements to a specific value.

  • Algorithms generate and generate_n use a generator function to create values for every element in a range of container elements.

  • Algorithm equal compares two sequences of values for equality.

  • Algorithm mismatch compares two sequences of values and returns a pair of iterators indicating the location in each sequence of the mismatched elements.

  • Algorithm lexicographical_compare compares the contents of two character arrays.

  • Algorithm remove eliminates all elements with a specific value in a certain range.


  • [Page 1195]
  • Algorithm remove_copy copies all elements that do not have a specific value in a certain range.

  • Algorithm remove_if deletes all elements that satisfy the if condition in a certain range.

  • Algorithm remove_copy_if copies all elements that satisfy the if condition in a certain range.

  • Algorithm replace replaces all elements with a specific value in certain range.

  • Algorithm replace_copy copies all elements with a specific value in a certain range.

  • Algorithm replace_if replaces all elements that satisfy the if condition in a certain range.

  • Algorithm replace_copy_if copies all elements that satisfy the if condition in a certain range.

  • Algorithm random_shuffle reorders randomly the elements in a certain range.

  • Algorithm count counts the elements with a specific value in a certain range.

  • Algorithm count_if counts the elements that satisfy the if condition in a certain range.

  • Algorithm min_element locates the smallest element in a certain range.

  • Algorithm max_element locates the largest element in a certain range.

  • Algorithm accumulate sums the values in a certain range.

  • Algorithm for_each applies a general function to every element in a certain range.

  • Algorithm transform applies a general function to every element in a certain range and replaces each element with the result of the function.

  • Algorithm find locates a specific value in a certain range.

  • Algorithm find_if locates the first value in a certain range that satisfies the if condition.

  • Algorithm sort arranges the elements in a certain range in ascending order or an order specified by a predicate.

  • Algorithm binary_search determines whether a specific value is in a certain range.

  • Algorithm swap exchanges two values.

  • Algorithm iter_swap exchanges the two elements.

  • Algorithm swap_ranges exchanges the elements in a certain range.

  • Algorithm copy_backward copies elements in a certain range and places the elements in results backward.

  • Algorithm merge combines two sorted ascending sequences of values into a third sorted ascending sequence.

  • Algorithm unique removes duplicated elements in a sorted sequence of elements in a certain range.

  • Algorithm reverse reverses all the elements in a certain range.

  • Algorithm inplace_merge merges two sorted sequences of elements in the same container.

  • Algorithm unique_copy makes a copy of all the unique elements in the sorted sequence of values in a certain range.

  • Algorithm reverse_copy makes a reversed copy of the elements in a certain range.

  • The set function includes compares two sets of sorted values to determine whether every element of the second set is in the first set.

  • The set function set_difference finds the elements from the first set of sorted values that are not in the second set of sorted values (both sets of values must be in ascending order).

  • The set function set_intersection determines the elements from the first set of sorted values that are in the second set of sorted values (both sets of values must be in ascending order).

  • The set function set_symmetric_difference determines the elements in the first set that are not in the second set and the elements in the second set that are not in the first set (both sets of values must be in ascending order).


  • [Page 1196]
  • The set function set_union creates a set of all the elements that are in either or both of the two sorted sets (both sets of values must be in ascending order).

  • Algorithm lower_bound finds the first location in a sorted sequence of values at which the third argument could be inserted in the sequence such that the sequence would still be sorted in ascending order.

  • Algorithm upper_bound finds the last location in a sorted sequence of values at which the third argument could be inserted in the sequence such that the sequence would still be sorted in ascending order.

  • Algorithm make_heap takes a sequence of values in a certain range and creates a heap that can be used to produce a sorted sequence.

  • Algorithm sort_heap sorts a sequence of values in a certain range that are already arranged in a heap.

  • Algorithm pop_heap removes the top heap element.

  • Algorithms min and max determine the minimum of two elements and the maximum of two elements, respectively.

  • Class template bitset makes it easy to create and manipulate bit sets, which are useful for representing a set of bit flags.

  • A function object is an instance of a class that overloads operator().

  • STL provides many predefined function objects, which can be found in header <functional>.

  • Binary function objects are function objects that take two arguments and return a value. Class template binary_function is an empty base class for creating binary function objects.


Previous Page
Next Page