Listing 3: The Main Body Implementation of linked_hash

/**
 * The main linked_hash class.
 */
template <class Key, class Data, class HashFcn, class EqualKey, class Alloc>
class linked_hash
{   
private:
   // 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;

   // The internal hash_map and list, which will store pointers to 
   // the linked hash nodes.
   _Hash_Map	_hash_map;
   _List	_list;

   // The allocator used for creating new nodes.
   _Node_Alloc	_node_allocator;

public:
   // Typedefs for the standard STL data types.
   typedef typename _Hash_Map::key_type key_type;
   typedef Data data_type;
   typedef pair<Key, Data> value_type;
   typedef typename _Hash_Map::hasher hasher;
   typedef typename _Hash_Map::key_equal key_equal;

   typedef Alloc allocator_type;
   typedef typename Alloc::size_type size_type;
   typedef typename Alloc::difference_type difference_type;
   typedef _linked_hash_iterator<Key, Data, HashFcn, EqualKey, Alloc> iterator;
   typedef _linked_hash_const_iterator<Key, Data, HashFcn, EqualKey, Alloc>
      const_iterator;
   typedef reverse_iterator<iterator> reverse_iterator;
   typedef reverse_iterator<const_iterator> const_reverse_iterator;

   typedef typename Alloc::pointer pointer;
   typedef typename Alloc::const_pointer const_pointer;
   typedef typename Alloc::reference reference;
   typedef typename Alloc::const_reference const_reference;

   // Returns a new allocator
   allocator_type get_allocator() const { return allocator_type(); }

public:
   // Default constructor
   linked_hash() {}

   // Constructor with a bucket count.
   // Uses 'explicit' to keep the compiler from allowing an implicit cast 
   // from a size_type to a linked_hash.
   explicit linked_hash(size_type __n) : _hash_map(__n) {}

   // Constructor with a bucket count and a hash function instance
   linked_hash(size_type __n, const hasher& __hf)
      : _hash_map(__n, __hf) {}

   // Constructor with a bucket count, hash function instance, 
   // and a key comparitor instance
   linked_hash(size_type __n, const hasher& __hf, const key_equal& __eql,
               const allocator_type& __a = allocator_type())
      : _hash_map(__n, __hf, __eql, __a) {}

   // Constructor with a range of data to insert during construction.
   template <class InputIterator>
   linked_hash(InputIterator f, InputIterator l) { insert(f, l); }

   // Constructor with a data range, and a bucket count.
   template <class InputIterator>
   linked_hash(InputIterator f, InputIterator l, size_type n) : _hash_map(n) {
      insert(f, l);
   }

   // Constructor with a data range, a bucket count, and a hash function instance
   template <class InputIterator>
   linked_hash(InputIterator f, InputIterator l, size_type n, const hasher& h)
      : _hash_map(n, h) { insert(f, l); }

   // Constructor with a data range, a bucket count, a hash function instance, 
   // and a key comparitor instance
   template <class InputIterator>
   linked_hash(InputIterator f, InputIterator l, size_type n,
               const hasher& h, const key_equal& k)
      : _hash_map(n, h, k) { insert(f, l); }

   // Copy constructor.  Performs a deep copy of the linked hash.
   linked_hash(const linked_hash& lh) {
      insert(lh.begin(), lh.end());
   }

   // Assignment operator.  Performs a deep copy of the linked hash.
   linked_hash& operator=(const linked_hash& lh) {
      insert(lh.begin(), lh.end());
   }

public:
   // Beginning and ending iterator accessors.
   iterator begin() { return iterator(*(_list.begin())); }
   iterator end() { return iterator(NULL); }
   const_iterator begin() const { return const_iterator(*(_list.begin())); }
   const_iterator end() const { return const_iterator(NULL); }

   // Linked hash size accessors.
   // Since the internal hash map will always have exactly one
   // copy of each item in the linked_hash, I just pass through
   // the functionality for these methods to the hash_map.
   size_type size() const { return _hash_map.size(); }
   size_type max_size() const { return _hash_map.max_size(); }
   bool empty() const { return _hash_map.empty(); }

