| OLD | NEW |
| 1 // Copyright (c) 2013 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2013 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 // | 4 // |
| 5 // This is a simplistic insertion-ordered map. It behaves similarly to an STL | 5 // This is a simplistic insertion-ordered map. It behaves similarly to an STL |
| 6 // map, but only implements a small subset of the map's methods. Internally, we | 6 // map, but only implements a small subset of the map's methods. Internally, we |
| 7 // just keep a map and a list going in parallel. | 7 // just keep a map and a list going in parallel. |
| 8 // | 8 // |
| 9 // This class provides no thread safety guarantees, beyond what you would | 9 // This class provides no thread safety guarantees, beyond what you would |
| 10 // normally see with std::list. | 10 // normally see with std::list. |
| 11 // | 11 // |
| 12 // Iterators should be stable in the face of mutations, except for an | 12 // Iterators should be stable in the face of mutations, except for an |
| 13 // iterator pointing to an element that was just deleted. | 13 // iterator pointing to an element that was just deleted. |
| 14 | 14 |
| 15 #ifndef UTIL_GTL_LINKED_HASH_MAP_H_ | 15 #ifndef UTIL_GTL_LINKED_HASH_MAP_H_ |
| 16 #define UTIL_GTL_LINKED_HASH_MAP_H_ | 16 #define UTIL_GTL_LINKED_HASH_MAP_H_ |
| 17 | 17 |
| 18 #include <list> | 18 #include <list> |
| 19 #include <utility> | 19 #include <utility> |
| 20 | 20 |
| 21 #include "base/hash_tables.h" | 21 #include "base/containers/hash_tables.h" |
| 22 #include "base/logging.h" | 22 #include "base/logging.h" |
| 23 | 23 |
| 24 // This holds a list of pair<Key, Value> items. This list is what gets | 24 // This holds a list of pair<Key, Value> items. This list is what gets |
| 25 // traversed, and it's iterators from this list that we return from | 25 // traversed, and it's iterators from this list that we return from |
| 26 // begin/end/find. | 26 // begin/end/find. |
| 27 // | 27 // |
| 28 // We also keep a map<Key, list::iterator> for find. Since std::list is a | 28 // We also keep a map<Key, list::iterator> for find. Since std::list is a |
| 29 // doubly-linked list, the iterators should remain stable. | 29 // doubly-linked list, the iterators should remain stable. |
| 30 template<class Key, class Value> | 30 template<class Key, class Value> |
| 31 class linked_hash_map { | 31 class linked_hash_map { |
| (...skipping 169 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 201 | 201 |
| 202 private: | 202 private: |
| 203 // The map component, used for speedy lookups | 203 // The map component, used for speedy lookups |
| 204 MapType map_; | 204 MapType map_; |
| 205 | 205 |
| 206 // The list component, used for maintaining insertion order | 206 // The list component, used for maintaining insertion order |
| 207 ListType list_; | 207 ListType list_; |
| 208 }; | 208 }; |
| 209 | 209 |
| 210 #endif // UTIL_GTL_LINKED_HASH_MAP_H_ | 210 #endif // UTIL_GTL_LINKED_HASH_MAP_H_ |
| OLD | NEW |