| 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. |
| (...skipping 106 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 117 size_type erase(const Key& key) { | 117 size_type erase(const Key& key) { |
| 118 typename MapType::iterator found = map_.find(key); | 118 typename MapType::iterator found = map_.find(key); |
| 119 if (found == map_.end()) return 0; | 119 if (found == map_.end()) return 0; |
| 120 | 120 |
| 121 list_.erase(found->second); | 121 list_.erase(found->second); |
| 122 map_.erase(found); | 122 map_.erase(found); |
| 123 | 123 |
| 124 return 1; | 124 return 1; |
| 125 } | 125 } |
| 126 | 126 |
| 127 // Erases values with the provided iterator. If the provided iterator is | 127 // Erases the item that 'position' points to. Returns an iterator that points |
| 128 // invalid or there is inconsistency between the map and list, a CHECK() error | 128 // to the item that comes immediately after the deleted item in the list, or |
| 129 // will occur. | 129 // end(). |
| 130 void erase(iterator position) { | 130 // If the provided iterator is invalid or there is inconsistency between the |
| 131 // map and list, a CHECK() error will occur. |
| 132 iterator erase(iterator position) { |
| 131 typename MapType::iterator found = map_.find(position->first); | 133 typename MapType::iterator found = map_.find(position->first); |
| 132 CHECK(found->second == position) | 134 CHECK(found->second == position) |
| 133 << "Inconsisent iterator for map and list, or the iterator is invalid."; | 135 << "Inconsisent iterator for map and list, or the iterator is invalid."; |
| 134 | 136 |
| 135 list_.erase(position); | |
| 136 map_.erase(found); | 137 map_.erase(found); |
| 138 return list_.erase(position); |
| 137 } | 139 } |
| 138 | 140 |
| 139 // Erases values between first and last, not including last. | 141 // Erases all the items in the range [first, last). Returns an iterator that |
| 140 void erase(iterator first, iterator last) { | 142 // points to the item that comes immediately after the last deleted item in |
| 143 // the list, or end(). |
| 144 iterator erase(iterator first, iterator last) { |
| 141 while (first != last && first != end()) { | 145 while (first != last && first != end()) { |
| 142 erase(first++); | 146 first = erase(first); |
| 143 } | 147 } |
| 148 return first; |
| 144 } | 149 } |
| 145 | 150 |
| 146 // Finds the element with the given key. Returns an iterator to the | 151 // Finds the element with the given key. Returns an iterator to the |
| 147 // value found, or to end() if the value was not found. Like a map, this | 152 // value found, or to end() if the value was not found. Like a map, this |
| 148 // iterator points to a pair<Key, Value>. | 153 // iterator points to a pair<Key, Value>. |
| 149 iterator find(const Key& key) { | 154 iterator find(const Key& key) { |
| 150 typename MapType::iterator found = map_.find(key); | 155 typename MapType::iterator found = map_.find(key); |
| 151 if (found == map_.end()) { | 156 if (found == map_.end()) { |
| 152 return end(); | 157 return end(); |
| 153 } | 158 } |
| (...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 223 | 228 |
| 224 private: | 229 private: |
| 225 // The map component, used for speedy lookups | 230 // The map component, used for speedy lookups |
| 226 MapType map_; | 231 MapType map_; |
| 227 | 232 |
| 228 // The list component, used for maintaining insertion order | 233 // The list component, used for maintaining insertion order |
| 229 ListType list_; | 234 ListType list_; |
| 230 }; | 235 }; |
| 231 | 236 |
| 232 #endif // UTIL_GTL_LINKED_HASH_MAP_H_ | 237 #endif // UTIL_GTL_LINKED_HASH_MAP_H_ |
| OLD | NEW |