| 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 128 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 139 } | 139 } |
| 140 return found->second; | 140 return found->second; |
| 141 } | 141 } |
| 142 | 142 |
| 143 // Returns the bounds of a range that includes all the elements in the | 143 // Returns the bounds of a range that includes all the elements in the |
| 144 // container with a key that compares equal to x. | 144 // container with a key that compares equal to x. |
| 145 std::pair<iterator, iterator> equal_range(const key_type& key) { | 145 std::pair<iterator, iterator> equal_range(const key_type& key) { |
| 146 std::pair<typename MapType::iterator, typename MapType::iterator> eq_range = | 146 std::pair<typename MapType::iterator, typename MapType::iterator> eq_range = |
| 147 map_.equal_range(key); | 147 map_.equal_range(key); |
| 148 | 148 |
| 149 return make_pair(eq_range.first->second, eq_range.second->second); | 149 return std::make_pair(eq_range.first->second, eq_range.second->second); |
| 150 } | 150 } |
| 151 | 151 |
| 152 std::pair<const_iterator, const_iterator> equal_range( | 152 std::pair<const_iterator, const_iterator> equal_range( |
| 153 const key_type& key) const { | 153 const key_type& key) const { |
| 154 std::pair<typename MapType::const_iterator, | 154 std::pair<typename MapType::const_iterator, |
| 155 typename MapType::const_iterator> eq_range = | 155 typename MapType::const_iterator> eq_range = |
| 156 map_.equal_range(key); | 156 map_.equal_range(key); |
| 157 const const_iterator& start_iter = eq_range.first != map_.end() ? | 157 const const_iterator& start_iter = eq_range.first != map_.end() ? |
| 158 eq_range.first->second : end(); | 158 eq_range.first->second : end(); |
| 159 const const_iterator& end_iter = eq_range.second != map_.end() ? | 159 const const_iterator& end_iter = eq_range.second != map_.end() ? |
| 160 eq_range.second->second : end(); | 160 eq_range.second->second : end(); |
| 161 | 161 |
| 162 return make_pair(start_iter, end_iter); | 162 return std::make_pair(start_iter, end_iter); |
| 163 } | 163 } |
| 164 | 164 |
| 165 // Returns the value mapped to key, or an inserted iterator to that position | 165 // Returns the value mapped to key, or an inserted iterator to that position |
| 166 // in the map. | 166 // in the map. |
| 167 Value& operator[](const key_type& key) { | 167 Value& operator[](const key_type& key) { |
| 168 return (*((this->insert(make_pair(key, Value()))).first)).second; | 168 return (*((this->insert(std::make_pair(key, Value()))).first)).second; |
| 169 } | 169 } |
| 170 | 170 |
| 171 // Inserts an element into the map | 171 // Inserts an element into the map |
| 172 std::pair<iterator, bool> insert(const std::pair<Key, Value>& pair) { | 172 std::pair<iterator, bool> insert(const std::pair<Key, Value>& pair) { |
| 173 // First make sure the map doesn't have a key with this value. If it does, | 173 // First make sure the map doesn't have a key with this value. If it does, |
| 174 // return a pair with an iterator to it, and false indicating that we | 174 // return a pair with an iterator to it, and false indicating that we |
| 175 // didn't insert anything. | 175 // didn't insert anything. |
| 176 typename MapType::iterator found = map_.find(pair.first); | 176 typename MapType::iterator found = map_.find(pair.first); |
| 177 if (found != map_.end()) return make_pair(found->second, false); | 177 if (found != map_.end()) return std::make_pair(found->second, false); |
| 178 | 178 |
| 179 // Otherwise, insert into the list first. | 179 // Otherwise, insert into the list first. |
| 180 list_.push_back(pair); | 180 list_.push_back(pair); |
| 181 | 181 |
| 182 // Obtain an iterator to the newly added element. We do -- instead of - | 182 // Obtain an iterator to the newly added element. We do -- instead of - |
| 183 // since list::iterator doesn't implement operator-(). | 183 // since list::iterator doesn't implement operator-(). |
| 184 typename ListType::iterator last = list_.end(); | 184 typename ListType::iterator last = list_.end(); |
| 185 --last; | 185 --last; |
| 186 | 186 |
| 187 CHECK(map_.insert(make_pair(pair.first, last)).second) | 187 CHECK(map_.insert(std::make_pair(pair.first, last)).second) |
| 188 << "Map and list are inconsistent"; | 188 << "Map and list are inconsistent"; |
| 189 | 189 |
| 190 return make_pair(last, true); | 190 return std::make_pair(last, true); |
| 191 } | 191 } |
| 192 | 192 |
| 193 size_type size() const { | 193 size_type size() const { |
| 194 return list_.size(); | 194 return list_.size(); |
| 195 } | 195 } |
| 196 | 196 |
| 197 void swap(linked_hash_map& other) { | 197 void swap(linked_hash_map& other) { |
| 198 map_.swap(other.map_); | 198 map_.swap(other.map_); |
| 199 list_.swap(other.list_); | 199 list_.swap(other.list_); |
| 200 } | 200 } |
| 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 |