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 2: Implementation of insert().