Answer the following statements true (T) or false (F)

1. Insertion into a vector runtime is O(1) at any position in the vector. Explain what ‘runtime is O(1)’ means.
2. Insertion into an STL list takes O(1) time at any position in the list. What does ‘ takes O(1) time’ mean?
3. STL ranges [first, last) are always ‘half-open’ – from the first element to a designation for one past the last element.
4. Given a map m, the expression m["value"] will return NULL if there is no string named "value" stored in the map.
5. Elements of a set and map are stored in sorted order.


1. False
Runtime is O(1) means there is an upper bound for the runtime that is independent of the size of the problem, which is the size of the vector in this case. Vector insertion is O(n) at any position in the vector except the back. Insertion is O(1) only for insertion at the back of the vector. For example, use of the push_back() member is O(1). There are other ways to insert most of which we do have not treated in the text, all of which are O(1) at the back.
2. True
An STL list is a linked structure. Insertion at any position involves only a half-dozen or so assignments and a free store allocation. This is O(1), which means there is a fixed upper bound for the insertion time that is independent of the size of the list.
3. True.
Note the begin() and end(),and the rbegin()and rend() member functions that all the sequence containers have. They provide a ‘half open’ range from the first element in the container to one past the last. The rbegin() and rend() members provide a range from the last to past the front, as a reverse_iterator would traverse.
4. False.
This will actually add a new entry to the map associated with the key "value" that has the default entry for the map container type.
5. True

Computer Science & Information Technology

You might also like to view...

A(n) _____ is a public member function that provides read-only access to a private data member.

a. accessor function b. reader function c. protector function d. constructor function

Computer Science & Information Technology

The hasNext() method of the Iterator interface has a return value of:

(a) byte (b) int (c) boolean (d) none of the above

Computer Science & Information Technology

The term associated with sending a packet to all devices on a single network is a(n) _______

Fill in the blank(s) with correct word

Computer Science & Information Technology

Which command will open the Vim editor from the terminal window in CentOS 7?

Vedit Vterm Vi Vim

Computer Science & Information Technology