9.01.txt

Exercise 9.1: Which is the most appropriate—a vector, a deque, or a list—for
the following program tasks? Explain the rationale for your choice. If there is
no reason to prefer one or another container, explain why not.

	(a) Read a fixed number of words, inserting them in the container
		alphabetically as they are entered. We’ll see in the next chapter that
		associative containers are better suited to this problem.
	(b) Read an unknown number of words. Always insert new words at the back.
		Remove the next value from the front.
	(c) Read an unknown number of integers from a file. Sort the numbers and
		then print them to standard output.

by Faisal Saadatmand

(a) List or forward list: the scalability is not a concern since we are reading
a fixed number of words. What is important is sorting the words in alphabetic
order at insertion time. For this we could benefit from using the list's
ability to insert data at any point in the container without the need for
reallocation, as in the case with the other containers. A singly or doubly
linked list would work here; though, a singly linked-list would require a
little more work, namely the use of a double pointer. 

(b) deque: since we do not know the number of words we are reading we cannot
use a fixed size array. We can use a list, a forward list, or a vector but they
are not ideal because we are inserting new data at the end or front of the
container only. A deque is better suitable for the task because, unlike the
other containers, it supports fast insert/delete at the front and the end of
the container.

(c) Again, a key factor is the unknown number of elements we are reading into
our container. This, naturally, excludes an array because it has a fixed size.
Since we are just storing, sorting and then printing data we do not have any
reason not to use a vector. We can achieve our task by reading the integers
into a vector object, calling sort() operation on our vector and then printing
the vector with a for range loop.