• Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off
Reading...
Front

Card Range To Study

through

image

Play button

image

Play button

image

Progress

1/140

Click to flip

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.