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 |