Deck 19: Standard Template Library

Question 1

You can assign stacks of the same base type

Answer 1

True

Question 2

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

Answer 2

True

Question 3

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

Answer 3

True

Question 4

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

Question 5

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

Question 6

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

Question 7

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

Question 8

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

Question 9

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

Question 10

The set container implements only iterator.

Question 11

Elements of a set and map are stored in sorted order.

Question 12

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

Question 13

Insertion into a vector runtime is O(1)at any position in the vector.Explain what 'runtime is O(1)' means.

Question 14

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 15

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

Question 16

You cannot copy stacks.

Question 17

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

Question 18

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

Question 19

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

Question 20

Given a map m,the expression m["value"] will return NULL if there is no string named "value" stored in the map.

Question 21

What kind of iterators does the queue template container have?

Question 22

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 23

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

Question 24

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

Question 25

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 26

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

Question 27

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 28

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 29

What is a generic algorithm?

Question 30

What kind of iterators does the stack template container have?

Question 31

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 32

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

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

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 35

I have an algorithm that runs in O(N1/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)About 30 minutes
e)You haven't given enough information.I can't tell.

Question 36

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 37

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 38

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 39

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

Question 40

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 41

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 42

Rewrite the code below using the ranged for loop and the auto keyword.
map personIDs = {
{1,"Walt"},
{2,"Kenrick"}
};
map::const_iterator iter;
for (iter = personIDs.begin();iter != personIDs.end();
iter++)
{
cout << iter->first << " " << iter->second << endl;
}

Question 43

The following code snippet is supposed to output "true" if the string "c++" is in the map and false otherwise.However,it has an error.Describe the error and give a fix.
if (mymap["c++"]==0)
{
cout << "false" << endl;
}
else
{
cout << "true" << endl;
}

Question 44

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

Question 45

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

Question 46

What is different about mathematical sets and STL sets?