src/google/protobuf/stubs/map_util.h

   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
  45 namespace google {
  46 namespace protobuf {
  47 namespace internal {
  48 // Local implementation of RemoveConst to avoid including base/type_traits.h.
  49 template <class T> struct RemoveConst { typedef T type; };
  50 template <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.
  72 template <class Collection>
  73 const typename Collection::value_type::second_type&
  74 FindOrDie(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.
  82 template <class Collection>
  83 typename Collection::value_type::second_type&
  84 FindOrDie(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.
  92 template <class Collection>
  93 const typename Collection::value_type::second_type&
  94 FindOrDieNoPrint(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.
 102 template <class Collection>
 103 typename Collection::value_type::second_type&
 104 FindOrDieNoPrint(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
 121 template <class Collection>
 122 const typename Collection::value_type::second_type&
 123 FindWithDefault(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.
 135 template <class Collection>
 136 const typename Collection::value_type::second_type*
 137 FindOrNull(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.
 147 template <class Collection>
 148 typename Collection::value_type::second_type*
 149 FindOrNull(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.
 164 template <class Collection>
 165 typename Collection::value_type::second_type
 166 FindPtrOrNull(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.
 179 template <class Collection>
 180 typename Collection::value_type::second_type
 181 FindPtrOrNull(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.
 192 template <class Collection>
 193 typename Collection::value_type::second_type::element_type*
 194 FindLinkedPtrOrNull(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.
 206 template <class Collection>
 207 typename Collection::value_type::second_type::element_type&
 208 FindLinkedPtrOrDie(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.
 219 template <class Collection, class Key, class Value>
 220 bool 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.
 238 template <class Collection, class Key>
 239 bool 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.
 245 template <class Collection, class Key, class Value>
 246 bool 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.
 266 template <class Collection>
 267 bool 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.
 279 template <class Collection>
 280 bool 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.
 289 template <class Collection, class InputIterator>
 290 void 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.
 301 template <class Collection>
 302 bool 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.
 320 template <class Collection>
 321 bool 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.
 327 template <class Collection>
 328 bool 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.
 337 template <class Collection>
 338 void 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.
 344 template <class Collection>
 345 void 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.
 352 template <class Collection>
 353 void 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.
 362 template <class Collection>
 363 void 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");
 377 template <class Collection>
 378 typename 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.
 395 template <class Collection>
 396 typename Collection::value_type::second_type&
 397 LookupOrInsert(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.
 403 template <class Collection>
 404 typename Collection::value_type::second_type&
 405 LookupOrInsert(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);
 422 template <typename Sequence, typename Collection>
 423 void 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.
 442 template <class Collection>
 443 typename Collection::value_type::second_type&
 444 LookupOrInsertNew(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".
 460 template <class Collection, class Arg>
 461 typename Collection::value_type::second_type&
 462 LookupOrInsertNew(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.
 496 template <class Collection>
 497 typename Collection::value_type::second_type::element_type*
 498 LookupOrInsertNewLinkedPtr(
 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.
 515 template <class Collection, class Arg>
 516 typename Collection::value_type::second_type::element_type*
 517 LookupOrInsertNewLinkedPtr(
 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.
 534 template <class Collection>
 535 typename Collection::value_type::second_type&
 536 LookupOrInsertNewSharedPtr(
 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.
 554 template <class Collection, class Arg>
 555 typename Collection::value_type::second_type&
 556 LookupOrInsertNewSharedPtr(
 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.
 581 template <class Collection>
 582 bool 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.
 600 template <class Collection>
 601 bool 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.
 623 template <class Collection>
 624 typename Collection::value_type::second_type* const
 625 InsertOrReturnExisting(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.
 636 template <class Collection>
 637 typename Collection::value_type::second_type* const
 638 InsertOrReturnExisting(
 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 //
 662 template <class Collection>
 663 typename 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.
 679 template <class MapContainer, class KeyContainer>
 680 void 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.
 693 template <class MapContainer, class KeyContainer>
 694 void 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.)
 710 template <class MapContainer, class KeyType>
 711 void 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.
 737 template <class MapContainer, class ValueContainer>
 738 void 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.)
 754 template <class MapContainer, class ValueType>
 755 void 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__