Deck 18: Standard Template Library

Question 1

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

Answer 1

True

Question 2

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

Answer 2

False

Question 3

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

Answer 3

True.

Question 4

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

Question 5

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

Question 6

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

Question 7

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

Question 8

You can assign stacks of the same base type

Question 9

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

Question 10

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

Question 11

The set container implements only iterator.

Question 12

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

Question 13

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

Question 14

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

Question 15

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

Question 16

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 17

You cannot copy stacks.

Question 18

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 19

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

Question 20

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

Question 21

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 22

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 23

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 24

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 25

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 26

Which of the following does not have STL containers types?

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

Question 27

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 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

Which of the following is an incorrect declarations of iterators for STL containers? You may assume that the proper header has been included and that a using directive makes the names from namespace std available.

A) vector::iterator vecIterator;
B) list::iterator listIterator;
C) deque::iterator dequeIterator;
D) list::iterator listIterator;

Question 30

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 31

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 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

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 35

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 36

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 37

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 38

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 39

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 40

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 41

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 42

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 43

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 44

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 45

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 46

What is a generic algorithm?

Question 47

What kind of iterators does the stack template container have?

Question 48

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

Question 49

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 50

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

Question 51

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 52

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

Question 53

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 54

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 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

What is different about mathematical sets and STL sets?

Question 57

What kind of iterators does the queue template container have?

Question 58

Declare a stack template container to hold values of type double using the default container.

Question 59

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?