Basic Data Structure

Implement the deque. It should allow the typical operations and an iterator to traverse all items (the same bidirectional iterator, i.e. allowing ++/-- operations as the one used in a list). Use the STL for reference on the deque interface, at minimum you need to have the [] (index) operator and be able to add/remove items from the front/back of the queue, all in O(1) time. 2. Implement a data structure for the sparse matrix. The idea is to allow the usual access as if the matrix is a 2-d array, but only the non-zero elements are physically saved in the underlying structure. 3. Do an evaluation of the performances of STL sequence containers (vector, list, deque) in a simulated real world testing condition (relatively large data set), in typical operations, such as insertion/deletion/retrieval of items of different sizes (e.g. T being an int vs. T being a structure taking up 1KB for space). What you'll be measuring is the time as a function of the number of data elements. Obviously it's dependent on the speed of the computer one uses, so what matters is the relative speed.