Associative map

Using the cached-measurement feature of our chunked sequence structure, we have implemented asymptotically efficient associative maps in the style of STL map. Our implementation is, however, not designed to compete with highly optimized implementations, such as that of STL. Rather, the main purpose of our implementation is to provide an example of advanced use of cached measurement so that others can apply similar techniques to build their own custom data structures.

namespace pasl {
namespace data {
namespace map {

template <class Key,
          class Item,
          class Compare = std::less<Key>,
          class Key_swap = std_swap<Key>,
          class Alloc = std::allocator<std::pair<const Key, Item> >,
          int chunk_capacity = 8
>
class map;

}}}

Our map interface implements only a subset of the STL interface. The operations that we do implement have the same time and space complexity as do the operations implemented by the STL container. However, the constant factors imposed by our container may be significantly larger than those of the STL container because our structure is not specifically optimized for this use case.

Example: insert

// accessing mapped values
#include <iostream>
#include <string>

#include "map.hpp"

int main () {
  pasl::data::map::map<char,std::string> mymap;
  
  mymap['a']="an element";
  mymap['b']="another element";
  mymap['c']=mymap['b'];
  
  std::cout << "mymap['a'] is " << mymap['a'] << '\n';
  std::cout << "mymap['b'] is " << mymap['b'] << '\n';
  std::cout << "mymap['c'] is " << mymap['c'] << '\n';
  std::cout << "mymap['d'] is " << mymap['d'] << '\n';
  
  std::cout << "mymap now contains " << mymap.size() << " elements.\n";
  
  return 0;
}

Output

mymap['a'] is an element
mymap['b'] is another element
mymap['c'] is another element
mymap['d'] is 
mymap now contains 4 elements.

Example: erase

// accessing mapped values
#include <iostream>
#include <string>

#include "map.hpp"

int main ()
{
  pasl::data::map::map<char,int> mymap;
  pasl::data::map::map<char,int>::iterator it;
  
  // insert some values:
  mymap['a']=10;
  mymap['b']=20;
  mymap['c']=30;
  mymap['d']=40;
  mymap['e']=50;
  mymap['f']=60;
  
  it=mymap.find('b');
  mymap.erase (it);                   // erasing by iterator
  
  mymap.erase ('c');                  // erasing by key
  
  // show content:
  for (it=mymap.begin(); it!=mymap.end(); ++it)
    std::cout << (*it).first << " => " << (*it).second << '\n';
  
  return 0;
}

Output

f => 60
e => 50
d => 40
a => 10