linked_hash_map.h revision 7d4cd473f85ac64c3747c96c277f9e506a0d2246
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) 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Clears the map of all values. 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void clear() { 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) map_.clear(); 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) list_.clear(); 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns true iff the map is empty. 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool empty() const { 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return list_.empty(); 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Erases values with the provided key. Returns the number of elements 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // erased. In this implementation, this will be 0 or 1. 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_type erase(const Key& key) { 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename MapType::iterator found = map_.find(key); 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (found == map_.end()) return 0; 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) list_.erase(found->second); 1002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) map_.erase(found); 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return 1; 1032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Erases values with the provided iterator. If the provided iterator is 1062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // invalid or there is inconsistency between the map and list, a CHECK() error 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // will occur. 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void erase(iterator position) { 1092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename MapType::iterator found = map_.find(position->first); 1102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) CHECK(found->second == position) 1112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) << "Inconsisent iterator for map and list, or the iterator is invalid."; 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) list_.erase(position); 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) map_.erase(found); 1152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Erases values between first and last, not including last. 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void erase(iterator first, iterator last) { 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (first != last && first != end()) { 1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) erase(first++); 1212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Finds the element with the given key. Returns an iterator to the 1252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // value found, or to end() if the value was not found. Like a map, this 1262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // iterator points to a pair<Key, Value>. 1272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) iterator find(const Key& key) { 1282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename MapType::iterator found = map_.find(key); 1292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (found == map_.end()) { 1302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return end(); 1312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return found->second; 1332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const_iterator find(const Key& key) const { 1362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename MapType::const_iterator found = map_.find(key); 1372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (found == map_.end()) { 1382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return end(); 1392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return found->second; 1412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns the bounds of a range that includes all the elements in the 1442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // container with a key that compares equal to x. 1452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::pair<iterator, iterator> equal_range(const key_type& key) { 1462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::pair<typename MapType::iterator, typename MapType::iterator> eq_range = 1472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) map_.equal_range(key); 1482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return make_pair(eq_range.first->second, eq_range.second->second); 1502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::pair<const_iterator, const_iterator> equal_range( 1532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const key_type& key) const { 1542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::pair<typename MapType::const_iterator, 1552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename MapType::const_iterator> eq_range = 1562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) map_.equal_range(key); 1572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const const_iterator& start_iter = eq_range.first != map_.end() ? 1582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) eq_range.first->second : end(); 1592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const const_iterator& end_iter = eq_range.second != map_.end() ? 1602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) eq_range.second->second : end(); 1612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return make_pair(start_iter, end_iter); 1632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns the value mapped to key, or an inserted iterator to that position 1662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // in the map. 1672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Value& operator[](const key_type& key) { 1682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return (*((this->insert(make_pair(key, Value()))).first)).second; 1692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Inserts an element into the map 1722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::pair<iterator, bool> insert(const std::pair<Key, Value>& pair) { 1732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // First make sure the map doesn't have a key with this value. If it does, 1742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // return a pair with an iterator to it, and false indicating that we 1752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // didn't insert anything. 1762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename MapType::iterator found = map_.find(pair.first); 1772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (found != map_.end()) return make_pair(found->second, false); 1782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Otherwise, insert into the list first. 1802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) list_.push_back(pair); 1812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Obtain an iterator to the newly added element. We do -- instead of - 1832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // since list::iterator doesn't implement operator-(). 1842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename ListType::iterator last = list_.end(); 1852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) --last; 1862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) CHECK(map_.insert(make_pair(pair.first, last)).second) 1882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) << "Map and list are inconsistent"; 1892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return make_pair(last, true); 1912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_type size() const { 1942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return list_.size(); 1952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void swap(linked_hash_map& other) { 1982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) map_.swap(other.map_); 1992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) list_.swap(other.list_); 2002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 2032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // The map component, used for speedy lookups 2042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) MapType map_; 2052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // The list component, used for maintaining insertion order 2072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ListType list_; 2082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 2092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif // UTIL_GTL_LINKED_HASH_MAP_H_ 211