2. (Efficiency of ADT Implementations)

We have implemented simple and generalised lattices using nested STL vectors and STL maps, respectively. The performance of these data structures may not be good enough for all applications and in some cases it may be necessary to implement them in a different way.

Answer the following questions:

a) Are there advantages in using Boost uBLAS upper- and lower-triangular matrices instead of nested STL vectors?

b) For generalised lattices, consider using C++ (or Boost) unordered maps instead of STL maps because they have constant complexity instead of logarithmic complexity:

// boost or std namespace unordered_map > tree;

c) Create a new generalised lattice class whose implementation is an unordered map (you can copy and modify the code from the original class). Test the performance of the new class by creating a large lattice whose row set is a Boost date.

d) Why would the use of nested STL lists be an inefficient implementation of a lattice?

What is the resulting complexity? For example, how efficient is searching in this new structure?