©Copyright 1996 Rogue Wave Software If you are accessing this for the first time, please read the licensing statement. Standard C++ Library also has a Class Reference. Standard C++ Library User Guide and Tutorial Welcome to the Standard C++ Library User Guide and Tutorial. You can view a Comprehensive Table of Contents showing all chapters, first- and second-level headings, or click on one of the chapter names below to go directly to that chapter. Each chapter begins with a chapter-level table of contents.
Chapter 10: stack and queue Chapter 11: priority_queue Chapter 12: String Chapter 13: Generic Algorithms Chapter 14: Ordered Collection Algorithms Chapter 15: Using Allocators Chapter 16: Building Containers & Generic Algorithms Chapter 17: The Traits Parameter Chapter 18: Exception Handling Chapter 19: auto_ptr Chapter 20: Complex Chapter 21: Numeric Limits Chapter 22: Glossary
Click on the banner to return to the user guide home page.
Chapter 3: Functions and Predicates ❍ Functions ❍ Predicates ❍ Function Objects ❍ Negators and Binders Chapter 4: Container Classes ❍ Overview ❍ Selecting a Container ❍ Memory Management Issues ❍ Container Types Not Found in the Standard Library Chapter 5: vector and vector ❍ The vector Data Abstraction ■ ❍ Include Files Vector Operations ■ Declaration and Initialization of Vectors ■ Type Definitions ■ Subscripting a Vector ■ Extent and Size-Changing Operations ■ Insertin
❍ ■ Declaration and Initialization of Lists ■ Type Definitions ■ Placing Elements into a List ■ Removing Elements ■ Extent and Size-Changing Operations ■ Access and Iteration ■ Test for Inclusion ■ Sorting and Sorted List Operations ■ Searching Operations ■ In Place Transformations ■ Other Operations Example Program - An Inventory System Chapter 7: deque ❍ The Deque Data Abstraction ■ Include Files ❍ Deque Operations ❍ Example Program - Radix Sort Chapter 8: set, multiset, and
❍ The bitset Abstraction ■ Include Files ■ Declaration and Initialization of bitset ■ Accessing and Testing Elements ■ Set operations ■ Conversions Chapter 9: map and multimap ❍ The map Data Abstraction ■ ❍ ❍ Include files Map and Multimap Operations ■ Declaration and Initialization of map ■ Type Definitions ■ Insertion and Access ■ Removal of Values ■ Iterators ■ Searching and Counting ■ Element Comparisons ■ Other Map Operations Example Programs ■ A Telephone Database ■
■ Declaration and Initialization of queue ■ Example Program - Bank Teller Simulation Chapter 11: priority_queue ❍ The priority queue Data Abstraction ■ ❍ The Priority Queue Operations ■ ❍ Include Files Declaration and Initialization of priority queue Application - Event-Driven Simulation ■ An Ice Cream Store Simulation Chapter 12: String ❍ The string Abstraction ■ ❍ ❍ Include Files String Operations ■ Declaration and Initialization of string ■ Resetting Size and Capacity ■ Assignment,
❍ ❍ ❍ ❍ ❍ ❍ ■ Initialize a Sequence with Generated Values ■ Swap Values from Two Parallel Ranges Searching Operations ■ Find an Element Satisfying a Condition ■ Find Consecutive Duplicate Elements ■ Find a Subsequence within a Sequence ■ Locate Maximum or Minimum Element ■ Locate the First Mismatched Elements in Parallel Sequences In-Place Transformations ■ Reverse Elements in a Sequence ■ Replace Certain Elements With Fixed Value ■ Rotate Elements Around a Midpoint ■ Partition a
Chapter 14: Ordered Collection Algorithms ❍ Overview ■ Include Files ❍ Sorting Algorithms ❍ Partial Sort ❍ nth Element ❍ Binary Search ❍ Merge Ordered Sequences ❍ Set Operations ❍ Heap Operations Chapter 15: Using Allocators ❍ An Overview of the Standard Library Allocators ❍ Using Allocators with Existing Standard Library Containers ❍ Building Your Own Allocators ■ Using the Standard Allocator Interface ■ Using Rogue Wave's Alternative Interface ■ How to Support Both Interfaces C
Chapter 17: The Traits Parameter ❍ Using the Traits Technique Chapter 18: Exception Handling ❍ Overview ■ Include Files ❍ The Standard Exception Hierarchy ❍ Using Exceptions ❍ Example Program Chapter 19: auto_ptr ❍ Overview ■ Include File ❍ Declaration and Initialization of Auto Pointers ❍ Example Program Chapter 20: Complex ❍ Overview ■ ❍ ❍ Include Files Creating and Using Complex Numbers ■ Declaring Complex Numbers ■ Accessing Complex Number Values ■ Arithmetic Operations ■ C
Chapter 21: Numeric Limits ❍ Overview ❍ Fundamental Data Types ❍ Numeric Limit Members ■ Members Common to All Types ■ Members Specific to Floating Point Values Chapter 22: Glossary
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software What is the Standard C++ Library? The International Standards Organization (ISO) and the American National Standards Institute (ANSI) are completing the process of standardizing the C++ programming language. A major result of this standardization process is the "Standard C++ Library," a large and comprehensive collection of classes and functions.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Does the Standard C++ Library Differ From Other Libraries? A major portion of the Standard C++ Library is a collection of class definitions for standard data structures and a collection of algorithms commonly used to manipulate such structures. This part of the library was formerly known as the Standard Template Library or STL.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software What are the Effects of Non-Object-Oriented Design? The STL portion of the Standard C++ Library was purposely designed with an architecture that is not object-oriented. This design has side effects, some advantageous, and some not, that developers must be aware of as they investigate how to most effectively use the library. We'll discuss a few of them here.
It is very important to know that iterators can become invalidated as a result of a subsequent insertion or deletion from the underlying container class. This invalidation is not checked, and use of an invalid iterator can produce unexpected results. Familiarity with the Standard C++ Library will help reduce the number of errors related to iterators.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software How Should I Use the Standard C++ Library? Within a few years the Standard C++ Library will be the standard set of classes and libraries delivered with all ANSI-conforming C++ compilers. We have noted that the design of a large portion of the Standard C++ Library is in many ways not object-oriented. On the other hand, C++ excels as a language for manipulating objects.
classes are intended to stand alone as a library or are tailored to a specific task.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Reading This Manual This manual is an introduction to the Rogue Wave implementation of the Standard C++ Library. It assumes that you are already familiar with the basics features of the C++ programming language. If you are new to C++ you may wish to examine an introductory text, such as the book The C++ Programming Language, by Bjarne Stroustrup (Addison-Wesley, 1991).
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Conventions We use distinctinve fonts for class_names and function_names() When we wish to refer to a function name or algorithm name but not draw attention to the arguments, we will follow the function name with an empty pair of parentheses. We do this even when the actual function invocation requires additional arguments.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Using the Standard Library Because the Standard C++ Library consists largely of template declarations, on most platforms it is only necessary to include in your programs the appropriate header files. These header files will be noted in the text that describes how to use each algorithm or class.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Running the Tutorial Programs All the tutorial programs described in this text have been gathered together and are available as part of the distribution package. You can compile and run these programs, and use them as models for your own programming problems. Many of these example programs have been extended with additional output commands that are not reproduced here in the text.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Introduction to Iterators Iterators Fundamental to the use of the container classes and the associated algorithms provided by the standard library is the concept of an iterator. Abstractly, an iterator is simply a pointer-like object used to cycle through all the elements stored in a container.
for the purpose. In either case, it is not proper to dereference an iterator that is being used to specify the end of a range. Just as with conventional pointers, the fundamental operation used to modify an iterator is the increment operator (operator ++). When the increment operator is applied to an iterator that denotes the final value in a sequence, it will be changed to the "past the end" value.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Varieties of Iterators There are five basic forms of iterators used in the standard library: input iterator read only, forward moving output iterator write only, forward moving forward iterator both read and write, forward moving bidirectional iterator read and write, forward and backward moving random access iterator read and write, random access Iterator categories are hierarchical.
random access iterator ordinary pointers vector deque In the following sections we will describe the capabilities and construction of each form of iterator. Input Iterators Input iterators are the simplest form of iterator. To understand their capabilities, consider an example program. The find() generic algorithm (to be described in more detail in Chapter 13: Find an Element Satisfying a Condition), performs a simple linear search, looking for a specific value being held within a container.
int * where = find(data, data+100, 7); Note that constant pointers, pointers which do not permit the underlying array to be modified, can be created by simply placing the keyword const in a declaration. const int * first = data; const int * last = data + 100; // can't modify location returned by the following const int * where = find(first, last, 7); Container iterators. All of the iterators constructed for the various containers provided by the standard library are at least as general as input iterators.
As we noted earlier, ordinary pointers, as well as all the iterators constructed by containers in the standard library, can be used as examples of output iterators. (Ordinary pointers are random access iterators, which are a superset of output iterators.) So, for example, the following code fragment copies elements from an ordinary C-style array into a standard library vector: int data[100]; vector newdata(100); ... copy (data, data+100, newdata.
through the elements of a container. For example, we can use bidirectional iterators in a function that reverses the values of a container, placing the results into a new container.
randomInteger() The program will cycle as long as first is denoting a position that occurs earlier in the sequence than the one denoted by last. Only random access iterators can be compared using relational operators; all other iterators can be compared only for equality or inequality. On each cycle through the loop, the expression last - first yields the number of elements between the two limits. The function randomInteger() is assumed to generate a random number between 0 and the argument.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Stream Iterators Stream iterators are used to access an existing input or output stream using iterator operations. Input Stream Iterators Stream Iterators As we noted in the discussion of input iterators, the standard library provides a mechanism to turn an input stream into an input iterator. This ability is provided by the class istream_iterator.
values from a vector into the standard output, and separates each value by a space: copy (newdata.begin(), newdata.end(), ostream_iterator (cout, " ")); Simple file transformation algorithms can be created by combining input and output stream iterators and the various algorithms provided by the standard library.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Insert Iterators Assignment to the dereferenced value of an output iterator is normally used to overwrite the contents of an existing location. For example, the following invocation of the function copy() transfers values from one vector to another, although the space for the second vector was already set aside (and even initialized) by the declaration statement: vector a(10); vector b(10); ... copy (a.
The following simple program illustrates the use of all three forms of insert iterators. First, the values 3, 2 and 1 are inserted into the front of an initially empty list. Note that as it is inserted, each value becomes the new front, so that the resultant list is ordered 1, 2, 3. Next, the values 7, 8 and 9 are inserted into the end of the list. Finally, the find() operation is used to locate an iterator that denotes the 7 value, and the numbers 4, 5 and 6 are inserted immediately prior.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Iterator Operations The standard library provides two functions that can be used to manipulate iterators. The function advance() takes an iterator and a numeric value as argument, and modifies the iterator by moving the given amount.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Functions A number of algorithms provided in the standard library require functions as arguments. A simple example is the algorithm for_each(), which invokes a function, passed as an argument, on each value held in a container.
transform (words.begin(), words.end(), counts.begin(), words.begin(), stringRepeat); Transforming the words one, two, three with the values 3, 2, 3 would yield the result oneoneone, twotwo, threethreethree.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Predicates A predicate is simply a function that returns either a boolean (true/false) value or an integer value. Following the normal C convention, an integer value is assumed to be true if non-zero, and false otherwise.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Function Objects A function object is an instance of a class that defines the parenthesis operator as a member function. There are a number of situations where it is convenient to substitute function objects in place of functions. When a function object is used as a function, the parenthesis operator is invoked whenever the function is called.
to improve execution by using inline function calls, or to allow a function object to access or set state information that is held by an object. We will give examples of each. The following table illustrates the function objects provided by the standard library.
typedef Arg argument_type; typedef Result result_type; }; template struct binary_function { typedef Arg1 first_argument_type; typedef Arg2 second_argument_type; typedef Result result_type; }; An example of the use of these functions is found in Chapter 6. Here we want to take a binary function of type "Widget" and an argument of type integer, and compare the widget identification number against the integer value.
incremented. Using this object, the following call on the standard library function generate() will initialize a vector of 20 elements with the values 1 through 20: vector aVec(20); generate (aVec.begin(), aVec.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Negators and Binders Negators and binders are function adaptors that are used to build new function objects out of existing function objects. Almost always, these are applied to functions as part of the process of building an argument list prior to invoking yet another function or generic algorithm.
find_if(on_hand.begin(), on_hand.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Overview The standard library provides no fewer than ten alternative forms of container. In this section we will briefly describe the varieties, considering the characteristics of each, and discuss how you might go about selecting which container to use in solving a particular problem. Subsequent sections will then go over each of the different containers in more detail.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Selecting a Container The following series of questions can help you determine which type of container is best suited for solving a particular problem. How are values going to be accessed? If random access is important, than a vector or a deque should be used. If sequential access is sufficient, then one of the other structures may be suitable.
Is the collection indexed? That is, can the collection be viewed as a series of key/value pairs? If the keys are integers between 0 and some upper limit, a vector or deque should be employed. If, on the other hand, the key values are some other ordered data type (such as characters, strings, or a user-defined type), the map container can be used.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Memory Management Issues Containers in the standard library can maintain a variety of different types of elements. These include the fundamental data types (integer, char, and so on), pointers, or user-defined types. Containers cannot hold references. In general, memory management is handled automatically by the standard container classes, with little interaction by the programmer.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Container Types Not Found in the Standard Library There are a number of "classic" container types that are not found in the standard library. In most cases, the reason is that the containers that have been provided can easily be adapted to a wide variety of uses, including those traditionally solved by these alternative collections. There is no tree collection that is described as such.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software The vector Data Abstraction The vector container class generalizes the concept of an ordinary C array. Like an array, a vector is an indexed data structure, with index values that range from 0 to one less than the number of elements contained in the structure. Also like an array, values are most commonly assigned to and extracted from the vector using the subscript operator.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Vector Operations Each of the member functions provided by the vector data type will shortly be described in more detail. Note that while member functions provide basic operations, the utility of the data structure is greatly extended through the use of the generic algorithms described in Chapters 13 and 14.
Constructors and Iterators A vector can be assigned the values of another vector, in which case the target receives a copy of the argument vector. vec_three = vec_five; The assign() member function is similar to an assignment, but is more versatile and, in some cases, requires more arguments. Like an assignment, the existing values in the container are deleted, and replaced with the values specified by the arguments. There are two forms of assign().
difference_type A signed integer type, used to describe distances between iterators. Subscripting a Vector The value being maintained by a vector at a specific index can be accessed or modified using the subscript operator, just like an ordinary array. And, like arrays, there currently are no attempts to verify the validity of the index values (although this may change in future releases). Indexing a constant vector yields a constant reference.
with reserve() is larger than the current capacity, then a reallocation occurs and the argument value becomes the new capacity. (It may subsequently grow even larger; the value given as the argument need not be a bound, just a guess.) If the capacity is already in excess of the argument, then no reallocation takes place. Invoking reserve() does not change the size of the vector, nor the element values themselves (with the exception that they may potentially be moved should reallocation take place).
individual insertions, because with a single call at most one allocation will be performed. // find the location of the 7 vector::iterator where = find(vec_five.begin(), vec_five.end(), 7); // then insert the 12 before the 7 vec_five.insert(where, 12); vec_five.insert(where, 6, 14); // insert six copies of 14 The most general form of the insert() member function takes a position and a pair of iterators that denote a subsequence from another container.
if (num) cout << "contains a 17" << endl; else cout << "does not contain a 17" << endl; Initializing Count Sorting and Sorted Vector Operations A vector does not automatically maintain its values in sequence. However, a vector can be placed in order using the generic algorithm sort() (Chapter 14, Sorting Algorithms). The simplest form of sort uses for its comparisons the less-than operator for the element type.
Copy one sequence into another copy Copy values from a generator into a vector generate Find an element that matches a condition find Find consecutive duplicate elements adjacent_find Find a subsequence within a vector search Locate maximum or minimum element max_element, min_element Reverse order of elements reverse Replace elements with new values replace Rotate elements around a midpoint rotate Partition elements into two groups partition Generate permutations next_permutation Inpla
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Boolean Vectors Vectors of bit values (boolean 1/0 values) are handled as a special case by the standard library, so that the values can be efficiently packed (several elements to a word). The operations for a boolean vector , vector, are a superset of those for an ordinary vector, only the implementation is more efficient. One new member function added to the boolean vector data type is flip().
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Example Program - Sieve of Eratosthenes Obtaining the Source An example program that illustrates the use of vectors is the classic algorithm, called the sieve of Eratosthenes, used to discover prime numbers. A list of all the numbers up to some bound is represented by an integer vector.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software The list Data Abstraction The vector data structure is a container of relatively fixed size. While the standard library provides facilities for dynamically changing the size of a vector, such operations are costly and should be used only rarely. Yet in many problems, the size of a collection may be difficult to predict in advance, or may vary widely during the course of execution.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software List Operations The member functions provided by the list data type are described in more detail below. Note that while member functions provide basic operations, the utility of the data structure is greatly extended through the use of the generic algorithms described in Chapters 13 and 14. Declaration and Initialization of Lists Memory Management There are a variety of ways to declare a list.
output operations performed by the copy operation into list insertions. (See Chapter 2: Insert Iterators.) The inserter requires two arguments; the list into which the value is to be inserted, and an iterator indicating the location at which values will be placed. Insert iterators can also be used to copy elements into an arbitrary location in an existing list. list list_seven (aVector.begin(), aVector.end()); // the following is equivalent to the above list list_eight; copy (aVector.
Type Definitions The class list includes a number of type definitions. The most common use for these is in declaration statements. For example, an iterator for a list of integers can be declared as follows: list::iterator location; In addition to iterator, the following types are defined: value_type The type associated with the elements the list maintains. const_iterator An iterator that does not allow modification of the underlying sequence.
an iterator denoting the location of the inserted value. This result value was ignored in the invocations shown above. // find the location of the first occurrence of the // value 5 in list list::iterator location = find(list_nine.begin(), list_nine.end(), 5); // and insert an 11 immediate before it location = list_nine.insert(location, 11); It is also possible to insert a fixed number of copies of an argument value. This form of insert() does not yield the location of the values. line_nine.
list_eleven.swap(list_twelve); Removing Elements Just as there are a number of different ways to insert an element into a list, there are a variety of ways to remove values from a list. The most common operations used to remove a value are pop_front() or pop_back(), which delete the single element from the front or the back of the list, respectively. These member functions simply remove the given element, and do not themselves yield any useful result.
unique(). In this case the more general unique() generic algorithm can be used (see Chapter 13: Remove Overruns of Similar Values). In the following example the binary function is the greater-than operator, which will remove all elements smaller than a preceding element. // remove first from consecutive equal elements list_nine.unique(); // explicitly give comparison function list_nine.unique(greater()); // the following is equivalent to the above location3 = unique(list_nine.begin(), list_nine.
Condition) can be used for this purpose. The following statements, for example, test to see whether an integer list contains the element 17. int num = 0; count(list_five.begin(), list_five.end(), 17, num); if (num > 0) cout << "contains a 17" << endl; else cout << "does not contain a 17" << endl; if (find(list_five.begin(), list_five.end(), 17) != list_five.
value one. The version of transform() that manipulates two parallel sequences can be used in a similar fashion. transform(list_ten.begin(), list_ten.end(), list_ten.begin(), bind1st(plus(), 1)); Similarly, the functions replace() and replace_if() (Section 12.4.2) can be used to replace elements of a list with specific values. Rotations ( Chapter 13: Rotate Elements Around a Midpoint) and partitions (Chapter 13: Partition a Sequence...), can also be performed with lists.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Example Program - An Inventory System Obtaining the Sample Program We will use a simple inventory management system to illustrate the use of several list operations. Assume a business, named WorldWideWidgetWorks, requires a software system to manage their supply of widgets.
list::iterator weneed = find (on_order.begin(), on_order.end(), wid); if (weneed != on_order.end()) { cout << "Ship " << Widget(wid) << " to fill back order" << endl; on_order.erase(weneed); } else on_hand.push_front(Widget(wid)); } When a customer orders a new widget, we scan the list of widgets in stock to determine if the order can be processed immediately. We can use the function find_if() to search the list.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software The Deque Data Abstraction The name "deque" is short for "double-ended queue," and is pronounced like "deck." Traditionally, the term is used to describe any data structure that permits both insertions and removals from either the front or the back of a collection. The deque container class permits this, as well as much more.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Deque Operations A deque is declared in the same fashion as a vector, and includes within the class the same type definitions as vector. The begin() and end() member functions return random access iterators, rather than bidirectional iterators, as they do for lists.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Example Program - Radix Sort The radix sort algorithm is a good illustration of how lists and deques can be combined with other containers. In the case of radix sort, a vector of deques is manipulated, much like a hash table. Obtaining the Sample Program Radix sorting is a technique for ordering a list of positive integer values. The values are successively ordered on digit positions, from right to left.
The value of the variable divisor indicates which digit is currently being examined. A boolean flag is used to determine when execution should halt. Each time the while loop is executed a vector of deques is declared. By placing the declaration of this structure inside the while loop, it is reinitialized to empty each step. Each time the loop is executed, the values in the list are copied into the appropriate bucket by executing the function copyIntoBuckets() on each value.
(int d, vector< deque > & b, bool & f) : divisor(d), buckets(b), flag(f) {} int divisor; vector > & buckets; bool & flag; void operator () (unsigned int v) { int index = (v / divisor) % 10; // flag is set to true if any bucket // other than zeroth is used if (index) flag = true; buckets[index].
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software The set Data Abstraction Sets, Ordered and Not A set is a collection of values. Because the container used to implement the set data structure maintains values in an ordered representation, sets are optimized for insertion and removal of elements, and for testing to see whether a particular value is contained in the collection.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software set and multiset Operations Sets and Bags The member functions provided by the set and multiset data types will shortly be described in more detail. Note that while member functions provide basic operations, the utility of these data structures is greatly extended through the use of the generic algorithms described in Chapters 13 and 14.
set set_six (set_four); // copy constructor A set can be assigned to another set, and two sets can exchange their values using the swap() operation (in a manner analogous to other standard library containers). set_one = set_five; set_six.swap(set_two); Type Definitions The classes set and multiset include a number of type definitions. The most common use for these is in a declaration statement.
Insertions of several elements from another container can also be performed using an iterator pair: set_one.insert (set_three.begin(), set_three.end()); The pair data structure is a tuple of values. The first value is accessed through the field name first, while the second is, naturally, named second. A function named make_pair() simplifies the task of producing an instance of class pair.
Searching and Counting The member function size() will yield the number of elements held by a container. The member function empty() will return a boolean true value if the container is empty, and is generally faster than testing the size against zero. The member function find() takes an element value, and returns an iterator denoting the location of the value in the set if it is present, or a value matching the end-of-set (the value yielded by the function end()) if it is not.
Subset test The function includes() can be used to determine if one set is a subset of another; that is, if all elements from the first are contained in the second. In the case of multisets the number of matching elements in the second set must exceed the number of elements in the first. The four arguments are a pair of iterators representing the (presumably) smaller set, and a pair of iterators representing the (potentially) larger set. if (includes(set_one.begin(), set_one.end(), set_two.begin(), set_two.
while the merge will contain five. To form the merge, the function merge() can be used (see Chapter 14: Merge Ordered Sequences). The arguments to this function exactly match those of the set_union() function. Set Difference There are two forms of set difference. A simple set difference represents the elements in the first set that are not contained in the second.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Example Program: - A Spelling Checker Obtaining the Sample Program A simple example program that uses a set is a spelling checker. The checker takes as arguments two input streams; the first representing a stream of correctly spelled words (that is, a dictionary), and the second a text file. First, the dictionary is read into a set.
void findMisspell(stringset & words, string & word) { for (int i = 1; i < word.length(); i++) { swap(word[i-1], word[i]); if (words.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software The bitset Abstraction A bitset is really a cross between a set and a vector. Like the vector abstraction vector, the abstraction represents a set of binary (0/1 bit) values. However, set operations can be performed on bitsets using the logical bit-wise operators. The class bitset does not provide any iterators for accessing elements.
bset_one[3] = 1; if (bset_one.test(4)) cout << "bit position 4 is set" << endl; if (bset_one.any()) cout << "some bit position is set" << endl; if (bset_one.none()) cout << "no bit position is set" << endl; The function set() can be used to set a specific bit. bset_one.set(i) is equivalent to bset_one[i] = true. Invoking the function without any arguments sets all bit positions to true.
The member function to_string() converts a bitset into an object of type string. The string will have as many characters as the bitset. Each zero bit will correspond to the character 0, while each one bit will be represented by the character 1.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software The map Data Abstraction Other Names for Maps A map is an indexed data structure, similar to a vector or a deque. However, maps differ from vectors or deques in two important respects. First, in a map, unlike a vector or deque, the index values (called the key values) need not be integer, but can be any ordered data type. For example, maps can be indexed by real numbers, or by strings.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Map and Multimap Operations The member functions provided by the map and multimap data types will shortly be described in more detail. Note that while member functions provide basic operations, the utility of the data structure is greatly extended through the use of the generic algorithms described in Chapters 13 and 14.
key_type The type associated with the keys used to index the map. value_type The type held by the container, a key/value pair. const_iterator An iterator that does not allow modification of the underlying sequence. reverse_iterator An iterator that moves in a backward direction. const_reverse_iterator A combination constant and reverse iterator. reference A reference to an underlying value. const_reference A reference to an underlying value that will not permit the element to be modified.
// erase the 4th element 4 map_three.erase(4); // erase the 5th element mtesttype::iterator five = map_three.find(5); map_three.erase(five); // erase all values between the 7th and 11th elements mtesttype::iterator seven = map_three.find(7); mtesttype::iterator eleven = map_three.find(11); map_three.erase (seven, eleven); If the underlying element type provides a destructor, then the destructor will be invoked prior to removing the key and value pair from the collection.
later in this section. The member function count() returns the number of elements that match the key value supplied as the argument. For a map, this value is always either zero or one, whereas for a multimap it can be any nonnegative value. If you simply want to determine whether or not a collection contains an element indexed by a given key, using count() is often easier than using the find() function and testing the result against the end-of-sequence iterator. if (map_one.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Example Programs We present three example programs that illustrate the use of maps and multimaps. These are a telephone database, graphs, and a concordance. A Telephone Database Obtaining the Sample Program A maintenance program for a simple telephone database is a good application for a map.
Simple operations on our database are directly implemented by map commands. Adding an element to the database is simply an insert, removing an element is an erase, and updating is a combination of the two. To print all the entries in the database we can use the for_each() algorithm, and apply the following simple utility routine to each entry: void printEntry(const entry_type & entry) { cout << entry.first << ":" << entry.
the values into the new map, which will order the values by prefix. Once the new map is created, it is then printed. typedef map > sortedMap; typedef sortedMap::value_type sorted_entry_type; void telephoneDirectory::displayByPrefix() { cout << "Display by prefix" << endl; sortedMap sortedData; friendMap::iterator itr; for (itr = database.begin(); itr != database.end(); itr++) sortedData.insert(sortedMap::value_type((*itr).second, (*itr).first)); for_each(sortedData.
cityMap[pensacola][phoenix] = 5; cityMap[peoria][pittsburgh] = 5; cityMap[peoria][pueblo] = 3; cityMap[phoenix][peoria] = 4; cityMap[phoenix][pittsburgh] = 10; cityMap[phoenix][pueblo] = 3; cityMap[pierre][pendleton] = 2; cityMap[pittsburgh][pensacola] = 4; cityMap[princeton][pittsburgh] = 2; cityMap[pueblo][pierre] = 3; The type stringVector is a map of integers indexed by strings. The type graph is, in effect, a two-dimensional sparse array, indexed by strings and holding integer values.
string city = que.top().second; que.pop(); // if we haven't seen it already, process it if (0 == distances.count(city)) { // then add it to shortest distance map distances[city] = distance; // and put values into queue const stringVector & cities = cityMap[city]; stringVector::const_iterator start = cities.begin(); stringVector::const_iterator stop = cities.end(); for (; start != stop; ++start) que.push(DistancePair(distance + (*start).second, (*start).
void concordance::readText (istream & in) { string line; for (int i = 1; getline(in, line, '\n'); i++) { allLower(line); list words; split (line, " ,.;:", words); list::iterator wptr; for (wptr = words.begin(); wptr != words.end(); ++wptr) addWord(*wptr, i); } } Lines are read from the input stream one by one. The text of the line is first converted into lower case, then the line is split into words, using the function split() described in Chapter 19 (Example Program of auto_ptr).
lastword = (*pairPtr).first; cout << endl << lastword << ": " << (*pairPtr).second; } cout << endl; // terminate last line } An iterator loop is used to cycle over the elements being maintained by the word list. Each new word generates a new line of output - thereafter line numbers appear separated by spaces. If, for example, the input was the text: It was the best of times, it was the worst of times.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Overview Most people have a good intuitive understanding of the stack and queue data abstractions, based on experience with everyday objects. An excellent example of a stack is a pile of papers on a desk, or a stack of dishes in a cupboard. In both cases the important characteristic is that it is the item on the top that is most easily accessed.
Click on the banner to return to the user guide home page.
Example Program - A RPN Calculator A classic application of a stack is in the implementation of calculator. Input to the calculator consists of a text string that represents an expression written in reverse polish notation (RPN). Operands, that is, integer constants, are pushed on a stack of values. As operators are encountered, the appropriate number of operands are popped off the stack, the operation is performed, and the result is pushed back on the stack.
int left = data.top(); // read next top element data.pop(); // pop it from stack switch (theOp) { case plus: data.push(left + right); break; case minus: data.push(left - right); break; case times: data.push(left * right); break; case divide: data.
Click on the banner to return to the user guide home page.
Example Program - Bank Teller Simulation Obtaining the Sample Program Queues are often found in businesses, such as supermarkets or banks. Suppose you are the manager of a bank, and you need to determine how many tellers to have working during certain hours. You decide to create a computer simulation, basing your simulation on certain observed behavior. For example, you note that during peak hours there is a ninety percent chance that a customer will arrive every minute.
free = true; return free; } void addCustomer(Customer c) { customer = c; free = false; } // start serving new customer private: bool free; Customer customer; }; The main program is then a large loop, cycling once each simulated minute. Each minute a new customer is, with probability 0.9, entered into the queue of waiting customers. Each teller is polled, and if any are free they take the next customer from the queue.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software The priority queue Data Abstraction A priority queue is a data structure useful in problems where you need to rapidly and repeatedly find and remove the largest element from a collection of values. An everyday example of a priority queue is the "to do" list of tasks waiting to be performed that most of us maintain to keep ourselves organized.
Click on the banner to return to the user guide home page.
queue_five(aVector.begin(), aVector.end(), eventComparison); Queues constructed out of vectors tend to be somewhat smaller, while queues constructed out of deques can be somewhat faster, particularly if the number of elements in the queue varies widely over the course of execution. However, these differences are slight, and either form will generally work in most circumstances.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Application - Event-Driven Simulation An extended example will illustrate the use of priority queues. The example illustrates one of the more common uses for priority queues, which is to support the construction of a simulation model. A discrete event-driven simulation is a popular simulation technique.
the second runs the simulation. A data field is also provided to hold the current simulation "time." Storing Pointers versus Storing Values class simulation { public: simulation () : eventQueue(), time(0) { } void scheduleEvent (event * newEvent) { eventQueue.push (newEvent); } void run(); unsigned int time; protected: priority_queue, eventComparison> eventQueue; }; Notice the declaration of the priority queue used to hold the pending events.
bool canSeat (unsigned int numberOfPeople); void order(unsigned int numberOfScoops); void leave(unsigned int numberOfPeople); private: unsigned int freeChairs; double profit; } theSimulation; There are three basic activities associated with the store. These are arrival, ordering and eating, and leaving. This is reflected not only in the three member functions defined in the simulation class, but in three separate subclasses of event.
enters. When executed, the arrival event creates and installs a new instance of order event. The function randomInteger() (see Chapter 2: Random Access Iterators) is used to compute a random integer between 1 and the argument value.
} To run the simulation we simply create some number of initial events (say, 30 minutes worth), then invoke the run() member function. void main() { // load queue with some number of initial events unsigned int t = 0; while (t < 30) { t += rand(6); theSimulation.scheduleEvent( new arriveEvent(t, 1 + randomInteger(4))); } // then run simulation and print profits theSimulation.run(); cout << "Total profits " << theSimulation.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software The string Abstraction A string is basically an indexable sequence of characters. In fact, although a string is not declared as a subclass of vector, almost all of the vector operators discussed in Chapter 5 can be applied to string values.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software String Operations In the following sections, we'll examine the standard library operations used to create and manipulate strings. Declaration and Initialization of string The simplest form of declaration for a string simply names a new variable, or names a variable along with the initial value for the string. This form was used extensively in the example graph program given in 9 (Example, Graphs).
cout << s6.capacity() << endl; s6.reserve(200); cout << s6.capacity() << endl; cout << s6.max_size() << endl; // change capacity to 200 The member function length() is simply a synonym for size(). The member function resize() changes the size of a string, either truncating characters from the end or inserting new characters. The optional second argument for resize() can be used to specify the character inserted into the newly created character positions. s7.
Character Access An individual character from a string can be accessed or assigned using the subscript operator. The member function at() is a synonym for this operation. cout << s4[2] << endl; // output position 2 of s4 s4[2] = 'x'; // change position 2 cout << s4.at(2) << endl; // output updated value The member function c_str() returns a pointer to a null terminated character array, whose elements are the same as those contained in the string.
Copy and Substring The member function copy() generates a substring of the receiver, then assigns this substring to the target given as the first argument. The range of values for the substring is specified either by an initial position, or a position and a length. s3.copy (s4, 2); // assign to s4 positions 2 to end of s3 s5.copy (s4, 2, 3); // assign to s4 positions 2 to 4 of s5 The member function substr() returns a string that represents a portion of the current string.
character, if located, is returned. If no such character exists then a value out of the range of any legal subscript is returned. i = s2.find_first_of ("aeiou"); // find first vowel j = s2.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software An Example Function - Split a Line into Words Obtaining the Sample Program In this section we will illustrate the use of some of the string functions by defining a function to split a line of text into individual words. We have already made use of this function in the concordance example program in Chapter 9. There are three arguments to the function.
Click on the banner to return to the user guide home page.
❍ ❍ ❍ Scalar-Producing Algorithms ■ Count the Number of Elements that Satisfy a Condition ■ Reduce Sequence to a Single Value ■ Generalized Inner Product ■ Test Two Sequences for Pairwise Equality ■ Lexical Comparison Sequence-Generating Algorithms ■ Transform One or Two Sequences ■ Partial Sums ■ Adjacent Differences Miscellaneous Algorithms ■ Apply a Function to All Elements in a Collection
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Overview In this chapter and in Chapter 14 we will examine and illustrate each of the generic algorithms provided by the standard library. The names and a short description of each of the algorithms in this chapter are given in the following table. We have divided the algorithms into several categories, based on how they are typically used.
mismatch find first mismatch in parallel sequences in-place transformations Chapter 13 (In-Place Transformations) reverse reverse the elements in a sequence replace replace specific values with new value replace_if replace elements matching predicate rotate rotate elements in a sequence around a point partition partition elements into two groups stable_partition partition preserving original ordering next_permutation generate permutations in sequence prev_permutation generate permutations i
adjacent_difference generate sequence of adjacent differences miscellaneous operations Chapter 13 (Miscellaneous Operations for_each apply a function to each element of collection In this chapter we will illustrate the use of each algorithm with a series of short examples. Many of the algorithms are also used in the sample programs provided in the on the various container classes. These cross references have been noted where appropriate.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Initialization Algorithms Obtaining the source The first set of algorithms we will cover are those that are chiefly, although not exclusively, used to initialize a newly created sequence with certain values. The standard library provides several initialization algorithms. In our discussion we'll provide examples of how to apply these algorithms, and suggest how to choose one algorithm over another.
vector::iterator & seven = find(iVec.begin(), iVec.end(), 7); fill (iVec.begin(), seven, 0); } In example 1, an array of character values is declared. The fill() algorithm is invoked to initialize each location in this array with a null character value. The first 10 positions are then replaced with the character 'x' by using the algorithm fill_n().
● ● ● Adding elements into a sequence Copying a sequence from input or to output Converting a sequence from one form into another These are illustrated in the following sample program.
"prise". The second half of example 2 illustrates the use of the copy_backward() algorithm. This function performs the same task as the copy() algorithm, but moves elements from the end of the sequence first, progressing to the front of the sequence. (If you think of the argument as a string, characters are moved starting from the right and progressing to the left.) In this case the result will be that buffer will be assigned the value "priprise".
char labelBuffer[80]; ostrstream ost(labelBuffer, 80); ost << "L_" << lastLabel++ << '\0'; return string(labelBuffer); } void generate_example () // illustrate the use of the generate and generate_n algorithms { // example 1, generate a list of label values list labelList; generate_n (inserter(labelList, labelList.begin()), 4, generateLabel); // example 2, generate an arithmetic progression vector iVec(10); generate (iVec.begin(), iVec.end(), iotaGen(2)); generate_n (iVec.
The function is generalized to iterators in the function named iter_swap(). The algorithm swap_ranges() then extends this to entire sequences. The values denoted by the first sequence are exchanged with the values denoted by a second, parallel sequence. The description of the swap_ranges() algorithm is as follows: ForwardIterator swap_ranges (ForwardIterator first, ForwardIterator last, ForwardIterator first2); Parallel Sequences The second range is described only by a starting iterator.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Searching Operations The next category of algorithms we will describe are those that are used to locate elements within a sequence that satisfy certain properties.
Find an Element Satisfying a Condition There are two algorithms, find() and find_if(), that are used to find the first element that satisfies a condition. The declarations of these two algorithms are as follows: InputIterator find_if (InputIterator first, InputIterator last, Predicate); InputIterator find (InputIterator first, InputIterator last, const T&); The algorithm find_if() takes as argument a predicate function, which can be any function that returns a boolean value (see Chapter 3).
Find Consecutive Duplicate Elements The adjacent_find() algorithm is used to discover the first element in a sequence equal to the next immediately following element. For example, if a sequence contained the values 1 4 2 5 6 6 7 5, the algorithm would return an iterator corresponding to the first 6 value. If no value satisfying the condition is found, then the end-of-sequence iterator is returned.
Speed of Search Suppose, for example, that we wish to discover the location of the string "ration" in the string "dreams and aspirations". The solution to this problem is shown in the example program. If no appropriate match is found, the value returned is the past-the-end iterator for the first sequence.
Largest and Smallest Elements of a Set These algorithms return an iterator that denotes the largest or smallest of the values in a sequence, respectively. Should more than one value satisfy the requirement, the result yielded is the first satisfactory value. Both algorithms can optionally take a third argument, which is the function to be used as the comparison operator in place of the default operator. The example program illustrates several uses of these algorithms.
starting position, without an ending position. It is assumed (but not checked) that the second sequence contains at least as many elements as the first. The arguments and return type for mismatch() can be described as follows: pair mismatch (InputIterator first1, InputIterator last1, InputIterator first2 [, BinaryPredicate ] ); The elements of the two sequences are examined in parallel, element by element.
cout else if cout else cout cout << << " is equal to "; (*aDiffPosition < *bDiffPosition) << " is less than "; << " is greater than "; b << endl; } A second form of the mismatch() algorithm is similar to the one illustrated, except it accepts a binary predicate as a fourth argument. This binary function is used to compare elements, in place of the == operator.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software In-Place Transformations Obtaining the Source The next category of algorithms in the standard library that we examine are those used to modify and transform sequences without moving them from their original storage locations. A few of these routines, such as replace(), include a copy version as well as the original in-place transformation algorithms.
reverse (text, text + strlen(text)); cout << text << endl; // example 2, reversing a list list iList; generate_n (inserter(iList, iList.begin()), 10, iotaGen(2)); reverse (iList.begin(), iList.end()); } Replace Certain Elements With Fixed Value The algorithms replace() and replace_if() are used to replace occurrences of certain elements with a new value. In both cases the new value is the same, no matter how many replacements are performed.
replace_if (numbers.begin(), numbers.end(), isEven, 9); // illustrate copy versions of replace int aList[] = {2, 1, 4, 3, 2, 5}; int bList[6], cList[6], j; replace_copy (aList, aList+6, &bList[0], 2, 7); replace_copy_if (bList, bList+6, &cList[0], bind2nd(greater(), 3), 8); } The example program also illustrates the use of the replace_copy algorithms. First, an array containing the values 2 1 4 3 2 5 is created. This is modified by replacing the 2 values with 7, resulting in the array 7 1 4 3 7 5.
// now rotate around that location rotate (iList.begin(), middle, iList.end()); // rotate again around the same location list cList; rotate_copy (iList.begin(), middle, iList.end(), inserter(cList, cList.begin())); } The example program first creates a list of the integers in order from 1 to 10. Next, the find() algorithm (Find an Element Satisfying a Condition) is used to find the location of the element 7. This is used as the midpoint for the rotation.
// now put the even values low, odd high vector::iterator result = partition(numbers.begin(), numbers.end(), isEven); cout << "middle location " << result - numbers.begin() << endl; // now do a stable partition generate (numbers.begin(), numbers.end(), iotaGen(1)); stable_partition (numbers.begin(), numbers.end(), isEven); } The relative order of the elements within a partition in the resulting vector may not be the same as the values in the original vector.
while (next_permutation(start, start + 3)); // example 2, permute words char * words = {"Alpha", "Beta", "Gamma"}; do copy (words, words + 3, ostream_iterator (cout, " ")), cout << endl; while (next_permutation(words, words + 3, nameCompare)); // example 3, permute characters backwards char * word = "bela"; do cout << word << ' '; while (prev_permutation (word, &word[4])); cout << endl; } Example 3 in the sample program illustrates the use of the reverse permutation algorithm, which generates values
// then find the middle location vector::iterator midvec = find(numbers.begin(), numbers.end(), 1); // copy them into a list list numList; copy (numbers.begin(), numbers.end(), inserter (numList, numList.begin())); list::iterator midList = find(numList.begin(), numList.end, 1); // now merge the lists into one inplace_merge (numbers.begin(), midvec, numbers.end()); inplace_merge (numList.begin(), midList, numList.
}
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Removal Algorithms What is a Name? The following two algorithms can be somewhat confusing the first time they are encountered. Both claim to remove certain values from a sequence. But, in fact, neither one reduces the size of the sequence. Both operate by moving the values that are to be retained to the front of the sequence, and returning an iterator that describes where this sequence ends.
ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T &); ForwardIterator remove_if (ForwardIterator first, ForwardIterator last, Predicate); The algorithm remove() copies values to the front of the sequence, overwriting the location of the removed elements. All elements not removed remain in their relative order. Once all values have been examined, the remainder of the sequence is left unchanged.
aList.erase(where, aList.end()); } Remove Runs of Similar Values The algorithm unique() moves through a linear sequence, eliminating all but the first element from every consecutive group of equal elements. The argument sequence is described by forward iterators. ForwardIterator unique (ForwardIterator first, ForwardIterator last [, BinaryPredicate ] ); As the algorithm moves through the collection, elements are moved to the front of the sequence, overwriting the existing elements.
// remove trailing values aList.erase(where, aList.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Scalar-Producing Algorithms Obtaining the Source The next category of algorithms are those that reduce an entire sequence to a single scalar value. Remember that two of these algorithms, accumulate() and inner_product(), are declared in the numeric header file, not the algorithm header file as are the other generic algorithms.
first case the identity is zero, and the default operator + is used. In the second invocation the identity is 1, and the multiplication operator (named times) is explicitly passed as the fourth argument.
// example 1, a simple inner product int in1 = inner_product(a, a+3, b, 0); cout << "Inner product is " << in1 << endl; // example 2, user defined operations bool anyequal = inner_product(a, a+3, b, true, logical_or(), equal_to()); cout << "any equal? " << anyequal << endl; } Test Two Sequences for Pairwise Equality The equal() algorithm tests two sequences for pairwise equality.
InputInterator first2, InputIterator last2 [, BinaryFunction ] ); Unlike most of the other algorithms that take two sequences as an argument, the lexicographical_compare() algorithm, uses a first and past-end iterator for both sequences. A variation on the algorithm takes a fifth argument, which is the binary function used to compare the corresponding elements from the two sequences. The example program illustrates the use of this algorithm with character sequences, and with arrays of integer values.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Sequence-Generating Algorithms Obtaining the Source The algorithms described in this section are all used to generate a new sequence from an existing sequence by performing some type of transformation. In most cases, the output sequence is described by an output iterator. This means these algorithms can be used to overwrite an existing structure (such as a vector).
int square(int n) { return n * n; } void transform_example () // illustrate the use of the transform algorithm { // generate a list of value 1 to 6 list aList; generate_n (inserter(aList, aList.begin()), 6, iotaGen(1)); // transform elements by squaring, copy into vector vector aVec(6); transform (aList.begin(), aList.end(), aVec.begin(), square); // transform vector again, in place, yielding 4th powers transform (aVec.begin(), aVec.end(), aVec.
// output partial products partial_sum (aVec.begin(), aVec.end(), ostream_iterator (cout, " "), times() ); } Adjacent Differences An adjacent difference of a sequence is a new sequence formed by replacing every element with the difference between the element and the immediately preceding element. The first value in the new sequence remains unchanged.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Miscellaneous Algorithms In the final section we describe the remaining algorithms found in the standard library. Apply a Function to All Elements in a Collection The algorithm for_each() takes three arguments. The first two provide the iterators that describe the sequence to be evaluated. The third is a one-argument function.
void countCaps(char c) { if (isupper(c)) capCount++; } The following example counts the number of capital letters in a string value: string advice = "Never Trust Anybody Over 30!"; for_each(advice.begin(), advice.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Overview In this section we will describe the generic algorithms in the standard library that are specific to ordered collections.
set_union form union of two sets set_intersection form intersection of two sets set_difference form difference of two sets set_symmetric_difference form symmetric difference of two sets includes see if one set is a subset of another Heap operations Section Heap Operations make_heap turn a sequence into a heap push_heap add a new value to the heap pop_heap remove largest value from the heap sort_heap turn heap into sorted collection Ordered collections can be created using the standard libr
y) and Compare(y, x) are false. Note that this need not imply that x == y.
Click on the banner to return to the user guide home page.
// sort the vector ascending sort (aVec.begin(), aVec.end()); // sort the deque descending sort (aDec.begin(), aDec.end(), greater() ); // alternative way to sort descending sort (aVec.rbegin(), aVec.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Partial Sort The generic algorithm partial_sort() sorts only a portion of a sequence. In the first version of the algorithm, three iterators are used to describe the beginning, middle, and end of a sequence. If n represents the number of elements between the start and middle, then the smallest n elements will be moved into this range in order. The remaining elements are moved into the second region.
generate (aList.begin(), aList.end(), randomValue); // sort only the first seven elements vector start(7); partial_sort_copy (aList.begin(), aList.end(), start.begin(), start.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software nth Element Imagine we have the sequence 2 5 3 4 7, and we want to discover the median, or middle element. We could do this with the function nth_element(). One result might be the following sequence: 32|4|75 The vertical bars are used to describe the separation of the result into three parts; the elements before the requested value, the requested value, and the values after the requested value.
vector::iterator nth = aVec.begin() + 4; nth_element (aVec.begin(), nth, aVec.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Binary Search The standard library provides a number of different variations on binary search algorithms. All will perform only approximately log n comparisons, where n is the number of elements in the range described by the arguments. The algorithms work best with random access iterators, such as those generated by vectors or deques, when they will also perform approximately log n operations in total.
// illustrate the use of the binary search algorithm { // make an ordered vector of 15 random integers vector aVec(15); generate (aVec.begin(), aVec.end(), randomValue); sort (aVec.begin(), aVec.end()); // see if it contains an eleven if (binary_search (aVec.begin(), aVec.end(), 11)) cout << "contains an 11" << endl; else cout << "does not contain an 11" << endl; // insert an 11 and a 14 vector::iterator where; where = lower_bound (aVec.begin(), aVec.end(), 11); aVec.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Merge Ordered Sequences The algorithm merge() combines two ordered sequences to form a new ordered sequence. The size of the result is the sum of the sizes of the two argument sequences. This should be contrasted with the set_union() operation, which eliminates elements that are duplicated in both sets. The set_union() function will be described later in this section. The merge operation is stable.
merge (aVec.begin(), aVec.end(), aList.begin(), aList.end(), inserter(lResult, lResult.begin())); // merge into the output merge (aVec.begin(), aVec.end(), aList.begin(), aList.end(), ostream_iterator (cout, " ")); cout << endl; } The algorithm inplace_merge() (Section 13 Merge Two Adjacent Sequences into One) can be used to merge two sections of a single sequence into one sequence.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Set Operations The operations of set union, set intersection, and set difference were all described in Chapter 7 (Set Operations) when we discussed the set container class. However, the algorithms that implement these operations are generic, and applicable to any ordered data structure. The algorithms assume the input ranges are ordered collections that represent multisets; that is, elements can be repeated.
set_union (listOne.begin(), listOne.end(), listTwo.begin(), listTwo.end(), intOut), cout << endl; // merge - 1 2 3 3 4 4 5 5 6 7 merge (listOne.begin(), listOne.end(), listTwo.begin(), listTwo.end(), intOut), cout << endl; // intersection - 3 4 5 set_intersection (listOne.begin(), listOne.end(), listTwo.begin(), listTwo.end(), intOut), cout << endl; // difference - 1 2 set_difference (listOne.begin(), listOne.end(), listTwo.begin(), listTwo.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Heap Operations A heap is a binary tree in which every node is larger than the values associated with either child. A heap (and, for that matter, a binary tree) can be very efficiently stored in a vector, by placing the children of node i in positions 2 * i + 1 and 2 * i + 2.
performs at most a logarithmic number of operations. void pop_heap (RandomAccessIterator first, RandomAccessIterator last [, Compare ]); Finally, the algorithm sort_heap() converts a heap into a ordered (sorted) collection. Note that a sorted collection is still a heap, although the reverse is not the case. The sort is performed using approximately n log n operations, where n represents the number of elements in the range. The sort_heap() algorithm is not stable.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software An Overview of the Standard Library Allocators The Standard C++ allocator interface encapsulates the types and functions needed to manage the storage of data in a generic way.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Using Allocators with Existing Standard Library Containers Using allocators with existing Standard C++ Library container classes is a simple process.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Building Your Own Allocators Defining your own allocator is a relatively simple process. The Standard C++ Library describes a particular interface, consisting of types and functions. An allocator that conforms to the Standard must match the syntactic requirements for these member functions and types. The Standard C++ Library also specifies a portion of the semantics for the allocator type.
typedef implementation_defined value_type; }; Each of the pointer types in this interface must have a conversion to void*. It must be possible to use the resulting void* as a this value in a constructor or destructor and in conversions to ::types::pointer (for appropriate B) for use by B::deallocate(). Here is a description of the member functions that a Standard C++ Library allocator must provide: my_allocator(); my_allocator(const my_allocator&); ~my_allocator(); Constructors and destructor.
constructor for T. The effect is: new((void*)p) T(u) template void destroy(types::pointer p); Call the destructor on the value pointed to by p. The effect is: ((T*)p)->~T() template my_allocator::types::pointer operator new(my_allocator::types::size_type, my_allocator&); Allocate space for a single object of type T using my_allocator::allocate. The effect is: new((void*)x.
// Alternative allocator uses an interface class // (allocator_interface) // to get type safety. // class my_allocator { public: typedef implementation_defined size_type; typedef implementation_defined difference_type; my_allocator(); ~my_allocator(); void * allocate (size_type n, void * = 0); void deallocate (void* p); size_type max_size (size_type size) const }; We've also included a listing of the full implementation of the allocator_interface class, to show how a standard container will use your class.
size_type max_size () const { return alloc_->max_size(sizeof(T)); } pointer allocate(size_type n, pointer = 0) { return static_cast(alloc_->allocate(n*sizeof(T))); } void deallocate(pointer p) { alloc_->deallocate(p); } void construct(pointer p, const T& val) { new (p) T(val); } void destroy(T* p) { ((T*)p)->~T(); } }; class allocator_interface { public: typedef void* pointer; typedef const void* const_pointer; }; // // allocator globals // void * operator new(size_t N, my_alloca
Standard C++ Library allocators, otherwise you must use the alternative. The first place that you use RWSTD_ALLOCATOR is when determining which typenames the container must use to reflect the interface.
new value on an existing location. The tmp object in this example is a node that contains a data member that is an actual stored value. #ifdef RWSTD_ALLOCATOR the_allocator.construct( the_allocator.address((*tmp).data), x); #else value_allocator.construct( value_allocator.address((*tmp).
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Extending the Library The adoption of the Standard Library for C++ marks a very important development for users of the C++ programming language. Although the library is written in an OOP language and provides plenty of objects, it also employs an entirely different paradigm.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Building on the Standard Containers Let's examine a few of the ways you can use existing Standard C++ Library containers to create your own containers. For example, say you want to implement a set container that enforces unique values that are not inherently sorted. You also want a group of algorithms to operate on that set.
Generic Inheritance A second approach is to create a generic adaptor, rather than specifying vector.
_ }; } // End of my_namespace The advantages of adapting existing containers are numerous. For instance, you get to reuse the implementation and reuse the specifications of the container that you're adapting.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Creating Your Own Containers All of the options that build on existing Standard C++ Library containers incur a certain amount of overhead. When performance demands are critical, or the container requirements very specific, there may be no choice but to implement a container from scratch.
do the actual management of data storage. To use the allocator interface, a container must meet the following three requirements. 1.
typedef Allocator::types::pointer iterator; typedef Allocator::typesconst_pointer iterator; protected: Allocator the_allocator; // copy of the allocator private: size_type buffer_size; iterator buffer_start; iterator current_end; iterator end_of_buffer; public: // A constructor that initializes the set using a range // from some other container or array template set(Iterator start, Iterator finish, Allocator alloc = Allocator()); iterator begin() { return buffer_start; } iterator en
the_allocator.construct(current_end,*start); // 3 // Now lets remove duplicates using a standard algorithm std::unique(begin(),end()); } } // End of my_namespace //1 The allocator parameter is copied into a protected member of the container. This private copy can then be used for all subsequent storage management. //2 An initial buffer is allocated using the allocator's allocate function.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Tips and Techniques for Building Algorithms This sections describes some techniques that use features of iterators to increase the flexibility and efficiency of your algorithms. The iterator_category Primitive Sometimes an algorithm that can be implemented most efficiently with a random access iterator can also work with less powerful iterators.
Iterator union_aux(Iterator first1, Iterator last1, Iterator first2, Iterator last2, Iterator Result, random_access_iterator_tag) { // More efficient implementation } } // End of my_namespace The iterator primitive iterator_category() returns a tag that selects and uses the best available implementation of the algorithm. In order for iterator_category() to work, the iterator provided to the algorithm must be either a simple pointer type, or derived from one of the basic Standard C++ Library iterator types.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Chapter 17: The Traits Parameter ❍ Using the Traits Technique Consider the following problem. You have a matrix that must work for all types of numbers, but the behavior of the matrix depends, in at least some measure, on the type of number. This means your matrix can't handle all numbers in the same way. Except for the behavioral difference, it sounds like the perfect problem for a template.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Using the Traits Technique To implement a traits parameter for a class, you add it as an extra template parameter to your class. You then supply a class for this parameter that encapsulates all the specific operations. Usually that class is itself a template. As an example, let's look at the matrix problem described above.
matrix > long_matrix; Of course you don't even have to specialize on matrix_traits. You just have to make sure you provide the interface that matrix expects from its traits template parameter. Most of the time, the operations contained in a traits class will be static functions so that there's no need to actually instantiate a traits object. The Standard Library uses this technique to give the string class maximum flexibility and efficiency across a wide range of types.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Overview The Standard C++ Library provides a set of classes for reporting errors. These classes use the exception handling facility of the language. The library implements a particular error model, which divides errors in two broad categories: logic errors and runtime errors. Logic errors are errors caused by problems in the internal logic of the program. They are generally preventable.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software The Standard Exception Hierarchy The library implements the two-category error model described above with a set of classes. These classes are defined in the stdexcept header file. They can be used to catch exceptions thrown by the library and to throw exceptions from your own code. The classes are related through inheritance.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Using Exceptions All exceptions thrown explicitly by any element of the library are guaranteed to be part of the standard exception hierarchy. Review the reference for these classes to determine which functions throw which exceptions. You can then choose to catch particular exceptions, or catch any that might be thrown (by specifying the base class exception).
To throw a base exception you would use the following code: throw exception; This is generally not very useful, since whatever catches this exception will have no idea what kind of error has occurred. Instead of a base exception, you will usually throw a derived class such as logic_error or one of its derivations (such as out_of_range as shown in the example above). Better still, you can extend the hierarchy by deriving your own classes.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Example Program Obtaining the Sample Program. This following example program demonstrates the use of exceptions. #include #include static void f() { throw runtime_error("a runtime error"); } int main () { string s; // First we'll try to incite then catch an exception from // the standard library string class. // We'll try to replace at a position that is non-existent.
} catch (const exception& e) { cout << "Got an exception: " << e.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Overview The auto_ptr class wraps any pointer obtained through new and provides automatic deletion of that pointer. The pointer wrapped by an auto_ptr object is deleted when the auto_ptr itself is destroyed. Include File Include the memory header file to access the auto_ptr class.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Declaration and Initialization of Auto Pointers You attach an auto_ptr object to a pointer either by using one of the constructors for auto_ptr, by assigning one auto_ptr object to another, or by using the reset member function. Only one auto_ptr "owns" a particular pointer at any one time, except for the NULL pointer (which all auto_ptrs own by default).
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Example Program This program illustrates the use of auto_ptr to ensure that pointers held in a vector are deleted when they are removed. Often, we might want to hold pointers to strings, since the strings themselves may be quite large and we'll be copying them when we put them into the vector. Particularly in contrast to a string, an auto_ptr is quite small: hardly bigger than a pointer.
v.insert(v.begin(), auto_ptr(new string("Venice"))); // Everything is fine since auto_ptrs transfer ownership of // their pointers when copied // Now remove the first element v.erase(v.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Overview The class complex is a template class, used to create objects for representing and manipulating complex numbers. The operations defined on complex numbers allow them to be freely intermixed with the other numeric types available in the C++ language, thereby permitting numeric software to be easily and naturally expressed.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Creating and Using Complex Numbers In the following sections we will describe the operations used to create and manipulate complex numbers. Declaring Complex Numbers The template argument is used to define the types associated with the real and imaginary fields. This argument must be one of the floating point number data types available in the C++ language, either float, double, or long double.
Accessing Complex Number Values The member functions real() and imag() return the real and imaginary fields of a complex number, respectively. These functions can also be invoked as ordinary functions with complex number arguments. // the following should be the same cout << com_one.real() << "+" << com_one.
cout << com_four << " in polar coordinates is " << arg(com_four) << " and " << norm(com_four) << endl; Trigonometric Functions The trigonometric functions defined for floating point values (namely, sin(), cos(), tan(), asin(), acos(), atan(), sinh(), cosh(), and tanh()), have all been extended to complex number arguments. Each takes a single complex number as argument and returns a complex number as result.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Example Program - Roots of a Polynomial Obtaining the Sample Program The roots of a polynomial a x2 + b x + c = 0 are given by the formula: x = (-b _ sqrt(b2 - 4ac))/2a The following program takes as input three double precision numbers, and returns the complex roots as a pair of values.
Click on the banner to return to the user guide home page.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Overview A new feature of the C++ Standard Library is an organized mechanism for describing the characteristics of the fundamental types provided in the execution environment. In older C and C++ libraries, these characteristics were often described by large collections of symbolic constants.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Fundamental Data Types The standard library describes a specific type by providing a specialized implementation of the numeric_limits class for the type. Static functions and static constant data members then provide information specific to the type. The standard library includes descriptions of the following fundamental data types.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Numeric Limit Members Since a number of the fields in the numeric_limits structure are meaningful only for floating point values, it is useful to separate the description of the members into common fields and floating-point specific fields. Members Common to All Types The following table summarizes the information available through the numeric_limits static member data fields and functions.
representation. All fundamental types are bounded. However, an implementation might choose to include, for example, an infinite precision integer package that would not be bounded. A type is modulo if the value resulting from the addition of two values can wrap around, that is, be smaller than either argument. The fundamental unsigned integer types are all modulo.
round_style rounding style for type For the float data type, the value in field radix, which represents the base of the exponential representation, is equivalent to the symbolic constant FLT_RADIX. For the types float, double and long double the value of epsilon is also available as FLT_EPSILON, DBL_EPSILON, and LDBL_EPSILON. A NaN is a "Not a Number." It is a representable value that nevertheless does not correspond to any numeric quantity. Many numeric algorithms manipulate such values.
Click on the banner to return to the user guide home page. ©Copyright 1996 Rogue Wave Software Chapter 22: Glossary bidirectional iterator An iterator that can be used for reading and writing, and which can move in either a forward or backward direction. binary function A function that requires two arguments. binder A function adaptor that is used to convert a two-argument binary function object into a one-argument unary function object, by binding one of the argument values to a specific constant.
generic algorithm A templated algorithm that is not specialized to any specific container type. Because of this, generic algorithms can be used with a wide variety of different forms of container. heap A way of organizing a collection so as to permit rapid insertion of new values, and rapid access to and removal of the largest value of the collection. heterogeneous collection A collection of values that are not all of the same type.
ordered collection A collection in which all values are ordered according to some binary comparison operator. The set data type automatically maintains an ordered collection. Other collections (vector, deque, list) can be converted into an ordered collection. output iterator An iterator that can be used only to write elements into a container, it cannot be used to read values.
tests for inclusion. stack An adaptor container class, built usually on top of a vector or deque. The stack provides rapid access to the topmost element. Elements are removed from a stack in the reverse of the order they are inserted into the stack. stream iterator An adaptor that converts iterator operations into stream operations. Can be use to either read from or write to an iostream. unary function A function that requires only one argument.
Click on the banner to return to the user guide home page. Licensing Statement The Rogue Wave single-user license for this product allows a single user on a single platform to link against the product library. A site license allows a specified number of users to link against the library. The fact that both the library and this documentation are easy to copy does not make it legal to do so.
