The associative container types that we have got to know in this chapter represent easy-to-use interfaces for their underlying implementation. They are abstract data types that abstract from their concrete implementation. Normally, we see nothing of this implementation, and we do not want it anyway. We rely on LEDA using the optimal implementation for every type - optimal with respect to the average case of use, according to the present state of knowledge of algorithmics. But, as we said, only for the average case - there may well be special situations in which it would be of advantage to use a specific implementation of an abstract data type.

For example, the class d_array is implemented by randomized search trees by default. However, there may be situations in which the use of a skiplist would provide faster response times. Therefore some data types, primarily the associative container types and the priority queues, offer several implementations from which the experienced user can choose the one that is most suitable for his situation. But be careful! This possibility should be taken into consideration only by a user who can exhibit solid knowledge about data structures and efficient algorithms - here one should know what one does.

In this spirit, we do not want to explain here how such specialized implementations like randomized search trees or skiplists work. This would go beyond the scope of this tutorial. To understand the internal working of such structures, it is warmly recommended to read a theoretical introduction to data structures and algorithms.

Rather, we want to show by means of the example of the skiplist implementation, which can be specified as an additional implementation parameter of a d_array, how such special implementations of an abstract data type are taken advantage of in LEDA: The name of the implementation can be specified as an additional template parameter.

Here is once again a version of our program for counting strings from standard input. This version now uses a skiplist to manage the key-value pairs:

#include <LEDA/d_array.h>
#include <LEDA/impl/skiplist.h>
#include <LEDA/string.h>
#include <iostream>

using leda::d_array;
using leda::skiplist;
using leda::string;

int main()
{
  d_array<string, int, skiplist>  counter(0);
  string s;

  while (std::cin >> s) counter[s]++;
  
  std::cout << "I have counted the following strings:\n";

  forall_defined(s,counter) 
    std::cout << s << " " << counter[s] << std::endl;
}

The header file of an implementation parameter to be included is always located in the subdirectory impl of the directory in which the header files of LEDA are located. The implementation parameter has to be specified as the last template argument of the type to be parameterized.

Such a specialized type like d_array<string,int,skiplist> is derived (in the sense of the language C++) from the corresponding non-parameterized type; this means here from d_array<string,int>. Therefore, the type with implementation parameter can be used in all places where the type without implementation parameter is also permitted.

A survey of the data structures that LEDA keeps ready as an implementation parameter and of the types that can be parameterized with these parameters can be found on the corresponding manual page.