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 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 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 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 typedef typename Collection::value_type value_type; 357 GOOGLE_CHECK(InsertIfNotPresent(collection, key, data)) 358 << "duplicate key: " << key; 359} 360 361// Same as above except doesn't log the key on error. 362template <class Collection> 363void InsertOrDieNoPrint( 364 Collection* const collection, 365 const typename Collection::value_type::first_type& key, 366 const typename Collection::value_type::second_type& data) { 367 typedef typename Collection::value_type value_type; 368 GOOGLE_CHECK(InsertIfNotPresent(collection, key, data)) << "duplicate key."; 369} 370 371// Inserts a new key and default-initialized value. Dies if the key was already 372// present. Returns a reference to the value. Example usage: 373// 374// map<int, SomeProto> m; 375// SomeProto& proto = InsertKeyOrDie(&m, 3); 376// proto.set_field("foo"); 377template <class Collection> 378typename Collection::value_type::second_type& InsertKeyOrDie( 379 Collection* const collection, 380 const typename Collection::value_type::first_type& key) { 381 typedef typename Collection::value_type value_type; 382 std::pair<typename Collection::iterator, bool> res = 383 collection->insert(value_type(key, typename value_type::second_type())); 384 GOOGLE_CHECK(res.second) << "duplicate key: " << key; 385 return res.first->second; 386} 387 388// 389// Lookup*() 390// 391 392// Looks up a given key and value pair in a collection and inserts the key-value 393// pair if it's not already present. Returns a reference to the value associated 394// with the key. 395template <class Collection> 396typename Collection::value_type::second_type& 397LookupOrInsert(Collection* const collection, 398 const typename Collection::value_type& vt) { 399 return collection->insert(vt).first->second; 400} 401 402// Same as above except the key-value are passed separately. 403template <class Collection> 404typename Collection::value_type::second_type& 405LookupOrInsert(Collection* const collection, 406 const typename Collection::value_type::first_type& key, 407 const typename Collection::value_type::second_type& value) { 408 return LookupOrInsert( 409 collection, typename Collection::value_type(key, value)); 410} 411 412// Counts the number of equivalent elements in the given "sequence", and stores 413// the results in "count_map" with element as the key and count as the value. 414// 415// Example: 416// vector<string> v = {"a", "b", "c", "a", "b"}; 417// map<string, int> m; 418// AddTokenCounts(v, 1, &m); 419// assert(m["a"] == 2); 420// assert(m["b"] == 2); 421// assert(m["c"] == 1); 422template <typename Sequence, typename Collection> 423void AddTokenCounts( 424 const Sequence& sequence, 425 const typename Collection::value_type::second_type& increment, 426 Collection* const count_map) { 427 for (typename Sequence::const_iterator it = sequence.begin(); 428 it != sequence.end(); ++it) { 429 typename Collection::value_type::second_type& value = 430 LookupOrInsert(count_map, *it, 431 typename Collection::value_type::second_type()); 432 value += increment; 433 } 434} 435 436// Returns a reference to the value associated with key. If not found, a value 437// is default constructed on the heap and added to the map. 438// 439// This function is useful for containers of the form map<Key, Value*>, where 440// inserting a new key, value pair involves constructing a new heap-allocated 441// Value, and storing a pointer to that in the collection. 442template <class Collection> 443typename Collection::value_type::second_type& 444LookupOrInsertNew(Collection* const collection, 445 const typename Collection::value_type::first_type& key) { 446 typedef typename std::iterator_traits< 447 typename Collection::value_type::second_type>::value_type Element; 448 std::pair<typename Collection::iterator, bool> ret = 449 collection->insert(typename Collection::value_type( 450 key, 451 static_cast<typename Collection::value_type::second_type>(NULL))); 452 if (ret.second) { 453 ret.first->second = new Element(); 454 } 455 return ret.first->second; 456} 457 458// Same as above but constructs the value using the single-argument constructor 459// and the given "arg". 460template <class Collection, class Arg> 461typename Collection::value_type::second_type& 462LookupOrInsertNew(Collection* const collection, 463 const typename Collection::value_type::first_type& key, 464 const Arg& arg) { 465 typedef typename std::iterator_traits< 466 typename Collection::value_type::second_type>::value_type Element; 467 std::pair<typename Collection::iterator, bool> ret = 468 collection->insert(typename Collection::value_type( 469 key, 470 static_cast<typename Collection::value_type::second_type>(NULL))); 471 if (ret.second) { 472 ret.first->second = new Element(arg); 473 } 474 return ret.first->second; 475} 476 477// Lookup of linked/shared pointers is used in two scenarios: 478// 479// Use LookupOrInsertNewLinkedPtr if the container owns the elements. 480// In this case it is fine working with the raw pointer as long as it is 481// guaranteed that no other thread can delete/update an accessed element. 482// A mutex will need to lock the container operation as well as the use 483// of the returned elements. Finding an element may be performed using 484// FindLinkedPtr*(). 485// 486// Use LookupOrInsertNewSharedPtr if the container does not own the elements 487// for their whole lifetime. This is typically the case when a reader allows 488// parallel updates to the container. In this case a Mutex only needs to lock 489// container operations, but all element operations must be performed on the 490// shared pointer. Finding an element must be performed using FindPtr*() and 491// cannot be done with FindLinkedPtr*() even though it compiles. 492 493// Lookup a key in a map or hash_map whose values are linked_ptrs. If it is 494// missing, set collection[key].reset(new Value::element_type) and return that. 495// Value::element_type must be default constructable. 496template <class Collection> 497typename Collection::value_type::second_type::element_type* 498LookupOrInsertNewLinkedPtr( 499 Collection* const collection, 500 const typename Collection::value_type::first_type& key) { 501 typedef typename Collection::value_type::second_type Value; 502 std::pair<typename Collection::iterator, bool> ret = 503 collection->insert(typename Collection::value_type(key, Value())); 504 if (ret.second) { 505 ret.first->second.reset(new typename Value::element_type); 506 } 507 return ret.first->second.get(); 508} 509 510// A variant of LookupOrInsertNewLinkedPtr where the value is constructed using 511// a single-parameter constructor. Note: the constructor argument is computed 512// even if it will not be used, so only values cheap to compute should be passed 513// here. On the other hand it does not matter how expensive the construction of 514// the actual stored value is, as that only occurs if necessary. 515template <class Collection, class Arg> 516typename Collection::value_type::second_type::element_type* 517LookupOrInsertNewLinkedPtr( 518 Collection* const collection, 519 const typename Collection::value_type::first_type& key, 520 const Arg& arg) { 521 typedef typename Collection::value_type::second_type Value; 522 std::pair<typename Collection::iterator, bool> ret = 523 collection->insert(typename Collection::value_type(key, Value())); 524 if (ret.second) { 525 ret.first->second.reset(new typename Value::element_type(arg)); 526 } 527 return ret.first->second.get(); 528} 529 530// Lookup a key in a map or hash_map whose values are shared_ptrs. If it is 531// missing, set collection[key].reset(new Value::element_type). Unlike 532// LookupOrInsertNewLinkedPtr, this function returns the shared_ptr instead of 533// the raw pointer. Value::element_type must be default constructable. 534template <class Collection> 535typename Collection::value_type::second_type& 536LookupOrInsertNewSharedPtr( 537 Collection* const collection, 538 const typename Collection::value_type::first_type& key) { 539 typedef typename Collection::value_type::second_type SharedPtr; 540 typedef typename Collection::value_type::second_type::element_type Element; 541 std::pair<typename Collection::iterator, bool> ret = 542 collection->insert(typename Collection::value_type(key, SharedPtr())); 543 if (ret.second) { 544 ret.first->second.reset(new Element()); 545 } 546 return ret.first->second; 547} 548 549// A variant of LookupOrInsertNewSharedPtr where the value is constructed using 550// a single-parameter constructor. Note: the constructor argument is computed 551// even if it will not be used, so only values cheap to compute should be passed 552// here. On the other hand it does not matter how expensive the construction of 553// the actual stored value is, as that only occurs if necessary. 554template <class Collection, class Arg> 555typename Collection::value_type::second_type& 556LookupOrInsertNewSharedPtr( 557 Collection* const collection, 558 const typename Collection::value_type::first_type& key, 559 const Arg& arg) { 560 typedef typename Collection::value_type::second_type SharedPtr; 561 typedef typename Collection::value_type::second_type::element_type Element; 562 std::pair<typename Collection::iterator, bool> ret = 563 collection->insert(typename Collection::value_type(key, SharedPtr())); 564 if (ret.second) { 565 ret.first->second.reset(new Element(arg)); 566 } 567 return ret.first->second; 568} 569 570// 571// Misc Utility Functions 572// 573 574// Updates the value associated with the given key. If the key was not already 575// present, then the key-value pair are inserted and "previous" is unchanged. If 576// the key was already present, the value is updated and "*previous" will 577// contain a copy of the old value. 578// 579// InsertOrReturnExisting has complementary behavior that returns the 580// address of an already existing value, rather than updating it. 581template <class Collection> 582bool UpdateReturnCopy(Collection* const collection, 583 const typename Collection::value_type::first_type& key, 584 const typename Collection::value_type::second_type& value, 585 typename Collection::value_type::second_type* previous) { 586 std::pair<typename Collection::iterator, bool> ret = 587 collection->insert(typename Collection::value_type(key, value)); 588 if (!ret.second) { 589 // update 590 if (previous) { 591 *previous = ret.first->second; 592 } 593 ret.first->second = value; 594 return true; 595 } 596 return false; 597} 598 599// Same as above except that the key and value are passed as a pair. 600template <class Collection> 601bool UpdateReturnCopy(Collection* const collection, 602 const typename Collection::value_type& vt, 603 typename Collection::value_type::second_type* previous) { 604 std::pair<typename Collection::iterator, bool> ret = collection->insert(vt); 605 if (!ret.second) { 606 // update 607 if (previous) { 608 *previous = ret.first->second; 609 } 610 ret.first->second = vt.second; 611 return true; 612 } 613 return false; 614} 615 616// Tries to insert the given key-value pair into the collection. Returns NULL if 617// the insert succeeds. Otherwise, returns a pointer to the existing value. 618// 619// This complements UpdateReturnCopy in that it allows to update only after 620// verifying the old value and still insert quickly without having to look up 621// twice. Unlike UpdateReturnCopy this also does not come with the issue of an 622// undefined previous* in case new data was inserted. 623template <class Collection> 624typename Collection::value_type::second_type* const 625InsertOrReturnExisting(Collection* const collection, 626 const typename Collection::value_type& vt) { 627 std::pair<typename Collection::iterator, bool> ret = collection->insert(vt); 628 if (ret.second) { 629 return NULL; // Inserted, no existing previous value. 630 } else { 631 return &ret.first->second; // Return address of already existing value. 632 } 633} 634 635// Same as above, except for explicit key and data. 636template <class Collection> 637typename Collection::value_type::second_type* const 638InsertOrReturnExisting( 639 Collection* const collection, 640 const typename Collection::value_type::first_type& key, 641 const typename Collection::value_type::second_type& data) { 642 return InsertOrReturnExisting(collection, 643 typename Collection::value_type(key, data)); 644} 645 646// Erases the collection item identified by the given key, and returns the value 647// associated with that key. It is assumed that the value (i.e., the 648// mapped_type) is a pointer. Returns NULL if the key was not found in the 649// collection. 650// 651// Examples: 652// map<string, MyType*> my_map; 653// 654// One line cleanup: 655// delete EraseKeyReturnValuePtr(&my_map, "abc"); 656// 657// Use returned value: 658// scoped_ptr<MyType> value_ptr(EraseKeyReturnValuePtr(&my_map, "abc")); 659// if (value_ptr.get()) 660// value_ptr->DoSomething(); 661// 662template <class Collection> 663typename Collection::value_type::second_type EraseKeyReturnValuePtr( 664 Collection* const collection, 665 const typename Collection::value_type::first_type& key) { 666 typename Collection::iterator it = collection->find(key); 667 if (it == collection->end()) { 668 return NULL; 669 } 670 typename Collection::value_type::second_type v = it->second; 671 collection->erase(it); 672 return v; 673} 674 675// Inserts all the keys from map_container into key_container, which must 676// support insert(MapContainer::key_type). 677// 678// Note: any initial contents of the key_container are not cleared. 679template <class MapContainer, class KeyContainer> 680void InsertKeysFromMap(const MapContainer& map_container, 681 KeyContainer* key_container) { 682 GOOGLE_CHECK(key_container != NULL); 683 for (typename MapContainer::const_iterator it = map_container.begin(); 684 it != map_container.end(); ++it) { 685 key_container->insert(it->first); 686 } 687} 688 689// Appends all the keys from map_container into key_container, which must 690// support push_back(MapContainer::key_type). 691// 692// Note: any initial contents of the key_container are not cleared. 693template <class MapContainer, class KeyContainer> 694void AppendKeysFromMap(const MapContainer& map_container, 695 KeyContainer* key_container) { 696 GOOGLE_CHECK(key_container != NULL); 697 for (typename MapContainer::const_iterator it = map_container.begin(); 698 it != map_container.end(); ++it) { 699 key_container->push_back(it->first); 700 } 701} 702 703// A more specialized overload of AppendKeysFromMap to optimize reallocations 704// for the common case in which we're appending keys to a vector and hence can 705// (and sometimes should) call reserve() first. 706// 707// (It would be possible to play SFINAE games to call reserve() for any 708// container that supports it, but this seems to get us 99% of what we need 709// without the complexity of a SFINAE-based solution.) 710template <class MapContainer, class KeyType> 711void AppendKeysFromMap(const MapContainer& map_container, 712 vector<KeyType>* key_container) { 713 GOOGLE_CHECK(key_container != NULL); 714 // We now have the opportunity to call reserve(). Calling reserve() every 715 // time is a bad idea for some use cases: libstdc++'s implementation of 716 // vector<>::reserve() resizes the vector's backing store to exactly the 717 // given size (unless it's already at least that big). Because of this, 718 // the use case that involves appending a lot of small maps (total size 719 // N) one by one to a vector would be O(N^2). But never calling reserve() 720 // loses the opportunity to improve the use case of adding from a large 721 // map to an empty vector (this improves performance by up to 33%). A 722 // number of heuristics are possible; see the discussion in 723 // cl/34081696. Here we use the simplest one. 724 if (key_container->empty()) { 725 key_container->reserve(map_container.size()); 726 } 727 for (typename MapContainer::const_iterator it = map_container.begin(); 728 it != map_container.end(); ++it) { 729 key_container->push_back(it->first); 730 } 731} 732 733// Inserts all the values from map_container into value_container, which must 734// support push_back(MapContainer::mapped_type). 735// 736// Note: any initial contents of the value_container are not cleared. 737template <class MapContainer, class ValueContainer> 738void AppendValuesFromMap(const MapContainer& map_container, 739 ValueContainer* value_container) { 740 GOOGLE_CHECK(value_container != NULL); 741 for (typename MapContainer::const_iterator it = map_container.begin(); 742 it != map_container.end(); ++it) { 743 value_container->push_back(it->second); 744 } 745} 746 747// A more specialized overload of AppendValuesFromMap to optimize reallocations 748// for the common case in which we're appending values to a vector and hence 749// can (and sometimes should) call reserve() first. 750// 751// (It would be possible to play SFINAE games to call reserve() for any 752// container that supports it, but this seems to get us 99% of what we need 753// without the complexity of a SFINAE-based solution.) 754template <class MapContainer, class ValueType> 755void AppendValuesFromMap(const MapContainer& map_container, 756 vector<ValueType>* value_container) { 757 GOOGLE_CHECK(value_container != NULL); 758 // See AppendKeysFromMap for why this is done. 759 if (value_container->empty()) { 760 value_container->reserve(map_container.size()); 761 } 762 for (typename MapContainer::const_iterator it = map_container.begin(); 763 it != map_container.end(); ++it) { 764 value_container->push_back(it->second); 765 } 766} 767 768} // namespace protobuf 769} // namespace google 770 771#endif // GOOGLE_PROTOBUF_STUBS_MAP_UTIL_H__ 772