1// Protocol Buffers - Google's data interchange format 2// Copyright 2014 Google Inc. All rights reserved. 3// https://developers.google.com/protocol-buffers/ 4// 5// Redistribution and use in source and binary forms, with or without 6// modification, are permitted provided that the following conditions are 7// met: 8// 9// * Redistributions of source code must retain the above copyright 10// notice, this list of conditions and the following disclaimer. 11// * Redistributions in binary form must reproduce the above 12// copyright notice, this list of conditions and the following disclaimer 13// in the documentation and/or other materials provided with the 14// distribution. 15// * Neither the name of Google Inc. nor the names of its 16// contributors may be used to endorse or promote products derived from 17// this software without specific prior written permission. 18// 19// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 31// from google3/util/gtl/map_util.h 32// Author: Anton Carver 33 34#ifndef GOOGLE_PROTOBUF_STUBS_MAP_UTIL_H__ 35#define GOOGLE_PROTOBUF_STUBS_MAP_UTIL_H__ 36 37#include <stddef.h> 38#include <iterator> 39#include <string> 40#include <utility> 41#include <vector> 42 43#include <google/protobuf/stubs/common.h> 44 45namespace google { 46namespace protobuf { 47namespace internal { 48// Local implementation of RemoveConst to avoid including base/type_traits.h. 49template <class T> struct RemoveConst { typedef T type; }; 50template <class T> struct RemoveConst<const T> : RemoveConst<T> {}; 51} // namespace internal 52 53// 54// Find*() 55// 56 57// Returns a const reference to the value associated with the given key if it 58// exists. Crashes otherwise. 59// 60// This is intended as a replacement for operator[] as an rvalue (for reading) 61// when the key is guaranteed to exist. 62// 63// operator[] for lookup is discouraged for several reasons: 64// * It has a side-effect of inserting missing keys 65// * It is not thread-safe (even when it is not inserting, it can still 66// choose to resize the underlying storage) 67// * It invalidates iterators (when it chooses to resize) 68// * It default constructs a value object even if it doesn't need to 69// 70// This version assumes the key is printable, and includes it in the fatal log 71// message. 72template <class Collection> 73const typename Collection::value_type::second_type& 74FindOrDie(const Collection& collection, 75 const typename Collection::value_type::first_type& key) { 76 typename Collection::const_iterator it = collection.find(key); 77 GOOGLE_CHECK(it != collection.end()) << "Map key not found: " << key; 78 return it->second; 79} 80 81// Same as above, but returns a non-const reference. 82template <class Collection> 83typename Collection::value_type::second_type& 84FindOrDie(Collection& collection, // NOLINT 85 const typename Collection::value_type::first_type& key) { 86 typename Collection::iterator it = collection.find(key); 87 GOOGLE_CHECK(it != collection.end()) << "Map key not found: " << key; 88 return it->second; 89} 90 91// Same as FindOrDie above, but doesn't log the key on failure. 92template <class Collection> 93const typename Collection::value_type::second_type& 94FindOrDieNoPrint(const Collection& collection, 95 const typename Collection::value_type::first_type& key) { 96 typename Collection::const_iterator it = collection.find(key); 97 GOOGLE_CHECK(it != collection.end()) << "Map key not found"; 98 return it->second; 99} 100 101// Same as above, but returns a non-const reference. 102template <class Collection> 103typename Collection::value_type::second_type& 104FindOrDieNoPrint(Collection& collection, // NOLINT 105 const typename Collection::value_type::first_type& key) { 106 typename Collection::iterator it = collection.find(key); 107 GOOGLE_CHECK(it != collection.end()) << "Map key not found"; 108 return it->second; 109} 110 111// Returns a const reference to the value associated with the given key if it 112// exists, otherwise returns a const reference to the provided default value. 113// 114// WARNING: If a temporary object is passed as the default "value," 115// this function will return a reference to that temporary object, 116// which will be destroyed at the end of the statement. A common 117// example: if you have a map with string values, and you pass a char* 118// as the default "value," either use the returned value immediately 119// or store it in a string (not string&). 120// Details: http://go/findwithdefault 121template <class Collection> 122const typename Collection::value_type::second_type& 123FindWithDefault(const Collection& collection, 124 const typename Collection::value_type::first_type& key, 125 const typename Collection::value_type::second_type& value) { 126 typename Collection::const_iterator it = collection.find(key); 127 if (it == collection.end()) { 128 return value; 129 } 130 return it->second; 131} 132 133// Returns a pointer to the const value associated with the given key if it 134// exists, or NULL otherwise. 135template <class Collection> 136const typename Collection::value_type::second_type* 137FindOrNull(const Collection& collection, 138 const typename Collection::value_type::first_type& key) { 139 typename Collection::const_iterator it = collection.find(key); 140 if (it == collection.end()) { 141 return 0; 142 } 143 return &it->second; 144} 145 146// Same as above but returns a pointer to the non-const value. 147template <class Collection> 148typename Collection::value_type::second_type* 149FindOrNull(Collection& collection, // NOLINT 150 const typename Collection::value_type::first_type& key) { 151 typename Collection::iterator it = collection.find(key); 152 if (it == collection.end()) { 153 return 0; 154 } 155 return &it->second; 156} 157 158// Returns the pointer value associated with the given key. If none is found, 159// NULL is returned. The function is designed to be used with a map of keys to 160// pointers. 161// 162// This function does not distinguish between a missing key and a key mapped 163// to a NULL value. 164template <class Collection> 165typename Collection::value_type::second_type 166FindPtrOrNull(const Collection& collection, 167 const typename Collection::value_type::first_type& key) { 168 typename Collection::const_iterator it = collection.find(key); 169 if (it == collection.end()) { 170 return typename Collection::value_type::second_type(); 171 } 172 return it->second; 173} 174 175// Same as above, except takes non-const reference to collection. 176// 177// This function is needed for containers that propagate constness to the 178// pointee, such as boost::ptr_map. 179template <class Collection> 180typename Collection::value_type::second_type 181FindPtrOrNull(Collection& collection, // NOLINT 182 const typename Collection::value_type::first_type& key) { 183 typename Collection::iterator it = collection.find(key); 184 if (it == collection.end()) { 185 return typename Collection::value_type::second_type(); 186 } 187 return it->second; 188} 189 190// Finds the pointer value associated with the given key in a map whose values 191// are linked_ptrs. Returns NULL if key is not found. 192template <class Collection> 193typename Collection::value_type::second_type::element_type* 194FindLinkedPtrOrNull(const Collection& collection, 195 const typename Collection::value_type::first_type& key) { 196 typename Collection::const_iterator it = collection.find(key); 197 if (it == collection.end()) { 198 return 0; 199 } 200 // Since linked_ptr::get() is a const member returning a non const, 201 // we do not need a version of this function taking a non const collection. 202 return it->second.get(); 203} 204 205// Same as above, but dies if the key is not found. 206template <class Collection> 207typename Collection::value_type::second_type::element_type& 208FindLinkedPtrOrDie(const Collection& collection, 209 const typename Collection::value_type::first_type& key) { 210 typename Collection::const_iterator it = collection.find(key); 211 GOOGLE_CHECK(it != collection.end()) << "key not found: " << key; 212 // Since linked_ptr::operator*() is a const member returning a non const, 213 // we do not need a version of this function taking a non const collection. 214 return *it->second; 215} 216 217// Finds the value associated with the given key and copies it to *value (if not 218// NULL). Returns false if the key was not found, true otherwise. 219template <class Collection, class Key, class Value> 220bool FindCopy(const Collection& collection, 221 const Key& key, 222 Value* const value) { 223 typename Collection::const_iterator it = collection.find(key); 224 if (it == collection.end()) { 225 return false; 226 } 227 if (value) { 228 *value = it->second; 229 } 230 return true; 231} 232 233// 234// Contains*() 235// 236 237// Returns true if and only if the given collection contains the given key. 238template <class Collection, class Key> 239bool ContainsKey(const Collection& collection, const Key& key) { 240 return collection.find(key) != collection.end(); 241} 242 243// Returns true if and only if the given collection contains the given key-value 244// pair. 245template <class Collection, class Key, class Value> 246bool ContainsKeyValuePair(const Collection& collection, 247 const Key& key, 248 const Value& value) { 249 typedef typename Collection::const_iterator const_iterator; 250 std::pair<const_iterator, const_iterator> range = collection.equal_range(key); 251 for (const_iterator it = range.first; it != range.second; ++it) { 252 if (it->second == value) { 253 return true; 254 } 255 } 256 return false; 257} 258 259// 260// Insert*() 261// 262 263// Inserts the given key-value pair into the collection. Returns true if and 264// only if the key from the given pair didn't previously exist. Otherwise, the 265// value in the map is replaced with the value from the given pair. 266template <class Collection> 267bool InsertOrUpdate(Collection* const collection, 268 const typename Collection::value_type& vt) { 269 std::pair<typename Collection::iterator, bool> ret = collection->insert(vt); 270 if (!ret.second) { 271 // update 272 ret.first->second = vt.second; 273 return false; 274 } 275 return true; 276} 277 278// Same as above, except that the key and value are passed separately. 279template <class Collection> 280bool InsertOrUpdate(Collection* const collection, 281 const typename Collection::value_type::first_type& key, 282 const typename Collection::value_type::second_type& value) { 283 return InsertOrUpdate( 284 collection, typename Collection::value_type(key, value)); 285} 286 287// Inserts/updates all the key-value pairs from the range defined by the 288// iterators "first" and "last" into the given collection. 289template <class Collection, class InputIterator> 290void InsertOrUpdateMany(Collection* const collection, 291 InputIterator first, InputIterator last) { 292 for (; first != last; ++first) { 293 InsertOrUpdate(collection, *first); 294 } 295} 296 297// Change the value associated with a particular key in a map or hash_map 298// of the form map<Key, Value*> which owns the objects pointed to by the 299// value pointers. If there was an existing value for the key, it is deleted. 300// True indicates an insert took place, false indicates an update + delete. 301template <class Collection> 302bool InsertAndDeleteExisting( 303 Collection* const collection, 304 const typename Collection::value_type::first_type& key, 305 const typename Collection::value_type::second_type& value) { 306 std::pair<typename Collection::iterator, bool> ret = 307 collection->insert(typename Collection::value_type(key, value)); 308 if (!ret.second) { 309 delete ret.first->second; 310 ret.first->second = value; 311 return false; 312 } 313 return true; 314} 315 316// Inserts the given key and value into the given collection if and only if the 317// given key did NOT already exist in the collection. If the key previously 318// existed in the collection, the value is not changed. Returns true if the 319// key-value pair was inserted; returns false if the key was already present. 320template <class Collection> 321bool InsertIfNotPresent(Collection* const collection, 322 const typename Collection::value_type& vt) { 323 return collection->insert(vt).second; 324} 325 326// Same as above except the key and value are passed separately. 327template <class Collection> 328bool InsertIfNotPresent( 329 Collection* const collection, 330 const typename Collection::value_type::first_type& key, 331 const typename Collection::value_type::second_type& value) { 332 return InsertIfNotPresent( 333 collection, typename Collection::value_type(key, value)); 334} 335 336// Same as above except dies if the key already exists in the collection. 337template <class Collection> 338void InsertOrDie(Collection* const collection, 339 const typename Collection::value_type& value) { 340 GOOGLE_CHECK(InsertIfNotPresent(collection, value)) << "duplicate value: " << value; 341} 342 343// Same as above except doesn't log the value on error. 344template <class Collection> 345void InsertOrDieNoPrint(Collection* const collection, 346 const typename Collection::value_type& value) { 347 GOOGLE_CHECK(InsertIfNotPresent(collection, value)) << "duplicate value."; 348} 349 350// Inserts the key-value pair into the collection. Dies if key was already 351// present. 352template <class Collection> 353void InsertOrDie(Collection* const collection, 354 const typename Collection::value_type::first_type& key, 355 const typename Collection::value_type::second_type& data) { 356 GOOGLE_CHECK(InsertIfNotPresent(collection, key, data)) 357 << "duplicate key: " << key; 358} 359 360// Same as above except doesn't log the key on error. 361template <class Collection> 362void InsertOrDieNoPrint( 363 Collection* const collection, 364 const typename Collection::value_type::first_type& key, 365 const typename Collection::value_type::second_type& data) { 366 GOOGLE_CHECK(InsertIfNotPresent(collection, key, data)) << "duplicate key."; 367} 368 369// Inserts a new key and default-initialized value. Dies if the key was already 370// present. Returns a reference to the value. Example usage: 371// 372// map<int, SomeProto> m; 373// SomeProto& proto = InsertKeyOrDie(&m, 3); 374// proto.set_field("foo"); 375template <class Collection> 376typename Collection::value_type::second_type& InsertKeyOrDie( 377 Collection* const collection, 378 const typename Collection::value_type::first_type& key) { 379 typedef typename Collection::value_type value_type; 380 std::pair<typename Collection::iterator, bool> res = 381 collection->insert(value_type(key, typename value_type::second_type())); 382 GOOGLE_CHECK(res.second) << "duplicate key: " << key; 383 return res.first->second; 384} 385 386// 387// Lookup*() 388// 389 390// Looks up a given key and value pair in a collection and inserts the key-value 391// pair if it's not already present. Returns a reference to the value associated 392// with the key. 393template <class Collection> 394typename Collection::value_type::second_type& 395LookupOrInsert(Collection* const collection, 396 const typename Collection::value_type& vt) { 397 return collection->insert(vt).first->second; 398} 399 400// Same as above except the key-value are passed separately. 401template <class Collection> 402typename Collection::value_type::second_type& 403LookupOrInsert(Collection* const collection, 404 const typename Collection::value_type::first_type& key, 405 const typename Collection::value_type::second_type& value) { 406 return LookupOrInsert( 407 collection, typename Collection::value_type(key, value)); 408} 409 410// Counts the number of equivalent elements in the given "sequence", and stores 411// the results in "count_map" with element as the key and count as the value. 412// 413// Example: 414// vector<string> v = {"a", "b", "c", "a", "b"}; 415// map<string, int> m; 416// AddTokenCounts(v, 1, &m); 417// assert(m["a"] == 2); 418// assert(m["b"] == 2); 419// assert(m["c"] == 1); 420template <typename Sequence, typename Collection> 421void AddTokenCounts( 422 const Sequence& sequence, 423 const typename Collection::value_type::second_type& increment, 424 Collection* const count_map) { 425 for (typename Sequence::const_iterator it = sequence.begin(); 426 it != sequence.end(); ++it) { 427 typename Collection::value_type::second_type& value = 428 LookupOrInsert(count_map, *it, 429 typename Collection::value_type::second_type()); 430 value += increment; 431 } 432} 433 434// Returns a reference to the value associated with key. If not found, a value 435// is default constructed on the heap and added to the map. 436// 437// This function is useful for containers of the form map<Key, Value*>, where 438// inserting a new key, value pair involves constructing a new heap-allocated 439// Value, and storing a pointer to that in the collection. 440template <class Collection> 441typename Collection::value_type::second_type& 442LookupOrInsertNew(Collection* const collection, 443 const typename Collection::value_type::first_type& key) { 444 typedef typename std::iterator_traits< 445 typename Collection::value_type::second_type>::value_type Element; 446 std::pair<typename Collection::iterator, bool> ret = 447 collection->insert(typename Collection::value_type( 448 key, 449 static_cast<typename Collection::value_type::second_type>(NULL))); 450 if (ret.second) { 451 ret.first->second = new Element(); 452 } 453 return ret.first->second; 454} 455 456// Same as above but constructs the value using the single-argument constructor 457// and the given "arg". 458template <class Collection, class Arg> 459typename Collection::value_type::second_type& 460LookupOrInsertNew(Collection* const collection, 461 const typename Collection::value_type::first_type& key, 462 const Arg& arg) { 463 typedef typename std::iterator_traits< 464 typename Collection::value_type::second_type>::value_type Element; 465 std::pair<typename Collection::iterator, bool> ret = 466 collection->insert(typename Collection::value_type( 467 key, 468 static_cast<typename Collection::value_type::second_type>(NULL))); 469 if (ret.second) { 470 ret.first->second = new Element(arg); 471 } 472 return ret.first->second; 473} 474 475// Lookup of linked/shared pointers is used in two scenarios: 476// 477// Use LookupOrInsertNewLinkedPtr if the container owns the elements. 478// In this case it is fine working with the raw pointer as long as it is 479// guaranteed that no other thread can delete/update an accessed element. 480// A mutex will need to lock the container operation as well as the use 481// of the returned elements. Finding an element may be performed using 482// FindLinkedPtr*(). 483// 484// Use LookupOrInsertNewSharedPtr if the container does not own the elements 485// for their whole lifetime. This is typically the case when a reader allows 486// parallel updates to the container. In this case a Mutex only needs to lock 487// container operations, but all element operations must be performed on the 488// shared pointer. Finding an element must be performed using FindPtr*() and 489// cannot be done with FindLinkedPtr*() even though it compiles. 490 491// Lookup a key in a map or hash_map whose values are linked_ptrs. If it is 492// missing, set collection[key].reset(new Value::element_type) and return that. 493// Value::element_type must be default constructable. 494template <class Collection> 495typename Collection::value_type::second_type::element_type* 496LookupOrInsertNewLinkedPtr( 497 Collection* const collection, 498 const typename Collection::value_type::first_type& key) { 499 typedef typename Collection::value_type::second_type Value; 500 std::pair<typename Collection::iterator, bool> ret = 501 collection->insert(typename Collection::value_type(key, Value())); 502 if (ret.second) { 503 ret.first->second.reset(new typename Value::element_type); 504 } 505 return ret.first->second.get(); 506} 507 508// A variant of LookupOrInsertNewLinkedPtr where the value is constructed using 509// a single-parameter constructor. Note: the constructor argument is computed 510// even if it will not be used, so only values cheap to compute should be passed 511// here. On the other hand it does not matter how expensive the construction of 512// the actual stored value is, as that only occurs if necessary. 513template <class Collection, class Arg> 514typename Collection::value_type::second_type::element_type* 515LookupOrInsertNewLinkedPtr( 516 Collection* const collection, 517 const typename Collection::value_type::first_type& key, 518 const Arg& arg) { 519 typedef typename Collection::value_type::second_type Value; 520 std::pair<typename Collection::iterator, bool> ret = 521 collection->insert(typename Collection::value_type(key, Value())); 522 if (ret.second) { 523 ret.first->second.reset(new typename Value::element_type(arg)); 524 } 525 return ret.first->second.get(); 526} 527 528// Lookup a key in a map or hash_map whose values are shared_ptrs. If it is 529// missing, set collection[key].reset(new Value::element_type). Unlike 530// LookupOrInsertNewLinkedPtr, this function returns the shared_ptr instead of 531// the raw pointer. Value::element_type must be default constructable. 532template <class Collection> 533typename Collection::value_type::second_type& 534LookupOrInsertNewSharedPtr( 535 Collection* const collection, 536 const typename Collection::value_type::first_type& key) { 537 typedef typename Collection::value_type::second_type SharedPtr; 538 typedef typename Collection::value_type::second_type::element_type Element; 539 std::pair<typename Collection::iterator, bool> ret = 540 collection->insert(typename Collection::value_type(key, SharedPtr())); 541 if (ret.second) { 542 ret.first->second.reset(new Element()); 543 } 544 return ret.first->second; 545} 546 547// A variant of LookupOrInsertNewSharedPtr where the value is constructed using 548// a single-parameter constructor. Note: the constructor argument is computed 549// even if it will not be used, so only values cheap to compute should be passed 550// here. On the other hand it does not matter how expensive the construction of 551// the actual stored value is, as that only occurs if necessary. 552template <class Collection, class Arg> 553typename Collection::value_type::second_type& 554LookupOrInsertNewSharedPtr( 555 Collection* const collection, 556 const typename Collection::value_type::first_type& key, 557 const Arg& arg) { 558 typedef typename Collection::value_type::second_type SharedPtr; 559 typedef typename Collection::value_type::second_type::element_type Element; 560 std::pair<typename Collection::iterator, bool> ret = 561 collection->insert(typename Collection::value_type(key, SharedPtr())); 562 if (ret.second) { 563 ret.first->second.reset(new Element(arg)); 564 } 565 return ret.first->second; 566} 567 568// 569// Misc Utility Functions 570// 571 572// Updates the value associated with the given key. If the key was not already 573// present, then the key-value pair are inserted and "previous" is unchanged. If 574// the key was already present, the value is updated and "*previous" will 575// contain a copy of the old value. 576// 577// InsertOrReturnExisting has complementary behavior that returns the 578// address of an already existing value, rather than updating it. 579template <class Collection> 580bool UpdateReturnCopy(Collection* const collection, 581 const typename Collection::value_type::first_type& key, 582 const typename Collection::value_type::second_type& value, 583 typename Collection::value_type::second_type* previous) { 584 std::pair<typename Collection::iterator, bool> ret = 585 collection->insert(typename Collection::value_type(key, value)); 586 if (!ret.second) { 587 // update 588 if (previous) { 589 *previous = ret.first->second; 590 } 591 ret.first->second = value; 592 return true; 593 } 594 return false; 595} 596 597// Same as above except that the key and value are passed as a pair. 598template <class Collection> 599bool UpdateReturnCopy(Collection* const collection, 600 const typename Collection::value_type& vt, 601 typename Collection::value_type::second_type* previous) { 602 std::pair<typename Collection::iterator, bool> ret = collection->insert(vt); 603 if (!ret.second) { 604 // update 605 if (previous) { 606 *previous = ret.first->second; 607 } 608 ret.first->second = vt.second; 609 return true; 610 } 611 return false; 612} 613 614// Tries to insert the given key-value pair into the collection. Returns NULL if 615// the insert succeeds. Otherwise, returns a pointer to the existing value. 616// 617// This complements UpdateReturnCopy in that it allows to update only after 618// verifying the old value and still insert quickly without having to look up 619// twice. Unlike UpdateReturnCopy this also does not come with the issue of an 620// undefined previous* in case new data was inserted. 621template <class Collection> 622typename Collection::value_type::second_type* const 623InsertOrReturnExisting(Collection* const collection, 624 const typename Collection::value_type& vt) { 625 std::pair<typename Collection::iterator, bool> ret = collection->insert(vt); 626 if (ret.second) { 627 return NULL; // Inserted, no existing previous value. 628 } else { 629 return &ret.first->second; // Return address of already existing value. 630 } 631} 632 633// Same as above, except for explicit key and data. 634template <class Collection> 635typename Collection::value_type::second_type* const 636InsertOrReturnExisting( 637 Collection* const collection, 638 const typename Collection::value_type::first_type& key, 639 const typename Collection::value_type::second_type& data) { 640 return InsertOrReturnExisting(collection, 641 typename Collection::value_type(key, data)); 642} 643 644// Erases the collection item identified by the given key, and returns the value 645// associated with that key. It is assumed that the value (i.e., the 646// mapped_type) is a pointer. Returns NULL if the key was not found in the 647// collection. 648// 649// Examples: 650// map<string, MyType*> my_map; 651// 652// One line cleanup: 653// delete EraseKeyReturnValuePtr(&my_map, "abc"); 654// 655// Use returned value: 656// scoped_ptr<MyType> value_ptr(EraseKeyReturnValuePtr(&my_map, "abc")); 657// if (value_ptr.get()) 658// value_ptr->DoSomething(); 659// 660template <class Collection> 661typename Collection::value_type::second_type EraseKeyReturnValuePtr( 662 Collection* const collection, 663 const typename Collection::value_type::first_type& key) { 664 typename Collection::iterator it = collection->find(key); 665 if (it == collection->end()) { 666 return NULL; 667 } 668 typename Collection::value_type::second_type v = it->second; 669 collection->erase(it); 670 return v; 671} 672 673// Inserts all the keys from map_container into key_container, which must 674// support insert(MapContainer::key_type). 675// 676// Note: any initial contents of the key_container are not cleared. 677template <class MapContainer, class KeyContainer> 678void InsertKeysFromMap(const MapContainer& map_container, 679 KeyContainer* key_container) { 680 GOOGLE_CHECK(key_container != NULL); 681 for (typename MapContainer::const_iterator it = map_container.begin(); 682 it != map_container.end(); ++it) { 683 key_container->insert(it->first); 684 } 685} 686 687// Appends all the keys from map_container into key_container, which must 688// support push_back(MapContainer::key_type). 689// 690// Note: any initial contents of the key_container are not cleared. 691template <class MapContainer, class KeyContainer> 692void AppendKeysFromMap(const MapContainer& map_container, 693 KeyContainer* key_container) { 694 GOOGLE_CHECK(key_container != NULL); 695 for (typename MapContainer::const_iterator it = map_container.begin(); 696 it != map_container.end(); ++it) { 697 key_container->push_back(it->first); 698 } 699} 700 701// A more specialized overload of AppendKeysFromMap to optimize reallocations 702// for the common case in which we're appending keys to a vector and hence can 703// (and sometimes should) call reserve() first. 704// 705// (It would be possible to play SFINAE games to call reserve() for any 706// container that supports it, but this seems to get us 99% of what we need 707// without the complexity of a SFINAE-based solution.) 708template <class MapContainer, class KeyType> 709void AppendKeysFromMap(const MapContainer& map_container, 710 vector<KeyType>* key_container) { 711 GOOGLE_CHECK(key_container != NULL); 712 // We now have the opportunity to call reserve(). Calling reserve() every 713 // time is a bad idea for some use cases: libstdc++'s implementation of 714 // vector<>::reserve() resizes the vector's backing store to exactly the 715 // given size (unless it's already at least that big). Because of this, 716 // the use case that involves appending a lot of small maps (total size 717 // N) one by one to a vector would be O(N^2). But never calling reserve() 718 // loses the opportunity to improve the use case of adding from a large 719 // map to an empty vector (this improves performance by up to 33%). A 720 // number of heuristics are possible; see the discussion in 721 // cl/34081696. Here we use the simplest one. 722 if (key_container->empty()) { 723 key_container->reserve(map_container.size()); 724 } 725 for (typename MapContainer::const_iterator it = map_container.begin(); 726 it != map_container.end(); ++it) { 727 key_container->push_back(it->first); 728 } 729} 730 731// Inserts all the values from map_container into value_container, which must 732// support push_back(MapContainer::mapped_type). 733// 734// Note: any initial contents of the value_container are not cleared. 735template <class MapContainer, class ValueContainer> 736void AppendValuesFromMap(const MapContainer& map_container, 737 ValueContainer* value_container) { 738 GOOGLE_CHECK(value_container != NULL); 739 for (typename MapContainer::const_iterator it = map_container.begin(); 740 it != map_container.end(); ++it) { 741 value_container->push_back(it->second); 742 } 743} 744 745// A more specialized overload of AppendValuesFromMap to optimize reallocations 746// for the common case in which we're appending values to a vector and hence 747// can (and sometimes should) call reserve() first. 748// 749// (It would be possible to play SFINAE games to call reserve() for any 750// container that supports it, but this seems to get us 99% of what we need 751// without the complexity of a SFINAE-based solution.) 752template <class MapContainer, class ValueType> 753void AppendValuesFromMap(const MapContainer& map_container, 754 vector<ValueType>* value_container) { 755 GOOGLE_CHECK(value_container != NULL); 756 // See AppendKeysFromMap for why this is done. 757 if (value_container->empty()) { 758 value_container->reserve(map_container.size()); 759 } 760 for (typename MapContainer::const_iterator it = map_container.begin(); 761 it != map_container.end(); ++it) { 762 value_container->push_back(it->second); 763 } 764} 765 766} // namespace protobuf 767} // namespace google 768 769#endif // GOOGLE_PROTOBUF_STUBS_MAP_UTIL_H__ 770