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().