An STL-Compatible Hybrid of Linked List & Hash Map

by William Nagel



Example 1: 



// Typedef the node that linked_hash will be using internally.

typedef _linked_hash_node<Key, Data, HashFcn, EqualKey, Alloc> _Node;



// Typedef an allocator for allocating new nodes.

typedef typename Alloc::rebind<_Node>::other _Node_Alloc;



// Typedef an allocator for allocating node pointers.  This will be used in 

// the internal hash_map and list.

typedef typename Alloc::rebind<typename 

                                _Node_Alloc::pointer>::other _NodeP_Alloc;

// Typedefs for the internal hash_map and list	 

typedef hash_map<Key, typename _Node_Alloc::pointer, HashFcn, 

	 	               EqualKey, _NodeP_Alloc> _Hash_Map;

typedef list<_Node*, _NodeP_Alloc> _List;





Example 2: 



pair<iterator,bool> insert(const value_type& __obj) { 

   // First, allocate an empty node for insertion

   typename _Node_Alloc::pointer __np = _node_allocator.allocate(1);



   // Try to insert the new node into the hash_map

   pair<typename _Hash_Map::iterator, bool> __ip =  

      _hash_map.insert(typename _Hash_Map::value_type(__obj.first, __np)); 



   // If the insertion succeeds, insert the rest of the data

   if(__ip.second) {

      // Add the node to the list

      _list.push_front(__np);



      // Construct the node, from the iterators and the data

      _node_allocator.construct(__np, _Node(__obj.first, __obj.second, 

					    __ip.first, _list.begin()));

   }

   else {

      // If the insertion doesn't succeed, get rid of the allocated node

      _node_allocator.deallocate(__np, 1);

   }

   // Return node that was inserted (or the already inserted previous node)

   _Node* __rn = (*(__ip.first)).second;

   return pair<iterator, bool>(iterator(__rn), __ip.second);

}





Example 3: 



void erase(iterator pos) {

   // Save a pointer to the node

   _Node* __n = pos._current;

   // Remove the node from both the hash_map and the list

   _hash_map.erase(__n->_hmi);

   _list.erase(__n->_li);

   // Get rid of the node

   _node_allocator.destroy(__n);

   _node_allocator.deallocate(__n, 1);

}





Example 4: 



Data& operator[](const key_type& k) {

   return (*((insert(value_type(k, data_type()))).first)).second;

}





Example 5: 



linked_hash<string, MyDevice>	devices;

void insert_event(const string& name, MyEvent& evt)

{

    devices[name].queue(evt);

}

void process()

{

    for_each(devices.begin(), devices.end(), DevProcessor());

}





Listing One



/** The linked hash node holds the stored data, along with iterators into the 

 * internal hash map and list.  */

template <class Key, class Data, class HashFcn, class EqualKey, class Alloc>

struct _linked_hash_node

{

   typedef _linked_hash_node<Key, Data, HashFcn, EqualKey, Alloc> _Node;

   typedef hash_map<Key, _Node*, HashFcn, EqualKey, 

	      	    typename Alloc::rebind<_Node*>::other> _Hash_Map;

   typedef typename _Hash_Map::iterator _Hash_Map_iterator;

   typedef list<_Node*, typename Alloc::rebind<_Node*>::other> _List;

   typedef typename _List::iterator _List_iterator;

   typedef pair<Key, Data> value_type;



   // The actual stored data

   value_type		_val;



   // An iterator into the hash map

   _Hash_Map_iterator	_hmi;



   // An iterator into the linked list

   _List_iterator	_li;

      // Constructor

   _linked_hash_node(const Key& __k, const Data& __d, 

                    _Hash_Map_iterator __hmi, _List_iterator __li)

      : _val(__k, __d), _hmi(__hmi), _li(__li) {}

   // Destructor

   ~_linked_hash_node(void) {}

};





Listing One



/** The linked hash node holds the stored data, along with iterators into the 

 * internal hash map and list. */

template <class Key, class Data, class HashFcn, class EqualKey, class Alloc>

struct _linked_hash_node

{

   typedef _linked_hash_node<Key, Data, HashFcn, EqualKey, Alloc> _Node;

