12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Copyright (c) 2013 The Chromium Authors. All rights reserved. 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// found in the LICENSE file. 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This is a simplistic insertion-ordered map. It behaves similarly to an STL 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// map, but only implements a small subset of the map's methods. Internally, we 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// just keep a map and a list going in parallel. 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This class provides no thread safety guarantees, beyond what you would 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// normally see with std::list. 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Iterators should be stable in the face of mutations, except for an 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// iterator pointing to an element that was just deleted. 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef UTIL_GTL_LINKED_HASH_MAP_H_ 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define UTIL_GTL_LINKED_HASH_MAP_H_ 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <list> 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <utility> 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 217d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)#include "base/containers/hash_tables.h" 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/logging.h" 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This holds a list of pair<Key, Value> items. This list is what gets 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// traversed, and it's iterators from this list that we return from 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// begin/end/find. 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// We also keep a map<Key, list::iterator> for find. Since std::list is a 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// doubly-linked list, the iterators should remain stable. 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template<class Key, class Value> 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class linked_hash_map { 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef std::list<std::pair<Key, Value> > ListType; 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef base::hash_map<Key, typename ListType::iterator> MapType; 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public: 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef typename ListType::iterator iterator; 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef typename ListType::reverse_iterator reverse_iterator; 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef typename ListType::const_iterator const_iterator; 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef typename ListType::const_reverse_iterator const_reverse_iterator; 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef typename MapType::key_type key_type; 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef typename ListType::value_type value_type; 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef typename ListType::size_type size_type; 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) linked_hash_map() : map_(), list_() { 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns an iterator to the first (insertion-ordered) element. Like a map, 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // this can be dereferenced to a pair<Key, Value>. 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) iterator begin() { 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return list_.begin(); 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const_iterator begin() const { 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return list_.begin(); 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns an iterator beyond the last element. 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) iterator end() { 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return list_.end(); 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const_iterator end() const { 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return list_.end(); 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns an iterator to the last (insertion-ordered) element. Like a map, 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // this can be dereferenced to a pair<Key, Value>. 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) reverse_iterator rbegin() { 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return list_.rbegin(); 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const_reverse_iterator rbegin() const { 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return list_.rbegin(); 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns an iterator beyond the first element. 752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) reverse_iterator rend() { 762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return list_.rend(); 772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const_reverse_iterator rend() const { 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return list_.rend(); 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 8203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // Front and back accessors common to many stl containers. 8303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 8403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // Returns the earliest-inserted element 8503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) const value_type& front() const { 8603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) return list_.front(); 8703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) } 8803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 8903b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // Returns the earliest-inserted element. 9003b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) value_type& front() { 9103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) return list_.front(); 9203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) } 9303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 9403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // Returns the most-recently-inserted element. 9503b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) const value_type& back() const { 9603b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) return list_.back(); 9703b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) } 9803b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 9903b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) // Returns the most-recently-inserted element. 10003b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) value_type& back() { 10103b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) return list_.back(); 10203b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) } 10303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Clears the map of all values. 1052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void clear() { 1062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) map_.clear(); 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) list_.clear(); 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns true iff the map is empty. 1112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool empty() const { 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return list_.empty(); 1132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Erases values with the provided key. Returns the number of elements 1162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // erased. In this implementation, this will be 0 or 1. 1172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_type erase(const Key& key) { 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename MapType::iterator found = map_.find(key); 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (found == map_.end()) return 0; 1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) list_.erase(found->second); 1222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) map_.erase(found); 1232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 1; 1252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Erases values with the provided iterator. If the provided iterator is 1282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // invalid or there is inconsistency between the map and list, a CHECK() error 1292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // will occur. 1302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void erase(iterator position) { 1312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename MapType::iterator found = map_.find(position->first); 1322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) CHECK(found->second == position) 1332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) << "Inconsisent iterator for map and list, or the iterator is invalid."; 1342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) list_.erase(position); 1362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) map_.erase(found); 1372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Erases values between first and last, not including last. 1402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void erase(iterator first, iterator last) { 1412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (first != last && first != end()) { 1422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) erase(first++); 1432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Finds the element with the given key. Returns an iterator to the 1472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // value found, or to end() if the value was not found. Like a map, this 1482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // iterator points to a pair<Key, Value>. 1492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) iterator find(const Key& key) { 1502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename MapType::iterator found = map_.find(key); 1512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (found == map_.end()) { 1522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return end(); 1532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return found->second; 1552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const_iterator find(const Key& key) const { 1582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename MapType::const_iterator found = map_.find(key); 1592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (found == map_.end()) { 1602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return end(); 1612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return found->second; 1632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns the bounds of a range that includes all the elements in the 1662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // container with a key that compares equal to x. 1672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::pair<iterator, iterator> equal_range(const key_type& key) { 1682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::pair<typename MapType::iterator, typename MapType::iterator> eq_range = 1692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) map_.equal_range(key); 1702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 171d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) return std::make_pair(eq_range.first->second, eq_range.second->second); 1722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::pair<const_iterator, const_iterator> equal_range( 1752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const key_type& key) const { 1762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::pair<typename MapType::const_iterator, 1772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename MapType::const_iterator> eq_range = 1782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) map_.equal_range(key); 1792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const const_iterator& start_iter = eq_range.first != map_.end() ? 1802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) eq_range.first->second : end(); 1812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const const_iterator& end_iter = eq_range.second != map_.end() ? 1822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) eq_range.second->second : end(); 1832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 184d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) return std::make_pair(start_iter, end_iter); 1852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns the value mapped to key, or an inserted iterator to that position 1882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // in the map. 1892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Value& operator[](const key_type& key) { 190d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) return (*((this->insert(std::make_pair(key, Value()))).first)).second; 1912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Inserts an element into the map 1942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::pair<iterator, bool> insert(const std::pair<Key, Value>& pair) { 1952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // First make sure the map doesn't have a key with this value. If it does, 1962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // return a pair with an iterator to it, and false indicating that we 1972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // didn't insert anything. 1982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename MapType::iterator found = map_.find(pair.first); 199d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) if (found != map_.end()) return std::make_pair(found->second, false); 2002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Otherwise, insert into the list first. 2022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) list_.push_back(pair); 2032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Obtain an iterator to the newly added element. We do -- instead of - 2052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // since list::iterator doesn't implement operator-(). 2062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename ListType::iterator last = list_.end(); 2072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) --last; 2082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 209d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) CHECK(map_.insert(std::make_pair(pair.first, last)).second) 2102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) << "Map and list are inconsistent"; 2112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 212d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) return std::make_pair(last, true); 2132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_type size() const { 2162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return list_.size(); 2172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void swap(linked_hash_map& other) { 2202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) map_.swap(other.map_); 2212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) list_.swap(other.list_); 2222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 2252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // The map component, used for speedy lookups 2262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) MapType map_; 2272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // The list component, used for maintaining insertion order 2292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ListType list_; 2302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 2312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif // UTIL_GTL_LINKED_HASH_MAP_H_ 233