Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
140 Cards in this Set
- Front
- Back
The STL was developed by
|
Alexander Stepanov and Meng Lee at Hewlett-Packard
and was based on research by Stepanov, Lee, and David Musser. It is a collection of libraries written in the C++ language. Although the STL is not part of the core C++ language, it is part of the C++ standard, and so any implementation of C++ that conforms to the standard includes the STL. As a practical matter, you can consider the STL to be part of the C++ language. |
|
a generalization of a pointer, and in fact is typically even implemented
using a pointer, but the abstraction of an iterator is designed to spare you the details of the implementation and give you a uniform interface to iterators that is the same across different container classes. Each container class has its own iterator types, just like each data type has its own pointer type. But just as all pointer types behave essentially the same for dynamic variables of their particular data type, so too does each iterator type behave the same, but each iterator is used only with its own container type. |
iterator
|
|
You manipulate iterators using the following overloaded
operators that apply to iterator objects: |
■
Prefix and postfix increment operators ( ++ ) for advancing the iterator to the next data item. ■ Prefix and postfix decrement operators ( -- ) for moving the iterator to the previous data item. ■ Equal and unequal operators ( == and != ) to test whether two iterators point to the same data location. ■ A dereferencing operator ( * ) so that if p is an iterator variable, then *p gives access to the data located at (pointed to by) p . This access may be read only, write only, or allow both reading and changing of the data, depending on the particular container class. Not all iterators have all of these operators. However, the vector template class is an example of a container whose iterators have all these operators and more. |
|
Many container classes, including the
vector template class, have the following member functions that return iterator objects (iterator values) that point to special data elements in the data structure: |
■
c.begin( ) returns an iterator for the container c that points to the “first” data item in the container c . ■ c.end( ) returns something that can be used to test when an iterator has passed beyond the last data item in a container c . The iterator c.end( ) is completely analogous to NULL when used to test whether a pointer has passed the last node in a linked list of the kind discussed in Chapter 17. The iterator c.end( ) is thus an iterator that is not located at a data item but that is a kind of end marker or sentinel. |
|
for
loop that cycles through all the elements in a container object c , as follows: |
//p is an iterator variable of the type for the container object c.
for (p = c.begin( ); p != c.end( ); p++) process *p //*p is the current data item. |
|
The iterators we want for a vector of
int s are of type |
std::vector<int>::iterator
|
|
Another container class is the
list template class. Iterators for list s of int s are of type |
std::list<int>::iterator
|
|
can be thought of as a linear arrangement of its data elements. There is a
first data element v[0], a second data element v[1], and so forth |
vector
An iterator p is an object that can be located at one of these elements (think “points to” one of these elements). An iterator can move its location from one element to another element. If p is located at, say, v[7], then p++ moves p so it is located at v[8]. This allows an iterator to move through the vector from the first element to the last element, but it needs to find the first element and needs to know when it has seen the last element. |
|
You can tell if an iterator is at the same location as another iterator by using the
operator |
==
|
|
The member function begin( ) is used to position an iterator at the first element in
a container. For vectors, and many other container classes, the member function begin( ) returns an iterator located at the first element. (For a vector v the first element is v[0].) Thus, |
iterator p = v.begin( );
initializes the iterator variable p to an iterator located at the first element. The basic for loop for visiting all elements of the vector v is therefore iterator p; for (p = v.begin( ); Boolean_Expression; p++) Action_At_Location p; The desired stopping condition is p = v.end( ) |
|
returns a sentinel value that can be checked to see if an
iterator has passed the last element. |
The member function end( )
|
|
If p is located at the last element, then after p++,
the test p = v.end( ) changes from |
false to true
|
|
v.end( )
|
Note that p != v.end( ) does not change from true to false until after p’s location
has advanced past the last element. So, v.end( ) is not located at any element. The value v.end( ) is a special value that serves as a sentinel. It is not an iterator, but you can compare v.end( ) to an iterator using == and !=. The value v.end( ) is analogous to the value NULL that is used to mark the end of a linked list of the kind discussed in Chapter 17. |
|
always produces the element located at the iterator p
|
The dereferencing operator *p
In some situations *p produces read-only access, which does not allow you to change the element. In other situations it gives you access to the element and will let you change the element. For vectors, *p will allow you to change the element located at p, as illustrated by the following for loop from Display 19.1: for (p = container.begin( ); p != container.end( ); p++) *p = 0; |
|
The increment and decrement operators can be used in either prefix (++p) or postfix
(p++) notation. In addition to changing p, they also return a value. The details of the value returned are completely analogous to what happens with the increment and decrement operators on int variables. |
In prefix notation, first the variable is changed and
then the changed value is returned. In postfix notation, the value is returned before the variable is changed. |
|
The following lines from Display 19.2 illustrate the fact that with vector iterators
you have random access to the elements of a vector, such as container: |
iterator p = container.begin( );
cout << "The third entry is " << container[2] << endl; cout << "The third entry is " << p[2] << endl; cout << "The third entry is " << *(p + 2) << endl; |
|
means that you can go directly to any particular element in one step
|
Random access
|
|
The expressions p[2] and *(p + 2) are
|
completely equivalent
By analogy to pointer arithmetic (see Chapter 10), (p + 2) names the location two places beyond p. Since p is at the first (index 0) location in the previous code, (p + 2) is at the third (index 2) location. The expression (p + 2) returns an iterator. The expression *(p + 2) dereferences that iterator. Of course, you can replace 2 with a different nonnegative integer to obtain a pointer to a different element. |
|
suppose the previously discussed code from Display 19.2 were
replaced with the following (note the added p++): iterator p = container.begin( ); p++; cout << "The third entry is " << container[2] << endl; cout << "The third entry is " << p[2] << endl; cout << "The third entry is " << *(p + 2) << endl; The output of these three couts would no longer be The third entry is C The third entry is C The third entry is C but would instead be |
The third entry is C
The third entry is D The third entry is D The p++ moves p from location 0 to location 1, and so (p + 2) is now an iterator at location 3, not location 2. So, *(p + 2) and p[2] are equivalent to container[3], not container[2]. |
|
Different containers have different kinds of iterators. The following are the main kinds of iterators.
|
Forward iterators: ++ works on the iterator.
Bidirectional iterators: Both ++ and -- work on the iterator. Random-access iterators: ++, --, and random access all work with the iterator. |
|
The categories of forward iterator, bidirectional iterator, and random-access iterator
each subdivide into two categories |
constant and mutable
|
|
the dereferencing
operator produces a read-only version of the element |
constant iterator
|
|
*p can be assigned a value, and that will change the corresponding
element in the container |
mutable iterator
|
|
if a container has mutable iterators and you want a constant
iterator for the container, you can have it. You might want a constant iterator as a kind of error checking device if you intend that your code should not change the elements in the container. For example, the following will produce a constant iterator for a vector container named container: |
std::vector<char>::const_iterator p = container.begin( );
or equivalently using std::vector<char>::const_iterator; const_iterator p = container.begin( ); |
|
an iterator that does not allow you to change the element at its location
|
Constant Iterator
|
|
For a container with bidirectional
iterators, there is a way to reverse everything using a kind of iterator known as a reverse iterator. The following will work fine: |
reverse_iterator rp;
for (rp = container.rbegin( ); rp != container.rend( ); rp++) cout << *rp << " "; The member function rbegin( ) returns an iterator located at the last element. The member function rend( ) returns a sentinel the marks the “end” of the elements in the reverse order. Note that for an iterator of type reverse_iterator, the increment operator, ++, moves backward through the elements. In other words, the meanings of -- and ++ are interchanged |
|
const_
reverse_iterator |
reverse_iterator type also has a constant version, which is named
|
|
can be used to cycle through all elements of a container with bidirectional iterators.
The elements are visited in reverse order. The general scheme is as follows: reverse_iterator rp; for (rp = c.rbegin( ); rp != c.rend( ); rp++) Process_At_Location p; The object c is a container class with bidirectional iterators. When using reverse_iterator you need to have some sort of using declaration or something equivalent. For example, if c is a vector<int>, the following will suffice: using std::vector<int>::reverse_iterator; reverse iterator rbegin( ) rend( ) |
Reverse Iterator
|
|
essentially a forward iterator that can be used with input streams
|
input iterator
|
|
essentially a forward iterator that can be used with output streams
|
output iterator
|
|
The ___ ___ of the STL are different kinds of structures for holding data,
such as lists, queues, and stacks. Each is a template class with a parameter for the particular type of data to be stored. So, for example, you can specify a list to be a list of ints or doubles or strings, or any class or struct type you wish. Each container template class may have its own specialized accessor and mutator functions for adding data and removing data from the container. Different container classes may have different kinds of iterators. For example, one container class may have bidirectional iterators whereas another container class may have only forward iterators. However, whenever they are defined, the iterator operators and the member functions begin( ) and end( ) have the same meaning for all STL container classes. |
container classes
|
|
arranges its data items into a list such that there is a first element,
a next element, and so forth, up to a last element |
sequential container
The linked lists we discussed in Chapter 17 are examples of a kind of sequential container. |
|
The simplest list that is part of the STL is
the |
doubly linked list
|
|
There are, however, differences between a vector and a list container.
|
One of the
main differences is that a vector container has random-access iterators whereas a list has only bidirectional iterators. |
|
slist<T>::iterator
slist<T>::const_iterator Mutable forward Constant forward <slist> (Depends on implementation and may not be available.) |
slist
(Warning: slist is not part of the STL.) |
|
list<T>::iterator
list<T>::const_iterator list<T>::reverse_iterator list<T>::const_reverse_iterator Mutable bidirectional Constant bidirectional Mutable bidirectional Constant bidirectional <list> |
list
|
|
vector<T>::iterator
vector<T>::const_iterator vector<T>::reverse_iterator vector<T>::const_reverse_iterator Mutable random access Constant random access Mutable random access Constant random access <vector> |
vector
|
|
deque<T>::iterator
deque<T>::const_iterator deque<T>::reverse_iterator deque<T>::const_reverse_iterator Mutable random access Constant random access Mutable random access Constant random access <deque> |
deque
|
|
Returns the number of elements in the container.
|
c.size( )
|
|
Returns an iterator located at the first element in the container.
|
c.begin( )
|
|
Returns an iterator located one beyond the last element in the container.
|
c.end( )
|
|
Returns an iterator located at the last element in the container. Used
with reverse_iterator. Not a member of slist. |
c.rbegin( )
|
|
Returns an iterator located one beyond the first element in the container.
Used with reverse_iterator. Not a member of slist. |
c.rend( )
|
|
Inserts the Element at the end of the sequence. Not a member of
slist. |
c.push_back(Element)
|
|
Inserts the Element at the front of the sequence. Not a member of
vector. |
c.push_front(Element)
|
|
Inserts a copy of Element before the location of Iterator.
|
c.insert(Iterator,Element)
|
|
Removes the element at location Iterator. Returns an iterator at the
location immediately following. Returns c.end( ) if the last element is removed. |
c.erase(Iterator)
|
|
A void function that removes all the elements in the container.
|
c.clear( )
|
|
Returns a reference to the element in the front of the sequence.
Equivalent to *(c.begin( )). |
c.front( )
|
|
True if c1.size( ) == c2.size( ) and each element of c1 is
equal to the corresponding element of c2. |
c1 == c2
|
|
!(c1 == c2)
|
c1 != c2
|
|
pronounced “d-queue” or “deck” and stands for “doubly ended queue.” A
deque is a kind of super queue. With a queue you add data at one end of the data sequence and remove data from the other end. With a deque you can add data at either end and remove data from either end. The template class deque is a template class for a deque with a parameter for the type of data stored. |
Deque
|
|
arranges its data items into a list so that there is a first element, a next
element, and so forth, up to a last element. The sequential container template classes that we have discussed are slist, list, vector, and deque. |
sequential container
|
|
Iterators and Removing Elements
|
Adding or removing an element to or from a container can affect other iterators. In general, there
is no guarantee that the iterators will be located at the same element after an addition or deletion. Some containers do, however, guarantee that the iterators will not be moved by additions or deletions, except of course if the iterator is located at an element that is removed. Of the template classes we have seen so far, list and slist guarantee that their iterators will not be moved by additions or deletions, except of course if the iterator is located at an element that is removed. The template classes vector and deque make no such guarantee. |
|
template classes that are implemented on top of other classes.
|
Container adapters
For example, the stack template class is by default implemented on top of the deque template class, which means that buried in the implementation of the stack is a deque where all the data resides. However, you are shielded from this implementation detail and see a stack as a simple last-in/first-out data structure. |
|
a queue
with the additional property that each entry is given a priority when it is added to the queue. If all entries have the same priority, then entries are removed from a priority queue in the same manner as they are removed from a queue. If items have different priorities, the higher-priority items are removed before lower-priority items. |
priority queue
|
|
the
type name for the stack template class using the default underlying container is stack<int> for a stack of ints. If you wish to specify that the underlying container is instead the vector template class, you would use |
stack<int, vector<int> >
|
|
Returns the number of elements in the stack.
|
s.size( )
|
|
Returns true if the stack is empty; otherwise, returns false.
|
s.empty( )
|
|
Returns a mutable reference to the top member of the stack.
|
s.top( )
|
|
Inserts a copy of Element at the top of the stack.
|
s.push(Element)
|
|
Removes the top element of the stack. Note that pop is a void function.
It does not return the element removed. |
s.pop( )
|
|
True if s1.size( ) == s2.size( ) and each element of s1 is
equal to the corresponding element of s2; otherwise, returns false. |
s1 == s2
|
|
More about stack...
|
The stack template class also has a default constructor, a copy constructor, and a constructor that takes
an object of any sequence class and initializes the stack to the elements in the sequence. It also has a destructor that returns all storage for recycling, and a well-behaved assignment operator. |
|
basically very simple databases. They store data, such as
structs or any other type of data. Each data item has an associated value known as its key. For example, if the data is a struct with an employee’s record, the key might be the employee’s Social Security number. Items are retrieved on the basis of the key. The key type and the type for data to be stored need not have any relationship to one another, although they often are related. A very simple case is when each data item is its own key. For example, in a set every element is its own key. |
Associative containers
|
|
in some sense, the simplest container you can imagine. It
stores elements without repetition. |
set template class
|
|
To work efficiently, a set object stores its values in
sorted order. You can specify the order used for storing elements as follows: |
set<T, Ordering> s;
Ordering should be a well-behaved ordering relation that takes two arguments of type T and returns a bool value.2 T is the type of elements stored. If no ordering is specified, then the ordering is assumed to use the < relational operator. |
|
Returns the number of elements in the queue.
|
q.size( )
|
|
Returns true if the queue is empty; otherwise, returns false.
|
q.empty( )
|
|
Returns a mutable reference to the front member of the queue.
|
q.front( )
|
|
Returns a mutable reference to the last member of the queue.
|
q.back( )
|
|
Adds Element to the back of the queue.
|
q.push(Element)
|
|
Removes the front element of the queue. Note that pop is a void
function. It does not return the element removed. |
q.pop( )
|
|
True if q1.size( ) == q2.size( ) and each element of q1 is
equal to the corresponding element of q2; otherwise, returns false. |
q1 == q2
|
|
More about queues
|
The queue template class also has a default constructor, a copy constructor, and a constructor that takes
an object of any sequence class and initializes the stack to the elements in the sequence. It also has a destructor that returns all storage for recycling, and a well-behaved assignment operator. |
|
essentially a function given as a set of ordered pairs. For each value first that
appears in a pair, there is at most one value second such that the pair (first, second) is in the map. The template class map implements map objects in the STL. |
map
|
|
if you want to assign a unique number to each string name, you could declare a map
object as follows: |
map<string, int> numberMap;
For string values known as keys, the numberMap object can associate a unique int value. Like a set object, a map object stores its elements in sorted order by its key values. You can specify the ordering on keys as a third entry in the angular brackets, < >. If you do not specify an ordering, a default ordering is used. The restrictions on orderings you can use are the same as those on the orderings allowed for the set template class. Note that the ordering is on key values only. The second type can be any type and need not have anything to do with any ordering. As with the set object, the sorting of the stored entries in a map object is done for reasons of efficiency. |
|
Inserts a copy of Element in the set. If Element is already in the set,
this has no effect. |
s.insert(Element)
|
|
Removes Element from the set. If Element is not in the set, this has no
effect. |
s.erase(Element)
|
|
Returns an iterator located at the copy of Element in the set. If Element
is not in the set, s.end( ) is returned. Whether the iterator is mutable or not is implementation dependent. |
s.find(Element)
|
|
Erases the element at the location of the Iterator.
|
s.erase(Iterator)
|
|
Returns the number of elements in the set.
|
s.size( )
|
|
Returns true if the set is empty; otherwise, returns false.
|
s.empty( )
|
|
Returns true if the sets contain the same elements; otherwise,
returns false. |
s1 == s2
|
|
More about sets
|
The set template class also has a default constructor, a copy constructor, and other specialized constructors
not mentioned here. It also has a destructor that returns all storage for recycling, and a well-behaved assignment operator. |
|
pair
|
The STL template class pair<T1, T2> has objects that are pairs of values such that the
first element is of type T1 and the second is of type T2. If aPair is an object of type pair<T1, T2>, then aPair.first is the first element, which is of type T1, and aPair.second is the second element, which is of type T2. The member variables first and second are public member variables, so no accessor or mutator functions are needed. The header file for the pair template is <utility>. So, to use the pair template class, you need the following, or something like it, in your file: #include<utility> using std::pair; |
|
Even more about maps
|
Type name: map<KeyType, T> or map<KeyType, T, Ordering> for a map that associates (“maps”) elements
of type KeyType to elements of type T. The Ordering is used to sort elements by key value for efficient storage. If no Ordering is given, the ordering used is the binary operator, <. Library header: <map>, which places the definition in the std namespace. Defined types include key_type for the type of the key values, mapped_type for the type of the values mapped to, and size_type. (So, the defined type key_type is simply what we called KeyType above.) Iterators: iterator, const_iterator, reverse_iterator, and const_reverse_iterator. All iterators are bidirectional. Those iterators not including const_ are neither constant nor mutable but something in between. For example, if p is of type iterator, then you can change the key value but not the value of type T. Perhaps it is best, at least at first, to treat all iterators as if they were constant. begin( ), end( ), rbegin( ), and rend( ) have the expected behavior. Adding or deleting elements does not affect iterators, except for an iterator located at the element removed. |
|
Inserts Element in the map. Element is of type pair<KeyType, T>.
Returns a value of type pair<iterator, bool>. If the insertion is successful, the second part of the returned pair is true and the iterator is located at the inserted element. |
m.insert(Element)
|
|
Removes the element with the key Target_Key.
|
m.erase(Target_Key)
|
|
Returns an iterator located at the element with key value Target_Key.
Returns m.end( ) if there is no such element. |
m.find(Target_Key)
|
|
Returns the number of pairs in the map.
|
m.size( )
|
|
Returns true if the map is empty; otherwise, returns false.
|
m.empty( )
|
|
Returns true if the maps contain the same pairs; otherwise, returns
false. |
m1 == m2
|
|
More about maps
|
The map template class also has a default constructor, a copy constructor, and other specialized constructors
not mentioned here. It also has a destructor that returns all storage for recycling, and a well-behaved assignment operator. |
|
just a set of instructions for performing
a task often though of by programmers as an abstraction of the code defining a function. |
algorithm
|
|
template functions are sometimes called
|
algorithms
|
|
It is often thought of as an abstraction of the code defining a function. It gives
the important details but not the fine details of the coding. |
algorithm
|
|
In the ___ the interface not only tells a programmer what
the function does and how to use the functions, but also how rapidly the task will be done. In some cases the standard even specifies the particular algorithm that is used, although not the exact details of the coding. Moreover, when it does specify the particular algorithm, it does so because of the known efficiency of the algorithm. |
STL
|
|
For
any positive integer N, T(N) is the amount of time it takes for the program to sort N numbers. The function T is called the ___ ___ of the program. |
running time
|
|
So far we have been assuming that this sorting program will take the same amount
of time on any list of N numbers. That need not be true. Perhaps it takes much less time if the list is already sorted or almost sorted. In that case, T(N) is defined to be the time taken by the “hardest” list, that is, the time taken on that list of N numbers that makes the program run the longest. This is called the |
worst-case running time
|
|
big-O notation
|
Estimates on running time, such as the one we just went through, are normally
expressed in something called big-O notation. (The O is the letter “Oh,” not the digit zero.) Suppose we estimate the running time to be, say, 6N + 5 operations, and suppose we know that no matter what the exact running time of each different operation may turn out to be, there will always be some constant factor c such that the real running time is less than or equal to c(6N + 5) Under these circumstances, we say that the code (or program or algorithm) runs in time O(6N + 5). This is usually read as “big-O of 6N + 5.” We need not know what the constant c will be. In fact, it will undoubtedly be different for different computers, but we must know that there is one such c for any reasonable computer system. If the computer is very fast, the c might be less than 1—say, 0.001. If the computer is very slow, the c might be very large—say, 1,000. Moreover, since changing the units (say from nanosecond to second) only involves a constant multiple, there is no need to give any units of time. Be sure to notice that a big-O estimate is an upper-bound estimate. We always approximate by taking numbers on the high side rather than the low side of the true count. Also notice that when performing a big-O estimate, we need not determine an exact count of the number of operations performed. We only need an estimate that is correct up to a constant multiple. If our estimate is twice as large as the true number, that is good enough. |
|
___ ___ ___ means a running time of T(N) = aN + b. A ___ ___ ___ is always an O(N) running time.
|
Linear running time
|
|
___ ___ ___ means a running time
with a highest term of N^2. A ___ ___ ___ is always an O(N^2) running time. |
Quadratic running time
|
|
logarithms in running-time formulas
|
We will also occasionally have logarithms in running-time formulas. Those normally
are given without any base, since changing the base is just a constant multiple. If you see log N, think log base 2 of N, but it would not be wrong to think log base 10 of N. Logarithms are very slow growing functions. So, an O(log N) running time is very fast. |
|
Insertions
at the back of a vector (push_back), the front or back of a deque (push_back and push_front), and anywhere in a list (insert) are all ___ (that is, a constant upper bound on the running time that is independent of the size of the container). |
O(1)
|
|
Insertion
or deletion of an arbitrary element for a vector or deque is ___ where N is the number of elements in the container. |
O(N)
|
|
For a set or map finding (find) is ___ where N
is the number of elements in the container. |
O(log N)
|
|
find
|
Does
find work with absolutely any container? No, not quite. To start with, it takes iterators as arguments, and some containers, such as stack , do not have iterators. To use the find function, the container must have iterators, the elements must be stored in a linear sequence so that the ++ operator moves iterators through the container, and the elements must be comparable using == . In other words, the container must have forward iterators (or some stronger kind of iterators, such as bidirectional iterators). |
|
An ___ is a generalization of a pointer. Iterators are used to move through the
elements in some range of a container. The operations ++, --, and dereferencing * are usually defined for an iterator. |
iterator
|
|
Container classes with iterators have member functions end( ) and begin( ) that
return iterator values such that you can process all the data in the container as follows: |
for (p = c.begin( ); p != c.end( ); p++)
process *p //*p is the current data item. |
|
The main kinds of iterators are as follows.
|
Forward iterators: ++ works on the iterator.
Bidirectional iterators: Both ++ and -- work on the iterator. Random-access iterators: ++, --, and random access all work with the iterator. |
|
With a constant iterator p, the dereferencing operator *p produces a read-only version
of the element. |
With a mutable iterator p, *p can be assigned a value.
|
|
A ___ ___ has reverse iterators that allow your code to cycle through
the elements in the container in reverse order. |
bidirectional container
|
|
The main container template classes in the STL are
|
list, which has mutable
bidirectional iterators; and the template classes vector and deque, both of which have mutable random-access iterators. |
|
container adapter classes, which means they are built on top of
other container classes. A stack is a last-in/first-out container. A queue is a first-in/ first-out container. |
stack and queue
|
|
store their elements
in sorted order for efficiency of search algorithms. A set is a simple collection of elements. A map allows storing and retrieving by key values. The multiset class allows repetitions of entries. The multimap class allows a single key to be associated with multiple data items. |
The set, map, multiset, and multimap container template classes
|
|
The ___ includes template functions to implement generic algorithms with guarantees
on their maximum running time. |
STL
|
|
1. If v is a vector, what does v.begin( ) return? What does v.end( ) return?
|
1. v.begin( ) returns an iterator located at the first element of v. v.end( ) returns a value
that serves as a sentinel value at the end of all the elements of v. |
|
2. If p is an iterator for a vector object v, what is *p?
|
2. *p is the dereferencing operator applied to p. *p is a reference to the element at location
p. |
|
3. Suppose v is a vector of ints. Write a for loop that will output all the elements of p
except for the first element. |
3. using std::vector<int>::iterator;
. . . iterator p; for (p = v.begin( ), p++; p != v.end( ); p++) cout << *p << " "; |
|
4. Suppose the vector v contains the letters ’A’, ’B’, ’C’, and ’D’ in that order. What
is the output of the following code? using std::vector<char>::iterator; . . . iterator i = v.begin( ); i++; cout << *(i + 2) << " "; i--; cout << i[2] << " "; cout << *(i + 2) << " "; |
4. D C C
|
|
5. Suppose the vector v contains the letters ’A’, ’B’, ’C’, and ’D’ in that order. What
is the output of the following code? using std::vector<char>::reverse_iterator; . . . reverse_iterator i = v.rbegin( ); i++; i++; cout << *i << " "; i--; cout << *i << " "; input iterator output iterator |
5. B C
|
|
6. Suppose you want to run the following code, where v is a vector of ints:
for (p = v.begin( ); p != v.end( ); p++) cout << *p << " "; Which of the following are possible ways to declare p? std::vector<int>::iterator p; std::vector<int>::const_iterator p; |
6. Either would work.
|
|
7. What is a major difference between vector and list?
|
7. A major difference is that a vector container has random-access iterators, whereas list
has only bidirectional iterators. |
|
8. Which of the template classes slist, list, vector, and deque have the member
function push_back? |
8. All except slist.
|
|
9. Which of the template classes slist, list, vector, and deque have random-access
iterators? |
9. vector and deque.
|
|
10. Which of the template classes slist, list, vector, and deque can have mutable
iterators? |
10. They all can have mutable iterators.
|
|
11. What kind of iterators (forward, bidirectional, or random-access) does the stack
template adapter class have? |
11. The stack template adapter class has no iterators.
|
|
12. What kind of iterators (forward, bidirectional, or random-access) does the queue
template adapter class have? |
12. The queue template adapter class has no iterators.
|
|
13. If s is a stack<char>, what is the type of the returned value of s.pop( )?
|
13. No value is returned; pop is a void function.
|
|
14. Why are the elements in the set template class stored in sorted order?
|
14. To facilitate an efficient search for elements.
|
|
15. Can a set have elements of a class type?
|
15. Yes, they can be of any type, although there is only one type for each object. The type
parameter in the template class is the type of element stored. |
|
16. Suppose s is of the type set<char>. What value is returned by s.find(’A’) if ’A’
is in s? What value is returned if ’A’ is not in s? |
16. If ’A’ is in s, then s.find(’A’) returns an iterator located at the element ’A’. If ’A’ is
not in s, then s.find(’A’) returns s.end( ). |
|
17. Show that a running time
T(N) = aN + b is an O ( N) running time. ( Hint: The only issue is the plus b . Assume N is always at least 1.) |
17. Just note that aN + b £ (a + b)N, as long as 1 £ N.
|
|
18. Show that for any two bases
a and b for logarithms, if a and b are both greater than 1, then there is a constant c such that log a N ≤ c (log b N) . Thus, there is no need to specify a base in O (log N) . That is, O (log a N) and O (log b N) mean the same thing. |
18. This is mathematics, not C++. So, = will mean equals, not assignment.
First note that loga N = (loga b)(logb N). To see this first identity just note that if you raise a to the power loga N you get N and if you raise a to the power (loga b)(logb N) you also get N. If you set c = (loga b) you get loga N = c(logb N). |
|
19. Replace all occurrences of the identifier vector with the identifier list in Display
19.16. Compile and run the program. |
19. The programs should run exactly the same.
|
|
20. Suppose v is an object of the class vector<int>. Use the search generic function
(Display 19.17) to write some code to determine whether or not v contains the number 42 immediately followed by 43. You need not give a complete program, but do give all necessary include and using directives. (Hint: It may help to use a second vector.) |
20. #include <iostream>
#include <vector> #include <algorithm> using std::cout; using std::vector; using std::vector<int>::const_iterator; using std::search; ... vector<int> target; target.push_back(42); target.push_back(43); const_iterator result = search(v.begin( ), v.end( ), target.begin( ), target.end( )); if (result != v.end( )) cout << "Found 42, 43.\n"; else cout << "42, 43 not there.\n"; |
|
21. Can you use the random_shuffle template function with a list container?
|
21. No, you must have random-access iterators, and the list template class only has
bidirectional iterators. |
|
22. Can you use the copy template function with vector containers, even though copy
requires forward iterators and vector has random-access iterators? |
22. Yes, a random-access iterator is also a forward iterator.
|
|
23. The mathematics course version of a set does not keep its elements in sorted order,
and it has a union operator. Why does the set_union template function require that the containers keep their elements in sorted order? |
23. The set_union template function requires that the containers keep their elements in
sorted order to allow the function template to be implemented in a more efficient way. |