diff options
Diffstat (limited to 'src/google/protobuf/stubs/map_util.h')
| -rw-r--r-- | src/google/protobuf/stubs/map_util.h | 771 |
1 files changed, 771 insertions, 0 deletions
diff --git a/src/google/protobuf/stubs/map_util.h b/src/google/protobuf/stubs/map_util.h new file mode 100644 index 0000000..fb2f5f3 --- /dev/null +++ b/src/google/protobuf/stubs/map_util.h @@ -0,0 +1,771 @@ +// Protocol Buffers - Google's data interchange format +// Copyright 2014 Google Inc. All rights reserved. +// http://code.google.com/p/protobuf/ +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following disclaimer +// in the documentation and/or other materials provided with the +// distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +// from google3/util/gtl/map_util.h +// Author: Anton Carver + +#ifndef GOOGLE_PROTOBUF_STUBS_MAP_UTIL_H__ +#define GOOGLE_PROTOBUF_STUBS_MAP_UTIL_H__ + +#include <stddef.h> +#include <iterator> +#include <string> +#include <utility> +#include <vector> + +#include <google/protobuf/stubs/common.h> + +namespace google { +namespace protobuf { +namespace internal { +// Local implementation of RemoveConst to avoid including base/type_traits.h. +template <class T> struct RemoveConst { typedef T type; }; +template <class T> struct RemoveConst<const T> : RemoveConst<T> {}; +} // namespace internal + +// +// Find*() +// + +// Returns a const reference to the value associated with the given key if it +// exists. Crashes otherwise. +// +// This is intended as a replacement for operator[] as an rvalue (for reading) +// when the key is guaranteed to exist. +// +// operator[] for lookup is discouraged for several reasons: +// * It has a side-effect of inserting missing keys +// * It is not thread-safe (even when it is not inserting, it can still +// choose to resize the underlying storage) +// * It invalidates iterators (when it chooses to resize) +// * It default constructs a value object even if it doesn't need to +// +// This version assumes the key is printable, and includes it in the fatal log +// message. +template <class Collection> +const typename Collection::value_type::second_type& +FindOrDie(const Collection& collection, + const typename Collection::value_type::first_type& key) { + typename Collection::const_iterator it = collection.find(key); + GOOGLE_CHECK(it != collection.end()) << "Map key not found: " << key; + return it->second; +} + +// Same as above, but returns a non-const reference. +template <class Collection> +typename Collection::value_type::second_type& +FindOrDie(Collection& collection, // NOLINT + const typename Collection::value_type::first_type& key) { + typename Collection::iterator it = collection.find(key); + GOOGLE_CHECK(it != collection.end()) << "Map key not found: " << key; + return it->second; +} + +// Same as FindOrDie above, but doesn't log the key on failure. +template <class Collection> +const typename Collection::value_type::second_type& +FindOrDieNoPrint(const Collection& collection, + const typename Collection::value_type::first_type& key) { + typename Collection::const_iterator it = collection.find(key); + GOOGLE_CHECK(it != collection.end()) << "Map key not found"; + return it->second; +} + +// Same as above, but returns a non-const reference. +template <class Collection> +typename Collection::value_type::second_type& +FindOrDieNoPrint(Collection& collection, // NOLINT + const typename Collection::value_type::first_type& key) { + typename Collection::iterator it = collection.find(key); + GOOGLE_CHECK(it != collection.end()) << "Map key not found"; + return it->second; +} + +// Returns a const reference to the value associated with the given key if it +// exists, otherwise returns a const reference to the provided default value. +// +// WARNING: If a temporary object is passed as the default "value," +// this function will return a reference to that temporary object, +// which will be destroyed at the end of the statement. A common +// example: if you have a map with string values, and you pass a char* +// as the default "value," either use the returned value immediately +// or store it in a string (not string&). +// Details: http://go/findwithdefault +template <class Collection> +const typename Collection::value_type::second_type& +FindWithDefault(const Collection& collection, + const typename Collection::value_type::first_type& key, + const typename Collection::value_type::second_type& value) { + typename Collection::const_iterator it = collection.find(key); + if (it == collection.end()) { + return value; + } + return it->second; +} + +// Returns a pointer to the const value associated with the given key if it +// exists, or NULL otherwise. +template <class Collection> +const typename Collection::value_type::second_type* +FindOrNull(const Collection& collection, + const typename Collection::value_type::first_type& key) { + typename Collection::const_iterator it = collection.find(key); + if (it == collection.end()) { + return 0; + } + return &it->second; +} + +// Same as above but returns a pointer to the non-const value. +template <class Collection> +typename Collection::value_type::second_type* +FindOrNull(Collection& collection, // NOLINT + const typename Collection::value_type::first_type& key) { + typename Collection::iterator it = collection.find(key); + if (it == collection.end()) { + return 0; + } + return &it->second; +} + +// Returns the pointer value associated with the given key. If none is found, +// NULL is returned. The function is designed to be used with a map of keys to +// pointers. +// +// This function does not distinguish between a missing key and a key mapped +// to a NULL value. +template <class Collection> +typename Collection::value_type::second_type +FindPtrOrNull(const Collection& collection, + const typename Collection::value_type::first_type& key) { + typename Collection::const_iterator it = collection.find(key); + if (it == collection.end()) { + return typename Collection::value_type::second_type(); + } + return it->second; +} + +// Same as above, except takes non-const reference to collection. +// +// This function is needed for containers that propagate constness to the +// pointee, such as boost::ptr_map. +template <class Collection> +typename Collection::value_type::second_type +FindPtrOrNull(Collection& collection, // NOLINT + const typename Collection::value_type::first_type& key) { + typename Collection::iterator it = collection.find(key); + if (it == collection.end()) { + return typename Collection::value_type::second_type(); + } + return it->second; +} + +// Finds the pointer value associated with the given key in a map whose values +// are linked_ptrs. Returns NULL if key is not found. +template <class Collection> +typename Collection::value_type::second_type::element_type* +FindLinkedPtrOrNull(const Collection& collection, + const typename Collection::value_type::first_type& key) { + typename Collection::const_iterator it = collection.find(key); + if (it == collection.end()) { + return 0; + } + // Since linked_ptr::get() is a const member returning a non const, + // we do not need a version of this function taking a non const collection. + return it->second.get(); +} + +// Same as above, but dies if the key is not found. +template <class Collection> +typename Collection::value_type::second_type::element_type& +FindLinkedPtrOrDie(const Collection& collection, + const typename Collection::value_type::first_type& key) { + typename Collection::const_iterator it = collection.find(key); + CHECK(it != collection.end()) << "key not found: " << key; + // Since linked_ptr::operator*() is a const member returning a non const, + // we do not need a version of this function taking a non const collection. + return *it->second; +} + +// Finds the value associated with the given key and copies it to *value (if not +// NULL). Returns false if the key was not found, true otherwise. +template <class Collection, class Key, class Value> +bool FindCopy(const Collection& collection, + const Key& key, + Value* const value) { + typename Collection::const_iterator it = collection.find(key); + if (it == collection.end()) { + return false; + } + if (value) { + *value = it->second; + } + return true; +} + +// +// Contains*() +// + +// Returns true if and only if the given collection contains the given key. +template <class Collection, class Key> +bool ContainsKey(const Collection& collection, const Key& key) { + return collection.find(key) != collection.end(); +} + +// Returns true if and only if the given collection contains the given key-value +// pair. +template <class Collection, class Key, class Value> +bool ContainsKeyValuePair(const Collection& collection, + const Key& key, + const Value& value) { + typedef typename Collection::const_iterator const_iterator; + std::pair<const_iterator, const_iterator> range = collection.equal_range(key); + for (const_iterator it = range.first; it != range.second; ++it) { + if (it->second == value) { + return true; + } + } + return false; +} + +// +// Insert*() +// + +// Inserts the given key-value pair into the collection. Returns true if and +// only if the key from the given pair didn't previously exist. Otherwise, the +// value in the map is replaced with the value from the given pair. +template <class Collection> +bool InsertOrUpdate(Collection* const collection, + const typename Collection::value_type& vt) { + std::pair<typename Collection::iterator, bool> ret = collection->insert(vt); + if (!ret.second) { + // update + ret.first->second = vt.second; + return false; + } + return true; +} + +// Same as above, except that the key and value are passed separately. +template <class Collection> +bool InsertOrUpdate(Collection* const collection, + const typename Collection::value_type::first_type& key, + const typename Collection::value_type::second_type& value) { + return InsertOrUpdate( + collection, typename Collection::value_type(key, value)); +} + +// Inserts/updates all the key-value pairs from the range defined by the +// iterators "first" and "last" into the given collection. +template <class Collection, class InputIterator> +void InsertOrUpdateMany(Collection* const collection, + InputIterator first, InputIterator last) { + for (; first != last; ++first) { + InsertOrUpdate(collection, *first); + } +} + +// Change the value associated with a particular key in a map or hash_map +// of the form map<Key, Value*> which owns the objects pointed to by the +// value pointers. If there was an existing value for the key, it is deleted. +// True indicates an insert took place, false indicates an update + delete. +template <class Collection> +bool InsertAndDeleteExisting( + Collection* const collection, + const typename Collection::value_type::first_type& key, + const typename Collection::value_type::second_type& value) { + std::pair<typename Collection::iterator, bool> ret = + collection->insert(typename Collection::value_type(key, value)); + if (!ret.second) { + delete ret.first->second; + ret.first->second = value; + return false; + } + return true; +} + +// Inserts the given key and value into the given collection if and only if the +// given key did NOT already exist in the collection. If the key previously +// existed in the collection, the value is not changed. Returns true if the +// key-value pair was inserted; returns false if the key was already present. +template <class Collection> +bool InsertIfNotPresent(Collection* const collection, + const typename Collection::value_type& vt) { + return collection->insert(vt).second; +} + +// Same as above except the key and value are passed separately. +template <class Collection> +bool InsertIfNotPresent( + Collection* const collection, + const typename Collection::value_type::first_type& key, + const typename Collection::value_type::second_type& value) { + return InsertIfNotPresent( + collection, typename Collection::value_type(key, value)); +} + +// Same as above except dies if the key already exists in the collection. +template <class Collection> +void InsertOrDie(Collection* const collection, + const typename Collection::value_type& value) { + CHECK(InsertIfNotPresent(collection, value)) << "duplicate value: " << value; +} + +// Same as above except doesn't log the value on error. +template <class Collection> +void InsertOrDieNoPrint(Collection* const collection, + const typename Collection::value_type& value) { + CHECK(InsertIfNotPresent(collection, value)) << "duplicate value."; +} + +// Inserts the key-value pair into the collection. Dies if key was already +// present. +template <class Collection> +void InsertOrDie(Collection* const collection, + const typename Collection::value_type::first_type& key, + const typename Collection::value_type::second_type& data) { + typedef typename Collection::value_type value_type; + GOOGLE_CHECK(InsertIfNotPresent(collection, key, data)) + << "duplicate key: " << key; +} + +// Same as above except doesn't log the key on error. +template <class Collection> +void InsertOrDieNoPrint( + Collection* const collection, + const typename Collection::value_type::first_type& key, + const typename Collection::value_type::second_type& data) { + typedef typename Collection::value_type value_type; + GOOGLE_CHECK(InsertIfNotPresent(collection, key, data)) << "duplicate key."; +} + +// Inserts a new key and default-initialized value. Dies if the key was already +// present. Returns a reference to the value. Example usage: +// +// map<int, SomeProto> m; +// SomeProto& proto = InsertKeyOrDie(&m, 3); +// proto.set_field("foo"); +template <class Collection> +typename Collection::value_type::second_type& InsertKeyOrDie( + Collection* const collection, + const typename Collection::value_type::first_type& key) { + typedef typename Collection::value_type value_type; + std::pair<typename Collection::iterator, bool> res = + collection->insert(value_type(key, typename value_type::second_type())); + GOOGLE_CHECK(res.second) << "duplicate key: " << key; + return res.first->second; +} + +// +// Lookup*() +// + +// Looks up a given key and value pair in a collection and inserts the key-value +// pair if it's not already present. Returns a reference to the value associated +// with the key. +template <class Collection> +typename Collection::value_type::second_type& +LookupOrInsert(Collection* const collection, + const typename Collection::value_type& vt) { + return collection->insert(vt).first->second; +} + +// Same as above except the key-value are passed separately. +template <class Collection> +typename Collection::value_type::second_type& +LookupOrInsert(Collection* const collection, + const typename Collection::value_type::first_type& key, + const typename Collection::value_type::second_type& value) { + return LookupOrInsert( + collection, typename Collection::value_type(key, value)); +} + +// Counts the number of equivalent elements in the given "sequence", and stores +// the results in "count_map" with element as the key and count as the value. +// +// Example: +// vector<string> v = {"a", "b", "c", "a", "b"}; +// map<string, int> m; +// AddTokenCounts(v, 1, &m); +// assert(m["a"] == 2); +// assert(m["b"] == 2); +// assert(m["c"] == 1); +template <typename Sequence, typename Collection> +void AddTokenCounts( + const Sequence& sequence, + const typename Collection::value_type::second_type& increment, + Collection* const count_map) { + for (typename Sequence::const_iterator it = sequence.begin(); + it != sequence.end(); ++it) { + typename Collection::value_type::second_type& value = + LookupOrInsert(count_map, *it, + typename Collection::value_type::second_type()); + value += increment; + } +} + +// Returns a reference to the value associated with key. If not found, a value +// is default constructed on the heap and added to the map. +// +// This function is useful for containers of the form map<Key, Value*>, where +// inserting a new key, value pair involves constructing a new heap-allocated +// Value, and storing a pointer to that in the collection. +template <class Collection> +typename Collection::value_type::second_type& +LookupOrInsertNew(Collection* const collection, + const typename Collection::value_type::first_type& key) { + typedef typename std::iterator_traits< + typename Collection::value_type::second_type>::value_type Element; + std::pair<typename Collection::iterator, bool> ret = + collection->insert(typename Collection::value_type( + key, + static_cast<typename Collection::value_type::second_type>(NULL))); + if (ret.second) { + ret.first->second = new Element(); + } + return ret.first->second; +} + +// Same as above but constructs the value using the single-argument constructor +// and the given "arg". +template <class Collection, class Arg> +typename Collection::value_type::second_type& +LookupOrInsertNew(Collection* const collection, + const typename Collection::value_type::first_type& key, + const Arg& arg) { + typedef typename std::iterator_traits< + typename Collection::value_type::second_type>::value_type Element; + std::pair<typename Collection::iterator, bool> ret = + collection->insert(typename Collection::value_type( + key, + static_cast<typename Collection::value_type::second_type>(NULL))); + if (ret.second) { + ret.first->second = new Element(arg); + } + return ret.first->second; +} + +// Lookup of linked/shared pointers is used in two scenarios: +// +// Use LookupOrInsertNewLinkedPtr if the container owns the elements. +// In this case it is fine working with the raw pointer as long as it is +// guaranteed that no other thread can delete/update an accessed element. +// A mutex will need to lock the container operation as well as the use +// of the returned elements. Finding an element may be performed using +// FindLinkedPtr*(). +// +// Use LookupOrInsertNewSharedPtr if the container does not own the elements +// for their whole lifetime. This is typically the case when a reader allows +// parallel updates to the container. In this case a Mutex only needs to lock +// container operations, but all element operations must be performed on the +// shared pointer. Finding an element must be performed using FindPtr*() and +// cannot be done with FindLinkedPtr*() even though it compiles. + +// Lookup a key in a map or hash_map whose values are linked_ptrs. If it is +// missing, set collection[key].reset(new Value::element_type) and return that. +// Value::element_type must be default constructable. +template <class Collection> +typename Collection::value_type::second_type::element_type* +LookupOrInsertNewLinkedPtr( + Collection* const collection, + const typename Collection::value_type::first_type& key) { + typedef typename Collection::value_type::second_type Value; + std::pair<typename Collection::iterator, bool> ret = + collection->insert(typename Collection::value_type(key, Value())); + if (ret.second) { + ret.first->second.reset(new typename Value::element_type); + } + return ret.first->second.get(); +} + +// A variant of LookupOrInsertNewLinkedPtr where the value is constructed using +// a single-parameter constructor. Note: the constructor argument is computed +// even if it will not be used, so only values cheap to compute should be passed +// here. On the other hand it does not matter how expensive the construction of +// the actual stored value is, as that only occurs if necessary. +template <class Collection, class Arg> +typename Collection::value_type::second_type::element_type* +LookupOrInsertNewLinkedPtr( + Collection* const collection, + const typename Collection::value_type::first_type& key, + const Arg& arg) { + typedef typename Collection::value_type::second_type Value; + std::pair<typename Collection::iterator, bool> ret = + collection->insert(typename Collection::value_type(key, Value())); + if (ret.second) { + ret.first->second.reset(new typename Value::element_type(arg)); + } + return ret.first->second.get(); +} + +// Lookup a key in a map or hash_map whose values are shared_ptrs. If it is +// missing, set collection[key].reset(new Value::element_type). Unlike +// LookupOrInsertNewLinkedPtr, this function returns the shared_ptr instead of +// the raw pointer. Value::element_type must be default constructable. +template <class Collection> +typename Collection::value_type::second_type& +LookupOrInsertNewSharedPtr( + Collection* const collection, + const typename Collection::value_type::first_type& key) { + typedef typename Collection::value_type::second_type SharedPtr; + typedef typename Collection::value_type::second_type::element_type Element; + std::pair<typename Collection::iterator, bool> ret = + collection->insert(typename Collection::value_type(key, SharedPtr())); + if (ret.second) { + ret.first->second.reset(new Element()); + } + return ret.first->second; +} + +// A variant of LookupOrInsertNewSharedPtr where the value is constructed using +// a single-parameter constructor. Note: the constructor argument is computed +// even if it will not be used, so only values cheap to compute should be passed +// here. On the other hand it does not matter how expensive the construction of +// the actual stored value is, as that only occurs if necessary. +template <class Collection, class Arg> +typename Collection::value_type::second_type& +LookupOrInsertNewSharedPtr( + Collection* const collection, + const typename Collection::value_type::first_type& key, + const Arg& arg) { + typedef typename Collection::value_type::second_type SharedPtr; + typedef typename Collection::value_type::second_type::element_type Element; + std::pair<typename Collection::iterator, bool> ret = + collection->insert(typename Collection::value_type(key, SharedPtr())); + if (ret.second) { + ret.first->second.reset(new Element(arg)); + } + return ret.first->second; +} + +// +// Misc Utility Functions +// + +// Updates the value associated with the given key. If the key was not already +// present, then the key-value pair are inserted and "previous" is unchanged. If +// the key was already present, the value is updated and "*previous" will +// contain a copy of the old value. +// +// InsertOrReturnExisting has complementary behavior that returns the +// address of an already existing value, rather than updating it. +template <class Collection> +bool UpdateReturnCopy(Collection* const collection, + const typename Collection::value_type::first_type& key, + const typename Collection::value_type::second_type& value, + typename Collection::value_type::second_type* previous) { + std::pair<typename Collection::iterator, bool> ret = + collection->insert(typename Collection::value_type(key, value)); + if (!ret.second) { + // update + if (previous) { + *previous = ret.first->second; + } + ret.first->second = value; + return true; + } + return false; +} + +// Same as above except that the key and value are passed as a pair. +template <class Collection> +bool UpdateReturnCopy(Collection* const collection, + const typename Collection::value_type& vt, + typename Collection::value_type::second_type* previous) { + std::pair<typename Collection::iterator, bool> ret = collection->insert(vt); + if (!ret.second) { + // update + if (previous) { + *previous = ret.first->second; + } + ret.first->second = vt.second; + return true; + } + return false; +} + +// Tries to insert the given key-value pair into the collection. Returns NULL if +// the insert succeeds. Otherwise, returns a pointer to the existing value. +// +// This complements UpdateReturnCopy in that it allows to update only after +// verifying the old value and still insert quickly without having to look up +// twice. Unlike UpdateReturnCopy this also does not come with the issue of an +// undefined previous* in case new data was inserted. +template <class Collection> +typename Collection::value_type::second_type* const +InsertOrReturnExisting(Collection* const collection, + const typename Collection::value_type& vt) { + std::pair<typename Collection::iterator, bool> ret = collection->insert(vt); + if (ret.second) { + return NULL; // Inserted, no existing previous value. + } else { + return &ret.first->second; // Return address of already existing value. + } +} + +// Same as above, except for explicit key and data. +template <class Collection> +typename Collection::value_type::second_type* const +InsertOrReturnExisting( + Collection* const collection, + const typename Collection::value_type::first_type& key, + const typename Collection::value_type::second_type& data) { + return InsertOrReturnExisting(collection, + typename Collection::value_type(key, data)); +} + +// Erases the collection item identified by the given key, and returns the value +// associated with that key. It is assumed that the value (i.e., the +// mapped_type) is a pointer. Returns NULL if the key was not found in the +// collection. +// +// Examples: +// map<string, MyType*> my_map; +// +// One line cleanup: +// delete EraseKeyReturnValuePtr(&my_map, "abc"); +// +// Use returned value: +// scoped_ptr<MyType> value_ptr(EraseKeyReturnValuePtr(&my_map, "abc")); +// if (value_ptr.get()) +// value_ptr->DoSomething(); +// +template <class Collection> +typename Collection::value_type::second_type EraseKeyReturnValuePtr( + Collection* const collection, + const typename Collection::value_type::first_type& key) { + typename Collection::iterator it = collection->find(key); + if (it == collection->end()) { + return NULL; + } + typename Collection::value_type::second_type v = it->second; + collection->erase(it); + return v; +} + +// Inserts all the keys from map_container into key_container, which must +// support insert(MapContainer::key_type). +// +// Note: any initial contents of the key_container are not cleared. +template <class MapContainer, class KeyContainer> +void InsertKeysFromMap(const MapContainer& map_container, + KeyContainer* key_container) { + GOOGLE_CHECK(key_container != NULL); + for (typename MapContainer::const_iterator it = map_container.begin(); + it != map_container.end(); ++it) { + key_container->insert(it->first); + } +} + +// Appends all the keys from map_container into key_container, which must +// support push_back(MapContainer::key_type). +// +// Note: any initial contents of the key_container are not cleared. +template <class MapContainer, class KeyContainer> +void AppendKeysFromMap(const MapContainer& map_container, + KeyContainer* key_container) { + GOOGLE_CHECK(key_container != NULL); + for (typename MapContainer::const_iterator it = map_container.begin(); + it != map_container.end(); ++it) { + key_container->push_back(it->first); + } +} + +// A more specialized overload of AppendKeysFromMap to optimize reallocations +// for the common case in which we're appending keys to a vector and hence can +// (and sometimes should) call reserve() first. +// +// (It would be possible to play SFINAE games to call reserve() for any +// container that supports it, but this seems to get us 99% of what we need +// without the complexity of a SFINAE-based solution.) +template <class MapContainer, class KeyType> +void AppendKeysFromMap(const MapContainer& map_container, + vector<KeyType>* key_container) { + GOOGLE_CHECK(key_container != NULL); + // We now have the opportunity to call reserve(). Calling reserve() every + // time is a bad idea for some use cases: libstdc++'s implementation of + // vector<>::reserve() resizes the vector's backing store to exactly the + // given size (unless it's already at least that big). Because of this, + // the use case that involves appending a lot of small maps (total size + // N) one by one to a vector would be O(N^2). But never calling reserve() + // loses the opportunity to improve the use case of adding from a large + // map to an empty vector (this improves performance by up to 33%). A + // number of heuristics are possible; see the discussion in + // cl/34081696. Here we use the simplest one. + if (key_container->empty()) { + key_container->reserve(map_container.size()); + } + for (typename MapContainer::const_iterator it = map_container.begin(); + it != map_container.end(); ++it) { + key_container->push_back(it->first); + } +} + +// Inserts all the values from map_container into value_container, which must +// support push_back(MapContainer::mapped_type). +// +// Note: any initial contents of the value_container are not cleared. +template <class MapContainer, class ValueContainer> +void AppendValuesFromMap(const MapContainer& map_container, + ValueContainer* value_container) { + GOOGLE_CHECK(value_container != NULL); + for (typename MapContainer::const_iterator it = map_container.begin(); + it != map_container.end(); ++it) { + value_container->push_back(it->second); + } +} + +// A more specialized overload of AppendValuesFromMap to optimize reallocations +// for the common case in which we're appending values to a vector and hence +// can (and sometimes should) call reserve() first. +// +// (It would be possible to play SFINAE games to call reserve() for any +// container that supports it, but this seems to get us 99% of what we need +// without the complexity of a SFINAE-based solution.) +template <class MapContainer, class ValueType> +void AppendValuesFromMap(const MapContainer& map_container, + vector<ValueType>* value_container) { + GOOGLE_CHECK(value_container != NULL); + // See AppendKeysFromMap for why this is done. + if (value_container->empty()) { + value_container->reserve(map_container.size()); + } + for (typename MapContainer::const_iterator it = map_container.begin(); + it != map_container.end(); ++it) { + value_container->push_back(it->second); + } +} + +} // namespace protobuf +} // namespace google + +#endif // GOOGLE_PROTOBUF_STUBS_MAP_UTIL_H__ |