Deck 18: Standard Template Library

Question 1

The model for the iterator in the STL was the pointer.

Answer 1

True

Question 2

The STL containers each define iterators appropriate to the internal structure of the container.

Answer 2

True

Question 3

A failing find)operation on an STL set returns a null pointer value.

Answer 3

False

Question 4

The runtime for insertion at any position into a vector is O1).Explain what 'runtime is O1)' means.

Question 5

You can assign stacks of the same base type

Question 6

The set container implements only iterator.

Question 7

Nonmodifying sequence algorithms do not change the elements in the containers they work on.

Question 8

Insertion into an STL list takes O1)time at any position in the list.What does ' takes O1)time' mean?

Question 9

The operator * is prefixed to an iterator to insert an element in the container.

Question 10

STL ranges [first,last)are always 'half-open' - from the first element to a designation for one past the last element.

Question 11

STL set operations are essentially insert,delete,and the query,"Is it there?".

Question 12

A Map is a function given as a set of ordered pairs.The first is the key that has to have ordering and the second is any type.The position of a pair in the set is determined by the ordering on the keys.

Question 13

The template stack and queue adapters have a copy constructor,an overloaded operator assignment,and a destructor.

Question 14

Order of magnitude estimates don't work well if we are interested in behavior for small data sets.

Question 15

The associative containers store their data in an order different from the insertion order.

Question 16

The Standard Template Library consists of the containers of various kinds.

Question 17

To declare an iterator,one must #include the proper header file,then specify the container type and use that with the scope resolution operator,::,to qualify the inner type iterator,to declare the iterator variable,as in
#include
std::vector::iterator myIterator;.

Question 18

You cannot copy stacks.

Question 19

The set container keeps track of how many copies of a data item you insert in the set object.

Question 20

The notation m["stringval"] = 100 is valid if m is a map that takes a pair of type string,int).

Question 21

Which of the following does not have STL containers types?

A)Associative containers
B)Generic Functions
C)Sequence containers
D)Container adapters

Question 22

Suppose we have the following definition:
Vector vec;
// use push_back to put 10 values into vec here.
Vector::iterator itr1,itr2,itr3;
Itr1 = vec.begin);
Itr2 = vec.begin)+ 5;
Itr3 = vec.end);
For this iterator which of the following is incorrect?

A)*iter1
B)itr2[3]
C)itr3 + 3
D)itr2 - 5

Question 23

Which of the following is not,strictly speaking,a component of the Standard Template Library?

A)Templates
B)Generic Algorithms
C)Containers
D)Iterators

Question 24

Which of the following operations do forward iterators have?

A)Overloaded operator+ to add an int value to the iterator to move the place the iterator points forward by the argument number of elements.
B)Overloaded operator* to multiply the iterator by an int value to move the place the iterator points by a number of elements equal to the argument.
C)Overloaded operator++ to move the place the iterator points forward by one element.
D)Overloaded operator-- to move the place the iterator points backward by one element.

Question 25

I have an algorithm that runs in On²)time,where n is the size of the problem.What does "the size of the problem" mean?

A)The size of the problem is the number of bytes the data occupies
B)The size of the problem is the number of lines in the source code of the program.
C)The size of a problem is the number of data items that the algorithm operates upon
D)The size of the problem is the depth of nesting of loops in the program.

Question 26

The time to find an element is the same for a set or a map.It is

A)O1)
B)ON^1/2)
C)Olog N)
D)ON)
E)ON²)

Question 27

Which of the following is not a member function of the stack adapter template? For members of stack,specify any needed arguments.

A)size)
B)empty)
C)front)
D)push)
E)top)

Question 28

Which of the following operations do random access iterators have?

A)Prefix operator* to make available the container element for use as l-value or r-value.
B)Overloaded binary operator+ to move the place the iterator points forward by the amount added.
C)Overloaded binary operator* to multiply the iterator by a double value to move the place the iterator points by a fractional number of elements equal to the double argument.
D)Overloaded unary operator++ to move the place the iterator points forward by as many elements as the argument.

Question 29

I have an algorithm that runs in ON^1/2),where n is the size of the problem.For N = 100,the time the algorithm runs is 1 minute.How long does the algorithm take for N=1000?

A)Same time
B)About 3 minutes
C)About 10 minutes
D)You haven't given enough information.I can't tell.

Question 30

Which of the following is not a member function of the queue adapter template? For members of queue,specify any needed arguments.

A)size)
B)empty)
C)front)
D)push)
E)top)

Question 31

I have an algorithm that runs in ON²),where Nis the size of the problem.For N = 100,the time for the algorithm to run is 1 minute.How long does the algorithm take for N=1000?