   typedef hash_map<Key, _Node*, HashFcn, EqualKey, 

                typename Alloc::rebind<_Node*>::other> _Hash_Map;

   typedef typename _Hash_Map::iterator _Hash_Map_iterator;

   typedef list<_Node*, typename Alloc::rebind<_Node*>::other> _List;

   typedef typename _List::iterator _List_iterator;

   typedef pair<Key, Data> value_type;



   // The actual stored data

   value_type       _val;

   // An iterator into the hash map

   _Hash_Map_iterator   _hmi;

   // An iterator into the linked list

   _List_iterator   _li;

      // Constructor

   _linked_hash_node(const Key& __k, const Data& __d, 

                 _Hash_Map_iterator __hmi, _List_iterator __li)

      : _val(__k, __d), _hmi(__hmi), _li(__li) {}

   // Destructor

   ~_linked_hash_node(void) {}

};





Listing Two



/** The non-const linked hash iterator. */

template <class Key, class Data, class HashFcn, class EqualKey, class Alloc>

struct _linked_hash_iterator {

   typedef linked_hash<Key,Data,HashFcn,EqualKey,Alloc> _Hash_Map;

   typedef _linked_hash_iterator<Key,Data,HashFcn,EqualKey,Alloc> iterator;

   typedef _linked_hash_const_iterator<Key, Data, HashFcn, EqualKey, Alloc>

         const_iterator;

   typedef _linked_hash_node<Key, Data, HashFcn, EqualKey, Alloc> _Node;

   typedef forward_iterator_tag iterator_category;

   typedef pair<Key, Data> value_type;

   typedef ptrdiff_t difference_type;

   typedef size_t size_type;

   typedef value_type& reference;

   typedef value_type* pointer;



   // A pointer to the node referenced by this iterator

   _Node* _current;

   // Constructor

   _linked_hash_iterator(_Node* __n) 

      : _current(__n) {}

   // Default constructor, creates an iterator with a NULL node.

   // Equivalent to calling linked_hash::end()

   _linked_hash_iterator() : _current(NULL) {}

   // Returns a reference to the underlying data value from the node.

   reference operator*() const { return _current->_val; }

   // Returns a pointer to the underlying data value from the node.

   pointer operator->() const { return &(operator*()); }

   // Increment operators.  Implemented separately below.

   iterator& operator++();

   iterator operator++(int);

   // Comparison operators.

   bool operator==(const iterator& __it) const

   { return _current == __it._current; }

   bool operator!=(const iterator& __it) const

   { return _current != __it._current; }

};

// Post-increment operator for non-const iterators

template <class Key, class Data, class HashFcn, class EqualKey, class Alloc>



inline _linked_hash_iterator<Key, Data, HashFcn, EqualKey, Alloc>&

_linked_hash_iterator<Key, Data, HashFcn, EqualKey, Alloc>::operator++() {

   typename _Node::_List::iterator __i = _current->_li;

   _current = *(++__i);

   return *this;

}

// Pre-increment operator for non-const iterators

template <class Key, class Data, class HashFcn, class EqualKey, class Alloc>

inline _linked_hash_iterator<Key, Data, HashFcn, EqualKey, Alloc>

_linked_hash_iterator<Key, Data, HashFcn, EqualKey, Alloc>::operator++(int) {

   iterator __tmp = *this;

   ++*this;

   return __tmp;

}

// Post-increment operator for const iterators

template <class Key, class Data, class HashFcn, class EqualKey, class Alloc>

inline _linked_hash_const_iterator<Key, Data, HashFcn, EqualKey, Alloc>&

_linked_hash_const_iterator<Key,Data,HashFcn,EqualKey,Alloc>::operator++() {

   typename _Node::_List::iterator __i = _current->_li;

   _current = *(++__i);

   return *this;

}

// Pre-increment operator for const iterators

template <class Key, class Data, class HashFcn, class EqualKey, class Alloc>

inline _linked_hash_const_iterator<Key, Data, HashFcn, EqualKey, Alloc>

_linked_hash_const_iterator<Key,Data,HashFcn,EqualKey,Alloc>::operator++(int) {

   iterator __tmp = *this;

   ++*this;

   return __tmp;

}











1



