Course week 5

Question 1

The STL can be divided into three parts. What are they?

generic algorithms, containers and interactions

iterators, contaminants and generic algorithms

containers, iterators and generic algorithms

containers, iterators and genetic algebras

Question 2

What information does the STL documentation contain regarding the runtime efficiency of most STL algorithms?

typically an upper bound and sometimes a lower bound

typically a lower bound and sometimes the average efficiency

typically a median value, but always a 95% confidence interval

typically an upper bound and sometimes the average efficiency

Question 3

For a C++ programmer it is important to know how to use the STL because

by using the STL, the programmer can fool other people into believing the programmer is an expert

the programmer can save considerable time by using the STL’s collection of algorithms whose asymptotic performances are known

when using STL containers or algorithms the programmer need not understand what code he/she is using or writing

Question 1

The two main types of STL containers are sequences and associative containers. What are the main features of sequence containers? (There may be more than 1 correct statement.)

the user can place the elements in any order he/she wants

the user must specify the position where an element is added or removed

the size of a sequence data structure is always fixed when it is created

it is impossible for a user to access two consecutive elements of a sequence

the sequence elements can be accessed using an index or using an iterator

Question 2

For an associative container,

the elements in the container are stored in the order of their search keys

the elements in the container are always stored in order

an element in the container can be found by using its search key

the container has a lock that can be opened with a search key after the container performs a ’memory dump’

Question 3

With regard to the appropriate choice of associative container, which of the following statements are correct? (There may be more than 1 correct statement.)

If one only has keys and all the keys are unique and ordering is not important, then one should use an unordered set container.

If one has keys that are associated with elements and each element has its own key and ordering is important, then one should use an ordered multimap container.

If one has keys that are associated with elements and several elements may have the same key and ordering is important, then one should use an ordered multiset container.

If one only has keys and some keys may be repeated and ordering is important, then one should use an ordered multiset container.

If one has keys that are associated with elements and each element has its own key and ordering is not important, then one should use a randomized recycling container.

Question 1

Let \(X\) be an STL container and \(Op1\) be some basic operation (example search for a value). It is possible that STL does not have a function that does \(Op1\) for \(X\). There are two reasons for this. One reason is that doing \(Op1\) for \(X\) is either impossible or it makes no sense. What is the other reason?

The designers of STL were not competent enough to invent working code for \(Op1\).

Peforming \(Op1\) for container \(X\) would always cause the program to terminate due to invalidation.

The only ways to do \(Op1\) for container \(X\) have poor efficiency and many users might assume that \(Op1\) can be done very efficiently.

Some commonly used C++ compilers were not capable of compiling the code for \(Op1\), so the STL designers decided to remove \(Op1\).

Question 2

For which of the following cases does STL provide a function having a constant runtime efficiency? (There may be more than 1 correct case.)

Searching for a key or value from a list container.

Adding an element to an ordered map.

Obtaining the smallest element in an ordered map.

Obtaining the element associated with the smallest key in an ordered map.

Obtaining the element at a certain position in an array.

Question 3

When trying to write code that runs efficiently, a programmer should choose containers so that

operations that are never computed are computed as inefficiently as possible

all operations are computed as efficiently as possible

the amount of data that needs to be stored is as small as possible

operations that are computed frequently are computed as efficiently as possible

Question 1

Regarding iterators in STL, which of the following statements are true? (More than one statement may be true.)

They have no use in STL.

They can be used to indicate a range of elements in a collection.

An iterator is like a bookmark between two consecutive elements.

They are a third kind of container.

Question 2

Suppose \(i1\) and \(i2\) are iterators for some sequence container. If \(i2 < i1\) is true, which of the following is correct?

The element to which \(i1\) points is larger than the element to which \(i2\) points.

Iterator \(i1\) points to a position that is closer to the beginning of the container than the position to which \(i2\) points.

Iterator \(i1\) points to a position that is closer to the end of the container than the position to which \(i2\) points.

The range of positions between \(i2\) and \(i1\) is empty.

Question 1

Suppose \(i1\) and \(i2\) are iterators from two different categories. Which of the following is correct?

For the same operation, \(i1\) and \(i2\) may have different runtime performances.

There exist no common operations that both \(i1\) and \(i2\) can do.

There exists at least one operation that only one of the iterators can do.

For one of the iterators the \(++\) operation will fail.

Question 2

Regarding iterator categories, which of the following statement are true? (More than one may be true.)

Only the forward-list container supports bidirectional iterators.

All categories of iterators allow the \(--\) (minus-minus) operation.

No associative container supports random-access iterators.

All sequence containers support random-access iterators.

A bidirectional iterator does not allow jumping an arbitrary number of elements forward or backward whereas a random-access iterator does.

Course week 5¶

Self-study (english videos and slides)¶

Standard Template Library (STL)¶

Submit weekly exercises¶