   // Capacity accessor/modifier methods.
   size_type bucket_count() const { return _hash_map.bucket_count(); }
   void resize(size_type n) { _hash_map.resize(n); }

   // Hash function and key comparitor accessors.
   hasher hash_funct() const { return _hash_map.hash_funct(); }
   key_equal key_eq() const { return _hash_map.key_eq(); }

   // Swaps the contents of two linked hashes, by swapping their 
   // internal hash_map and list.
   void swap(linked_hash& __lh) { 
      _hash_map.swap(__lh._hash_map); 
      _list.swap(__lh._list);
   }

   // Comparison operator.
   template <class _K1, class _T1, class _HF, class _EqK, class _Al>
   friend bool operator== (const linked_hash<_K1, _T1, _HF, _EqK, _Al>&,
  	  		   const linked_hash<_K1, _T1, _HF, _EqK, _Al>&);

public:
   // Inserts a new data item into the linked_hash
   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 the node that was inserted (or the already inserted previous node)
      _Node* __rn = (*(__ip.first)).second;
      return pair<iterator, bool>(iterator(__rn), __ip.second);
   }

   // Inserts a range of data items, by calling insert for each item
   template <class InputIterator>
   void insert(InputIterator f, InputIterator l) {
      for( ; f != l; ++f)
         insert(*f);
   }

   // Erase an iterator from the data structure.
   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);
   }

   // Erase the data associated with a key
   size_type erase(const key_type& k) {
      // Find the data item associated with this key
      typename _Hash_Map::iterator __i = _hash_map.find(k);
      if(__i == _hash_map.end()) {
         // If there is no such data item, return zero
         return 0;
      }

      // Save a pointer to the node
      _Node* __n = (*__i).second;

      // 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);

      // If the item exists, there will always be exactly one,
      // so I can always return a one.
      return 1;
   }

   // Erase a range of data items.
   void erase(iterator first, iterator last) {
      for( ; first != last; ++first)
         erase(first);
   }

   // Clear the whole data structure
   void clear() {
      // Clear out the hash_map
      _hash_map.clear();

      // Clear out the linked list and destroy all of the nodes
      typename _List::iterator __i = _list.begin();
      for( ; __i != _list.end(); ) {
         _Node* __n = *__i;
         typename _List::iterator __tmp = __i++;
         _list.erase(__tmp);
         _node_allocator.destroy(__n);
         _node_allocator.deallocate(__n, 1);
      }
   }

   // Find an item by its key.  Return a const iterator.
   const_iterator find(const key_type& k) const {
      // Find the item in the internal hash_map
      const typename _Hash_Map::const_iterator __i = _hash_map.find(k);

      // If the item wasn't found, return the end iterator.
      if(__i == _hash_map.end()) return end();

      // If the item was found, create a new const iterator from the node.
      return const_iterator((*__i).second);
   }

   // Find an item by its key.  Return a non-const iterator.
   iterator find(const key_type& k) {
      // Find the item in the internal hash_map
      typename _Hash_Map::iterator __i = _hash_map.find(k);

      // If the item wasn't found, return the end iterator.
      if(__i == _hash_map.end()) return end();

      // If the item was found, create a new non-const iterator from the node.
      return iterator((*__i).second);
   }

   // Subscript operator.
   // A wrapper around a call to insert() to either access the current data
   // or insert a new default data item.
   Data& operator[](const key_type& k) {
      return (*((insert(value_type(k, data_type()))).first)).second;
   }

   // Wraps the hash_map count() method, to return the number of items of
   // the given key contained in the structure (always either 1 or 0).
   size_type count(const key_type& k) const {
      return _hash_map.count(k);
   }

   // Returns a range of const iterators containing the given key.
   // This will always be a range of length one or length zero.
   pair<const_iterator, const_iterator>
   equal_range(const key_type& k) const {
      const_iterator __i = find(k);
      return pair<const_iterator, const_iterator>(__i, __i);
   }

   // Returns a range of non-const iterators containing the given key.
   // This will always be a range of length one or length zero.
   pair<iterator, iterator> equal_range(const key_type& k) {
      iterator __i = find(k);
      return pair<iterator, iterator>(__i, __i);
   }
};