A)Same time
B)10 minutes
C)100 minutes
D)1000 minutes

Question 32

Assume proper includes have been executed,but no using directive or declaration.Write a definition of an iterator for a vector of ints that is initialized to point to the first member of the vector vec.

Question 33

Declare a stack template container to hold values of type double using the list container.Write the necessary include and using statements.Mention any appropriate cautions about syntax.

Question 34

Which of the following member functions is NOT common to the sequential containers vector,list,deque)?

A)begin)
B)rbegin)
C)rend)
D)push_front)
E)front)

Question 35

Suppose we have the following definition:
Vector vec,vec1;
//use push_back to put 10 values into vec
Vector::iterator p = vec.begin);
Vector::const_iterator q = vec.begin);
Which of the following expressions is not legal? Treat the effect of these as non-cumulative.

A)*p = 1; B)*q = 1;
C)p = vec.end ); D)q = vec1.end);

Question 36

Assume proper includes have been executed,but not using directive or declaration.Write a definition of an iterator for a vector named vec of int values.Write a for loop that will display the contents vec on the screen,separated by spaces.Use iterators for the loop control.

Question 37

In which container does the position of an inserted element depend on the data,not the order of insertion?

A)Associative containers
B)Fraternal container
C)Sequence containers
D)Container adapters

Question 38

Given the following definition for a map,which code fragment is valid?
map mymap;

A)mymap[3,"hello"] = 10;
B)mymap.push_backPair3,"hello"));
C)mymap[10] = "hello";
D)mymap["hello"] = 3;

Question 39

Which of the following operations do bidirectional iterators have?

A)Prefix operator* to make available the container element for use as l-value or r-value.
B)Overloaded operator+ to add an int value to the iterator to move the place the iterator points forward by the argument number of elements.
C)Overloaded operator* to multiply the iterator by an int value to move the place the iterator points by a number of elements equal to the argument.
D)Overloaded operator- to move the place the iterator points backware by a number of elements equal to the argument.

Question 40

The operator * is prefixed to an iterator to

A)Multiply the element in the container
B)Extract the element in the container to assign to it only
C)Extract the element in the container to fetch its value only
D)Extract the element in the container as either an l-value or an r-value

Question 41

Suppose you want to run code that involves the loop
//Assume vector v and iterator p has been defined and
//given appropriate values
for p = v.begin); p != v.end); p++)
cout << *p << " ";
Which of the following could you use to declare the iterator p? Why?
std::vector::iterator p;
std::vector::const_iterator p;

Question 42

Suppose you have a generic algorithm that requires forward iterators.Can I use it with a vector or a list even though these iterators are random access and bidirectional iterators respectively? Explain.

Question 43

What is the difference between the iterators defined here.
vector vec;
//put 10 values into vec
const vector::iterator p = vec.begin);
vector::const_iterator q = vec.begin);

Question 44

What is different about mathematical sets and STL sets?

Question 45

I have an algorithm that runs in On²),where n is the size of the problem.What does "the size of the problem" mean?

Question 46

Define an iterator into a list of char of initial that allows traversal of the list for fetching from the list,but does not allow the list to be change through the iterator.Assume all includes and using directive/declarations have been executed.Assume further that the list has had sufficient elements inserted to support any actions needed.

Question 47

Assume proper includes have been executed,but not using directive or declaration.Write a definition of an iterator for a vector named vec of int values.Write a for loop that will display the contents vec on the screen,separated by spaces starting at the last element in the vector and proceeding to the first.Use iterators for the loop control.

Question 48

Why are the elements in the STL set and map)kept sorted?

Question 49

Can you use the random_shuffle generic algorithm with a list container? What about a vector container? Why or why not?

Question 50

Suppose we are given an STL vector container named vec that holds values of type double.What do each of vec[0],vec.front),*vec.begin)),*vec.end)- vec.size))and *vec.rend)-1)mean?

Question 51

What is a generic algorithm?

Question 52

Suppose we are given an STL vector container named vec that holds values of type double.What do each of vec[vec.size)-1],vec.back),*vec.end)-1),*vec.begin)+vec.size)-1)and *vec.rbegin)mean?

Question 53

What kind of iterators does the queue template container have?

Question 54

If myVec has type vector what type does myVec.front)return?

Question 55

For a vector,inserting or deleting invalidates iterators in positions after the insertion or deletion.What happens to the set container if we delete in the middle?

Question 56

Why does the compiler complain if I attempt to use a vector as a base container for a stack of double values? The declaration is:
stack> myStack;

Question 57

What kind of iterators does the stack template container have?