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 nullptr 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// nullptr 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 nullptr.
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 nullptr 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// nullptr). 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))
341 << "duplicate value: " << value;
342}
343
344// Same as above except doesn't log the value on error.
345template <class Collection>
346void InsertOrDieNoPrint(Collection* const collection,
347 const typename Collection::value_type& value) {
348 GOOGLE_CHECK(InsertIfNotPresent(collection, value)) << "duplicate value.";
349}
350
351// Inserts the key-value pair into the collection. Dies if key was already
352// present.
353template <class Collection>
354void InsertOrDie(Collection* const collection,
355 const typename Collection::value_type::first_type& key,
356 const typename Collection::value_type::second_type& data) {
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 GOOGLE_CHECK(InsertIfNotPresent(collection, key, data)) << "duplicate key.";
368}
369
370// Inserts a new key and default-initialized value. Dies if the key was already
371// present. Returns a reference to the value. Example usage:
372//
373// map<int, SomeProto> m;
374// SomeProto& proto = InsertKeyOrDie(&m, 3);
375// proto.set_field("foo");
376template <class Collection>
377typename Collection::value_type::second_type& InsertKeyOrDie(
378 Collection* const collection,
379 const typename Collection::value_type::first_type& key) {
380 typedef typename Collection::value_type value_type;
381 std::pair<typename Collection::iterator, bool> res =
382 collection->insert(value_type(key, typename value_type::second_type()));
383 GOOGLE_CHECK(res.second) << "duplicate key: " << key;
384 return res.first->second;
385}
386
387//
388// Lookup*()
389//
390
391// Looks up a given key and value pair in a collection and inserts the key-value
392// pair if it's not already present. Returns a reference to the value associated
393// with the key.
394template <class Collection>
395typename Collection::value_type::second_type&
396LookupOrInsert(Collection* const collection,
397 const typename Collection::value_type& vt) {
398 return collection->insert(vt).first->second;
399}
400
401// Same as above except the key-value are passed separately.
402template <class Collection>
403typename Collection::value_type::second_type&
404LookupOrInsert(Collection* const collection,
405 const typename Collection::value_type::first_type& key,
406 const typename Collection::value_type::second_type& value) {
407 return LookupOrInsert(
408 collection, typename Collection::value_type(key, value));
409}
410
411// Counts the number of equivalent elements in the given "sequence", and stores
412// the results in "count_map" with element as the key and count as the value.
413//
414// Example:
415// vector<string> v = {"a", "b", "c", "a", "b"};
416// map<string, int> m;
417// AddTokenCounts(v, 1, &m);
418// assert(m["a"] == 2);
419// assert(m["b"] == 2);
420// assert(m["c"] == 1);
421template <typename Sequence, typename Collection>
422void AddTokenCounts(
423 const Sequence& sequence,
424 const typename Collection::value_type::second_type& increment,
425 Collection* const count_map) {
426 for (typename Sequence::const_iterator it = sequence.begin();
427 it != sequence.end(); ++it) {
428 typename Collection::value_type::second_type& value =
429 LookupOrInsert(count_map, *it,
430 typename Collection::value_type::second_type());
431 value += increment;
432 }
433}
434
435// Returns a reference to the value associated with key. If not found, a value
436// is default constructed on the heap and added to the map.
437//
438// This function is useful for containers of the form map<Key, Value*>, where
439// inserting a new key, value pair involves constructing a new heap-allocated
440// Value, and storing a pointer to that in the collection.
441template <class Collection>
442typename Collection::value_type::second_type&
443LookupOrInsertNew(Collection* const collection,
444 const typename Collection::value_type::first_type& key) {
445 typedef typename std::iterator_traits<
446 typename Collection::value_type::second_type>::value_type Element;
447 std::pair<typename Collection::iterator, bool> ret =
448 collection->insert(typename Collection::value_type(
449 key,
450 static_cast<typename Collection::value_type::second_type>(nullptr)));
451 if (ret.second) {
452 ret.first->second = new Element();
453 }
454 return ret.first->second;
455}
456
457// Same as above but constructs the value using the single-argument constructor
458// and the given "arg".
459template <class Collection, class Arg>
460typename Collection::value_type::second_type&
461LookupOrInsertNew(Collection* const collection,
462 const typename Collection::value_type::first_type& key,
463 const Arg& arg) {
464 typedef typename std::iterator_traits<
465 typename Collection::value_type::second_type>::value_type Element;
466 std::pair<typename Collection::iterator, bool> ret =
467 collection->insert(typename Collection::value_type(
468 key,
469 static_cast<typename Collection::value_type::second_type>(nullptr)));
470 if (ret.second) {
471 ret.first->second = new Element(arg);
472 }
473 return ret.first->second;
474}
475
476// Lookup of linked/shared pointers is used in two scenarios:
477//
478// Use LookupOrInsertNewLinkedPtr if the container owns the elements.
479// In this case it is fine working with the raw pointer as long as it is
480// guaranteed that no other thread can delete/update an accessed element.
481// A mutex will need to lock the container operation as well as the use
482// of the returned elements. Finding an element may be performed using
483// FindLinkedPtr*().
484//
485// Use LookupOrInsertNewSharedPtr if the container does not own the elements
486// for their whole lifetime. This is typically the case when a reader allows
487// parallel updates to the container. In this case a Mutex only needs to lock
488// container operations, but all element operations must be performed on the
489// shared pointer. Finding an element must be performed using FindPtr*() and
490// cannot be done with FindLinkedPtr*() even though it compiles.
491
492// Lookup a key in a map or hash_map whose values are linked_ptrs. If it is
493// missing, set collection[key].reset(new Value::element_type) and return that.
494// Value::element_type must be default constructable.
495template <class Collection>
496typename Collection::value_type::second_type::element_type*
497LookupOrInsertNewLinkedPtr(
498 Collection* const collection,
499 const typename Collection::value_type::first_type& key) {
500 typedef typename Collection::value_type::second_type Value;
501 std::pair<typename Collection::iterator, bool> ret =
502 collection->insert(typename Collection::value_type(key, Value()));
503 if (ret.second) {
504 ret.first->second.reset(new typename Value::element_type);
505 }
506 return ret.first->second.get();
507}
508
509// A variant of LookupOrInsertNewLinkedPtr where the value is constructed using
510// a single-parameter constructor. Note: the constructor argument is computed
511// even if it will not be used, so only values cheap to compute should be passed
512// here. On the other hand it does not matter how expensive the construction of
513// the actual stored value is, as that only occurs if necessary.
514template <class Collection, class Arg>
515typename Collection::value_type::second_type::element_type*
516LookupOrInsertNewLinkedPtr(
517 Collection* const collection,
518 const typename Collection::value_type::first_type& key,
519 const Arg& arg) {
520 typedef typename Collection::value_type::second_type Value;
521 std::pair<typename Collection::iterator, bool> ret =
522 collection->insert(typename Collection::value_type(key, Value()));
523 if (ret.second) {
524 ret.first->second.reset(new typename Value::element_type(arg));
525 }
526 return ret.first->second.get();
527}
528
529// Lookup a key in a map or hash_map whose values are shared_ptrs. If it is
530// missing, set collection[key].reset(new Value::element_type). Unlike
531// LookupOrInsertNewLinkedPtr, this function returns the shared_ptr instead of
532// the raw pointer. Value::element_type must be default constructable.
533template <class Collection>
534typename Collection::value_type::second_type&
535LookupOrInsertNewSharedPtr(
536 Collection* const collection,
537 const typename Collection::value_type::first_type& key) {
538 typedef typename Collection::value_type::second_type SharedPtr;
539 typedef typename Collection::value_type::second_type::element_type Element;
540 std::pair<typename Collection::iterator, bool> ret =
541 collection->insert(typename Collection::value_type(key, SharedPtr()));
542 if (ret.second) {
543 ret.first->second.reset(new Element());
544 }
545 return ret.first->second;
546}
547
548// A variant of LookupOrInsertNewSharedPtr where the value is constructed using
549// a single-parameter constructor. Note: the constructor argument is computed
550// even if it will not be used, so only values cheap to compute should be passed
551// here. On the other hand it does not matter how expensive the construction of
552// the actual stored value is, as that only occurs if necessary.
553template <class Collection, class Arg>
554typename Collection::value_type::second_type&
555LookupOrInsertNewSharedPtr(
556 Collection* const collection,
557 const typename Collection::value_type::first_type& key,
558 const Arg& arg) {
559 typedef typename Collection::value_type::second_type SharedPtr;
560 typedef typename Collection::value_type::second_type::element_type Element;
561 std::pair<typename Collection::iterator, bool> ret =
562 collection->insert(typename Collection::value_type(key, SharedPtr()));
563 if (ret.second) {
564 ret.first->second.reset(new Element(arg));
565 }
566 return ret.first->second;
567}
568
569//
570// Misc Utility Functions
571//
572
573// Updates the value associated with the given key. If the key was not already
574// present, then the key-value pair are inserted and "previous" is unchanged. If
575// the key was already present, the value is updated and "*previous" will
576// contain a copy of the old value.
577//
578// InsertOrReturnExisting has complementary behavior that returns the
579// address of an already existing value, rather than updating it.
580template <class Collection>
581bool UpdateReturnCopy(Collection* const collection,
582 const typename Collection::value_type::first_type& key,
583 const typename Collection::value_type::second_type& value,
584 typename Collection::value_type::second_type* previous) {
585 std::pair<typename Collection::iterator, bool> ret =
586 collection->insert(typename Collection::value_type(key, value));
587 if (!ret.second) {
588 // update
589 if (previous) {
590 *previous = ret.first->second;
591 }
592 ret.first->second = value;
593 return true;
594 }
595 return false;
596}
597
598// Same as above except that the key and value are passed as a pair.
599template <class Collection>
600bool UpdateReturnCopy(Collection* const collection,
601 const typename Collection::value_type& vt,
602 typename Collection::value_type::second_type* previous) {
603 std::pair<typename Collection::iterator, bool> ret = collection->insert(vt);
604 if (!ret.second) {
605 // update
606 if (previous) {
607 *previous = ret.first->second;
608 }
609 ret.first->second = vt.second;
610 return true;
611 }
612 return false;
613}
614
615// Tries to insert the given key-value pair into the collection. Returns nullptr if
616// the insert succeeds. Otherwise, returns a pointer to the existing value.
617//
618// This complements UpdateReturnCopy in that it allows to update only after
619// verifying the old value and still insert quickly without having to look up
620// twice. Unlike UpdateReturnCopy this also does not come with the issue of an
621// undefined previous* in case new data was inserted.
622template <class Collection>
623typename Collection::value_type::second_type* InsertOrReturnExisting(
624 Collection* const collection, const typename Collection::value_type& vt) {
625 std::pair<typename Collection::iterator, bool> ret = collection->insert(vt);
626 if (ret.second) {
627 return nullptr; // 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* InsertOrReturnExisting(
636 Collection* const collection,
637 const typename Collection::value_type::first_type& key,
638 const typename Collection::value_type::second_type& data) {
639 return InsertOrReturnExisting(collection,
640 typename Collection::value_type(key, data));
641}
642
643// Erases the collection item identified by the given key, and returns the value
644// associated with that key. It is assumed that the value (i.e., the
645// mapped_type) is a pointer. Returns nullptr if the key was not found in the
646// collection.
647//
648// Examples:
649// map<string, MyType*> my_map;
650//
651// One line cleanup:
652// delete EraseKeyReturnValuePtr(&my_map, "abc");
653//
654// Use returned value:
655// std::unique_ptr<MyType> value_ptr(
656// 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 nullptr;
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 != nullptr);
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 != nullptr);
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 std::vector<KeyType>* key_container) {
711 GOOGLE_CHECK(key_container != nullptr);
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 != nullptr);
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 std::vector<ValueType>* value_container) {
755 GOOGLE_CHECK(value_container != nullptr);
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