Update third_party/protobuf to protobuf-v3.0.0-beta-3

third_party/protobuf/src/google/protobuf/map.h

Index: third_party/protobuf/src/google/protobuf/map.h
diff --git a/third_party/protobuf/src/google/protobuf/map.h b/third_party/protobuf/src/google/protobuf/map.h
index 83199380bffb732c2a6b74b2f5d893d7dc2f92e6..6f1a71e4364e4dae1aae09f6ce6782ca110598bd 100644
--- a/third_party/protobuf/src/google/protobuf/map.h
+++ b/third_party/protobuf/src/google/protobuf/map.h
@@ -31,9 +31,11 @@
 #ifndef GOOGLE_PROTOBUF_MAP_H__
 #define GOOGLE_PROTOBUF_MAP_H__
 
-#include <iterator>
 #include <google/protobuf/stubs/hash.h>
+#include <iterator>
 #include <limits>  // To support Visual Studio 2008
+#include <set>
+#include <utility>
 
 #include <google/protobuf/stubs/common.h>
 #include <google/protobuf/arena.h>
@@ -41,17 +43,23 @@
 #include <google/protobuf/map_type_handler.h>
 #include <google/protobuf/message.h>
 #include <google/protobuf/descriptor.h>
+#if __cpp_exceptions && LANG_CXX11
+#include <random>
+#endif
 
 namespace google {
 namespace protobuf {
 
+// The Map and MapIterator types are provided by this header file.
+// Please avoid using other types defined here, unless they are public
+// types within Map or MapIterator, such as Map::value_type.
 template <typename Key, typename T>
 class Map;
 
-template <typename Enum> struct is_proto_enum;
-
 class MapIterator;
 
+template <typename Enum> struct is_proto_enum;
+
 namespace internal {
 template <typename Key, typename T,
           WireFormatLite::FieldType key_wire_type,
@@ -73,15 +81,15 @@ class DynamicMapField;
 class GeneratedMessageReflection;
 }  // namespace internal
 
-#define TYPE_CHECK(EXPECTEDTYPE, METHOD)                                \
-  if (type() != EXPECTEDTYPE) {                                         \
-    GOOGLE_LOG(FATAL)                                                          \
-        << "Protocol Buffer map usage error:\n"                         \
-        << METHOD << " type does not match\n"                           \
-        << "  Expected : "                                              \
-        << FieldDescriptor::CppTypeName(EXPECTEDTYPE) << "\n"           \
-        << "  Actual   : "                                              \
-        << FieldDescriptor::CppTypeName(type());                        \
+#define TYPE_CHECK(EXPECTEDTYPE, METHOD)                        \
+  if (type() != EXPECTEDTYPE) {                                 \
+    GOOGLE_LOG(FATAL)                                                  \
+        << "Protocol Buffer map usage error:\n"                 \
+        << METHOD << " type does not match\n"                   \
+        << "  Expected : "                                      \
+        << FieldDescriptor::CppTypeName(EXPECTEDTYPE) << "\n"   \
+        << "  Actual   : "                                      \
+        << FieldDescriptor::CppTypeName(type());                \
   }
 
 // MapKey is an union type for representing any possible
@@ -166,11 +174,47 @@ class LIBPROTOBUF_EXPORT MapKey {
     return *val_.string_value_;
   }
 
+  bool operator<(const MapKey& other) const {
+    if (type_ != other.type_) {
+      // We could define a total order that handles this case, but
+      // there currently no need.  So, for now, fail.
+      GOOGLE_LOG(FATAL) << "Unsupported: type mismatch";
+    }
+    switch (type()) {
+      case FieldDescriptor::CPPTYPE_DOUBLE:
+      case FieldDescriptor::CPPTYPE_FLOAT:
+      case FieldDescriptor::CPPTYPE_ENUM:
+      case FieldDescriptor::CPPTYPE_MESSAGE:
+        GOOGLE_LOG(FATAL) << "Unsupported";
+        return false;
+      case FieldDescriptor::CPPTYPE_STRING:
+        return *val_.string_value_ < *other.val_.string_value_;
+      case FieldDescriptor::CPPTYPE_INT64:
+        return val_.int64_value_ < other.val_.int64_value_;
+      case FieldDescriptor::CPPTYPE_INT32:
+        return val_.int32_value_ < other.val_.int32_value_;
+      case FieldDescriptor::CPPTYPE_UINT64:
+        return val_.uint64_value_ < other.val_.uint64_value_;
+      case FieldDescriptor::CPPTYPE_UINT32:
+        return val_.uint32_value_ < other.val_.uint32_value_;
+      case FieldDescriptor::CPPTYPE_BOOL:
+        return val_.bool_value_ < other.val_.bool_value_;
+    }
+    return false;
+  }
+
   bool operator==(const MapKey& other) const {
     if (type_ != other.type_) {
-      return false;
+      // To be consistent with operator<, we don't allow this either.
+      GOOGLE_LOG(FATAL) << "Unsupported: type mismatch";
     }
     switch (type()) {
+      case FieldDescriptor::CPPTYPE_DOUBLE:
+      case FieldDescriptor::CPPTYPE_FLOAT:
+      case FieldDescriptor::CPPTYPE_ENUM:
+      case FieldDescriptor::CPPTYPE_MESSAGE:
+        GOOGLE_LOG(FATAL) << "Unsupported";
+        break;
       case FieldDescriptor::CPPTYPE_STRING:
         return *val_.string_value_ == *other.val_.string_value_;
       case FieldDescriptor::CPPTYPE_INT64:
@@ -183,11 +227,6 @@ class LIBPROTOBUF_EXPORT MapKey {
         return val_.uint32_value_ == other.val_.uint32_value_;
       case FieldDescriptor::CPPTYPE_BOOL:
         return val_.bool_value_ == other.val_.bool_value_;
-      case FieldDescriptor::CPPTYPE_DOUBLE:
-      case FieldDescriptor::CPPTYPE_FLOAT:
-      case FieldDescriptor::CPPTYPE_ENUM:
-      case FieldDescriptor::CPPTYPE_MESSAGE:
-        GOOGLE_LOG(FATAL) << "Can't get here.";
     }
     GOOGLE_LOG(FATAL) << "Can't get here.";
     return false;
@@ -196,6 +235,12 @@ class LIBPROTOBUF_EXPORT MapKey {
   void CopyFrom(const MapKey& other) {
     SetType(other.type());
     switch (type_) {
+      case FieldDescriptor::CPPTYPE_DOUBLE:
+      case FieldDescriptor::CPPTYPE_FLOAT:
+      case FieldDescriptor::CPPTYPE_ENUM:
+      case FieldDescriptor::CPPTYPE_MESSAGE:
+        GOOGLE_LOG(FATAL) << "Unsupported";
+        break;
       case FieldDescriptor::CPPTYPE_STRING:
         *val_.string_value_ = *other.val_.string_value_;
         break;
@@ -214,12 +259,6 @@ class LIBPROTOBUF_EXPORT MapKey {
       case FieldDescriptor::CPPTYPE_BOOL:
         val_.bool_value_ = other.val_.bool_value_;
         break;
-      case FieldDescriptor::CPPTYPE_DOUBLE:
-      case FieldDescriptor::CPPTYPE_FLOAT:
-      case FieldDescriptor::CPPTYPE_ENUM:
-      case FieldDescriptor::CPPTYPE_MESSAGE:
-        GOOGLE_LOG(FATAL) << "Can't get here.";
-        break;
     }
   }
 
@@ -457,8 +496,15 @@ class MapPair {
 };
 
 // google::protobuf::Map is an associative container type used to store protobuf map
-// fields. Its interface is similar to std::unordered_map. Users should use this
-// interface directly to visit or change map fields.
+// fields.  Each Map instance may or may not use a different hash function, a
+// different iteration order, and so on.  E.g., please don't examine
+// implementation details to decide if the following would work:
+//  Map<int, int> m0, m1;
+//  m0[0] = m1[0] = m0[1] = m1[1] = 0;
+//  assert(m0.begin()->first == m1.begin()->first);  // Bug!
+//
+// Map's interface is similar to std::unordered_map, except that Map is not
+// designed to play well with exceptions.
 template <typename Key, typename T>
 class Map {
  public:
@@ -473,40 +519,56 @@ class Map {
 
   typedef size_t size_type;
   typedef hash<Key> hasher;
-  typedef equal_to<Key> key_equal;
 
-  Map()
+  Map(bool old_style = true)
       : arena_(NULL),
-        allocator_(arena_),
-        elements_(0, hasher(), key_equal(), allocator_),
-        default_enum_value_(0) {}
-  explicit Map(Arena* arena)
+        default_enum_value_(0),
+        old_style_(old_style) {
+    Init();
+  }
+  explicit Map(Arena* arena, bool old_style = true)
       : arena_(arena),
-        allocator_(arena_),
-        elements_(0, hasher(), key_equal(), allocator_),
-        default_enum_value_(0) {
-    arena_->OwnDestructor(&elements_);
+        default_enum_value_(0),
+        old_style_(old_style) {
+    Init();
   }
-
   Map(const Map& other)
       : arena_(NULL),
-        allocator_(arena_),
-        elements_(0, hasher(), key_equal(), allocator_),
-        default_enum_value_(other.default_enum_value_) {
+        default_enum_value_(other.default_enum_value_),
+        old_style_(other.old_style_) {
+    Init();
     insert(other.begin(), other.end());
   }
   template <class InputIt>
-  Map(const InputIt& first, const InputIt& last)
+  Map(const InputIt& first, const InputIt& last, bool old_style = true)
       : arena_(NULL),
-        allocator_(arena_),
-        elements_(0, hasher(), key_equal(), allocator_),
-        default_enum_value_(0) {
+        default_enum_value_(0),
+        old_style_(old_style) {
+    Init();
     insert(first, last);
   }
 
-  ~Map() { clear(); }
+  ~Map() {
+    clear();
+    if (arena_ == NULL) {
+      if (old_style_)
+        delete deprecated_elements_;
+      else
+        delete elements_;
+    }
+  }
 
  private:
+  void Init() {
+    if (old_style_)
+      deprecated_elements_ = Arena::Create<DeprecatedInnerMap>(
+          arena_, 0, hasher(), equal_to<Key>(),
+          MapAllocator<std::pair<const Key, MapPair<Key, T>*> >(arena_));
+    else
+      elements_ =
+          Arena::Create<InnerMap>(arena_, 0, hasher(), Allocator(arena_));
+  }
+
   // re-implement std::allocator to use arena allocator for memory allocation.
   // Used for google::protobuf::Map implementation. Users should not use this class
   // directly.
@@ -550,11 +612,12 @@ class Map {
     !defined(GOOGLE_PROTOBUF_OS_EMSCRIPTEN)
     template<class NodeType, class... Args>
     void construct(NodeType* p, Args&&... args) {
-      // Clang 3.6 doesn't compile static casting to void* directly. (Issue #1266)
-      // According C++ standard 5.2.9/1: "The static_cast operator shall not cast
-      // away constness". So first the maybe const pointer is casted to const void* and
-      // after the const void* is const casted.
-      new (const_cast<void*>(static_cast<const void*>(p))) NodeType(std::forward<Args>(args)...);
+      // Clang 3.6 doesn't compile static casting to void* directly. (Issue
+      // #1266) According C++ standard 5.2.9/1: "The static_cast operator shall
+      // not cast away constness". So first the maybe const pointer is casted to
+      // const void* and after the const void* is const casted.
+      new (const_cast<void*>(static_cast<const void*>(p)))
+          NodeType(std::forward<Args>(args)...);
     }
 
     template<class NodeType>
@@ -595,86 +658,849 @@ class Map {
     friend class MapAllocator;
   };
 
-  typedef MapAllocator<std::pair<const Key, MapPair<Key, T>*> > Allocator;
-  typedef hash_map<Key, value_type*, hash<Key>, equal_to<Key>, Allocator>
-      InnerMap;
+  // InnerMap's key type is Key and its value type is value_type*.  We use a
+  // custom class here and for Node, below, to ensure that k_ is at offset 0,
+  // allowing safe conversion from pointer to Node to pointer to Key, and vice
+  // versa when appropriate.
+  class KeyValuePair {
+   public:
+    KeyValuePair(const Key& k, value_type* v) : k_(k), v_(v) {}
+
+    const Key& key() const { return k_; }
+    Key& key() { return k_; }
+    value_type* const value() const { return v_; }
+    value_type*& value() { return v_; }
+
+   private:
+    Key k_;
+    value_type* v_;
+  };
+
+  typedef MapAllocator<KeyValuePair> Allocator;
+
+  // InnerMap is a generic hash-based map.  It doesn't contain any
+  // protocol-buffer-specific logic.  It is a chaining hash map with the
+  // additional feature that some buckets can be converted to use an ordered
+  // container.  This ensures O(lg n) bounds on find, insert, and erase, while
+  // avoiding the overheads of ordered containers most of the time.
+  //
+  // The implementation doesn't need the full generality of unordered_map,
+  // and it doesn't have it.  More bells and whistles can be added as needed.
+  // Some implementation details:
+  // 1. The hash function has type hasher and the equality function
+  //    equal_to<Key>.  We inherit from hasher to save space
+  //    (empty-base-class optimization).
+  // 2. The number of buckets is a power of two.
+  // 3. Buckets are converted to trees in pairs: if we convert bucket b then
+  //    buckets b and b^1 will share a tree.  Invariant: buckets b and b^1 have
+  //    the same non-NULL value iff they are sharing a tree.  (An alternative
+  //    implementation strategy would be to have a tag bit per bucket.)
+  // 4. As is typical for hash_map and such, the Keys and Values are always
+  //    stored in linked list nodes.  Pointers to elements are never invalidated
+  //    until the element is deleted.
+  // 5. The trees' payload type is pointer to linked-list node.  Tree-converting
+  //    a bucket doesn't copy Key-Value pairs.
+  // 6. Once we've tree-converted a bucket, it is never converted back. However,
+  //    the items a tree contains may wind up assigned to trees or lists upon a
+  //    rehash.
+  // 7. The code requires no C++ features from C++11 or later.
+  // 8. Mutations to a map do not invalidate the map's iterators, pointers to
+  //    elements, or references to elements.
+  // 9. Except for erase(iterator), any non-const method can reorder iterators.
+  class InnerMap : private hasher {
+   public:
+    typedef value_type* Value;
+
+    InnerMap(size_type n, hasher h, Allocator alloc)
+        : hasher(h),
+          num_elements_(0),
+          seed_(Seed()),
+          table_(NULL),
+          alloc_(alloc) {
+      n = TableSize(n);
+      table_ = CreateEmptyTable(n);
+      num_buckets_ = index_of_first_non_null_ = n;
+    }
+
+    ~InnerMap() {
+      if (table_ != NULL) {
+        clear();
+        Dealloc<void*>(table_, num_buckets_);
+      }
+    }
+
+   private:
+    enum { kMinTableSize = 8 };
+
+    // Linked-list nodes, as one would expect for a chaining hash table.
+    struct Node {
+      KeyValuePair kv;
+      Node* next;
+    };
+
+    // This is safe only if the given pointer is known to point to a Key that is
+    // part of a Node.
+    static Node* NodePtrFromKeyPtr(Key* k) {
+      return reinterpret_cast<Node*>(k);
+    }
+
+    static Key* KeyPtrFromNodePtr(Node* node) { return &node->kv.key(); }
+
+    // Trees.  The payload type is pointer to Key, so that we can query the tree
+    // with Keys that are not in any particular data structure.  When we insert,
+    // though, the pointer is always pointing to a Key that is inside a Node.
+    struct KeyCompare {
+      bool operator()(const Key* n0, const Key* n1) const { return *n0 < *n1; }
+    };
+    typedef typename Allocator::template rebind<Key*>::other KeyPtrAllocator;
+    typedef std::set<Key*, KeyCompare, KeyPtrAllocator> Tree;
+
+    // iterator and const_iterator are instantiations of iterator_base.
+    template <typename KeyValueType>
+    class iterator_base {
+     public:
+      typedef KeyValueType& reference;
+      typedef KeyValueType* pointer;
+      typedef typename Tree::iterator TreeIterator;
+
+      // Invariants:
+      // node_ is always correct. This is handy because the most common
+      // operations are operator* and operator-> and they only use node_.
+      // When node_ is set to a non-NULL value, all the other non-const fields
+      // are updated to be correct also, but those fields can become stale
+      // if the underlying map is modified.  When those fields are needed they
+      // are rechecked, and updated if necessary.
+      iterator_base() : node_(NULL) {}
+
+      explicit iterator_base(const InnerMap* m) : m_(m) {
+        SearchFrom(m->index_of_first_non_null_);
+      }
+
+      // Any iterator_base can convert to any other.  This is overkill, and we
+      // rely on the enclosing class to use it wisely.  The standard "iterator
+      // can convert to const_iterator" is OK but the reverse direction is not.
+      template <typename U>
+      explicit iterator_base(const iterator_base<U>& it)
+          : node_(it.node_),
+            m_(it.m_),
+            bucket_index_(it.bucket_index_),
+            tree_it_(it.tree_it_) {}
+
+      iterator_base(Node* n, const InnerMap* m, size_type index)
+          : node_(n),
+            m_(m),
+            bucket_index_(index) {}
+
+      iterator_base(TreeIterator tree_it, const InnerMap* m, size_type index)
+          : node_(NodePtrFromKeyPtr(*tree_it)),
+            m_(m),
+            bucket_index_(index),
+            tree_it_(tree_it) {
+        // Invariant: iterators that use tree_it_ have an even bucket_index_.
+        GOOGLE_DCHECK_EQ(bucket_index_ % 2, 0);
+      }
+
+      // Advance through buckets, looking for the first that isn't empty.
+      // If nothing non-empty is found then leave node_ == NULL.
+      void SearchFrom(size_type start_bucket) {
+        GOOGLE_DCHECK(m_->index_of_first_non_null_ == m_->num_buckets_ ||
+               m_->table_[m_->index_of_first_non_null_] != NULL);
+        node_ = NULL;
+        for (bucket_index_ = start_bucket; bucket_index_ < m_->num_buckets_;
+             bucket_index_++) {
+          if (m_->TableEntryIsNonEmptyList(bucket_index_)) {
+            node_ = static_cast<Node*>(m_->table_[bucket_index_]);
+            break;
+          } else if (m_->TableEntryIsTree(bucket_index_)) {
+            Tree* tree = static_cast<Tree*>(m_->table_[bucket_index_]);
+            GOOGLE_DCHECK(!tree->empty());
+            tree_it_ = tree->begin();
+            node_ = NodePtrFromKeyPtr(*tree_it_);
+            break;
+          }
+        }
+      }
+
+      reference operator*() const { return node_->kv; }
+      pointer operator->() const { return &(operator*()); }
+
+      friend bool operator==(const iterator_base& a, const iterator_base& b) {
+        return a.node_ == b.node_;
+      }
+      friend bool operator!=(const iterator_base& a, const iterator_base& b) {
+        return a.node_ != b.node_;
+      }
+
+      iterator_base& operator++() {
+        if (node_->next == NULL) {
+          const bool is_list = revalidate_if_necessary();
+          if (is_list) {
+            SearchFrom(bucket_index_ + 1);
+          } else {
+            GOOGLE_DCHECK_EQ(bucket_index_ & 1, 0);
+            Tree* tree = static_cast<Tree*>(m_->table_[bucket_index_]);
+            if (++tree_it_ == tree->end()) {
+              SearchFrom(bucket_index_ + 2);
+            } else {
+              node_ = NodePtrFromKeyPtr(*tree_it_);
+            }
+          }
+        } else {
+          node_ = node_->next;
+        }
+        return *this;
+      }
+
+      iterator_base operator++(int /* unused */) {
+        iterator_base tmp = *this;
+        ++*this;
+        return tmp;
+      }
+
+      // Assumes node_ and m_ are correct and non-NULL, but other fields may be
+      // stale.  Fix them as needed.  Then return true iff node_ points to a
+      // Node in a list.
+      bool revalidate_if_necessary() {
+        GOOGLE_DCHECK(node_ != NULL && m_ != NULL);
+        // Force bucket_index_ to be in range.
+        bucket_index_ &= (m_->num_buckets_ - 1);
+        // Common case: the bucket we think is relevant points to node_.
+        if (m_->table_[bucket_index_] == static_cast<void*>(node_))
+          return true;
+        // Less common: the bucket is a linked list with node_ somewhere in it,
+        // but not at the head.
+        if (m_->TableEntryIsNonEmptyList(bucket_index_)) {
+          Node* l = static_cast<Node*>(m_->table_[bucket_index_]);
+          while ((l = l->next) != NULL) {
+            if (l == node_) {
+              return true;
+            }
+          }
+        }
+        // Well, bucket_index_ still might be correct, but probably
+        // not.  Revalidate just to be sure.  This case is rare enough that we
+        // don't worry about potential optimizations, such as having a custom
+        // find-like method that compares Node* instead of const Key&.
+        iterator_base i(m_->find(*KeyPtrFromNodePtr(node_)));
+        bucket_index_ = i.bucket_index_;
+        tree_it_ = i.tree_it_;
+        return m_->TableEntryIsList(bucket_index_);
+      }
+
+      Node* node_;
+      const InnerMap* m_;
+      size_type bucket_index_;
+      TreeIterator tree_it_;
+    };
+
+   public:
+    typedef iterator_base<KeyValuePair> iterator;
+    typedef iterator_base<const KeyValuePair> const_iterator;
+
+    iterator begin() { return iterator(this); }
+    iterator end() { return iterator(); }
+    const_iterator begin() const { return const_iterator(this); }
+    const_iterator end() const { return const_iterator(); }
+
+    void clear() {
+      for (size_type b = 0; b < num_buckets_; b++) {
+        if (TableEntryIsNonEmptyList(b)) {
+          Node* node = static_cast<Node*>(table_[b]);
+          table_[b] = NULL;
+          do {
+            Node* next = node->next;
+            DestroyNode(node);
+            node = next;
+          } while (node != NULL);
+        } else if (TableEntryIsTree(b)) {
+          Tree* tree = static_cast<Tree*>(table_[b]);
+          GOOGLE_DCHECK(table_[b] == table_[b + 1] && (b & 1) == 0);
+          table_[b] = table_[b + 1] = NULL;
+          typename Tree::iterator tree_it = tree->begin();
+          do {
+            Node* node = NodePtrFromKeyPtr(*tree_it);
+            typename Tree::iterator next = tree_it;
+            ++next;
+            tree->erase(tree_it);
+            DestroyNode(node);
+            tree_it = next;
+          } while (tree_it != tree->end());
+          DestroyTree(tree);
+          b++;
+        }
+      }
+      num_elements_ = 0;
+      index_of_first_non_null_ = num_buckets_;
+    }
+
+    const hasher& hash_function() const { return *this; }
+
+    static size_type max_size() {
+      return static_cast<size_type>(1) << (sizeof(void**) >= 8 ? 60 : 28);
+    }
+    size_type size() const { return num_elements_; }
+    bool empty() const { return size() == 0; }
+
+    iterator find(const Key& k) { return iterator(FindHelper(k).first); }
+    const_iterator find(const Key& k) const { return FindHelper(k).first; }
+
+    // In traditional C++ style, this performs "insert if not present."
+    std::pair<iterator, bool> insert(const KeyValuePair& kv) {
+      std::pair<const_iterator, size_type> p = FindHelper(kv.key());
+      // Case 1: key was already present.
+      if (p.first.node_ != NULL)
+        return std::make_pair(iterator(p.first), false);
+      // Case 2: insert.
+      if (ResizeIfLoadIsOutOfRange(num_elements_ + 1)) {
+        p = FindHelper(kv.key());
+      }
+      const size_type b = p.second;  // bucket number
+      Node* node = Alloc<Node>(1);
+      alloc_.construct(&node->kv, kv);
+      iterator result = InsertUnique(b, node);
+      ++num_elements_;
+      return std::make_pair(result, true);
+    }
+
+    // The same, but if an insertion is necessary then the value portion of the
+    // inserted key-value pair is left uninitialized.
+    std::pair<iterator, bool> insert(const Key& k) {
+      std::pair<const_iterator, size_type> p = FindHelper(k);
+      // Case 1: key was already present.
+      if (p.first.node_ != NULL)
+        return std::make_pair(iterator(p.first), false);
+      // Case 2: insert.
+      if (ResizeIfLoadIsOutOfRange(num_elements_ + 1)) {
+        p = FindHelper(k);
+      }
+      const size_type b = p.second;  // bucket number
+      Node* node = Alloc<Node>(1);
+      typedef typename Allocator::template rebind<Key>::other KeyAllocator;
+      KeyAllocator(alloc_).construct(&node->kv.key(), k);
+      iterator result = InsertUnique(b, node);
+      ++num_elements_;
+      return std::make_pair(result, true);
+    }
+
+    Value& operator[](const Key& k) {
+      KeyValuePair kv(k, Value());
+      return insert(kv).first->value();
+    }
+
+    void erase(iterator it) {
+      GOOGLE_DCHECK_EQ(it.m_, this);
+      const bool is_list = it.revalidate_if_necessary();
+      size_type b = it.bucket_index_;
+      Node* const item = it.node_;
+      if (is_list) {
+        GOOGLE_DCHECK(TableEntryIsNonEmptyList(b));
+        Node* head = static_cast<Node*>(table_[b]);
+        head = EraseFromLinkedList(item, head);
+        table_[b] = static_cast<void*>(head);
+      } else {
+        GOOGLE_DCHECK(TableEntryIsTree(b));
+        Tree* tree = static_cast<Tree*>(table_[b]);
+        tree->erase(it.tree_it_);
+        if (tree->empty()) {
+          // Force b to be the minimum of b and b ^ 1.  This is important
+          // only because we want index_of_first_non_null_ to be correct.
+          b &= ~static_cast<size_type>(1);
+          DestroyTree(tree);
+          table_[b] = table_[b + 1] = NULL;
+        }
+      }
+      DestroyNode(item);
+      --num_elements_;
+      if (GOOGLE_PREDICT_FALSE(b == index_of_first_non_null_)) {
+        while (index_of_first_non_null_ < num_buckets_ &&
+               table_[index_of_first_non_null_] == NULL) {
+          ++index_of_first_non_null_;
+        }
+      }
+    }
+
+   private:
+    std::pair<const_iterator, size_type> FindHelper(const Key& k) const {
+      size_type b = BucketNumber(k);
+      if (TableEntryIsNonEmptyList(b)) {
+        Node* node = static_cast<Node*>(table_[b]);
+        do {
+          if (IsMatch(*KeyPtrFromNodePtr(node), k)) {
+            return std::make_pair(const_iterator(node, this, b), b);
+          } else {
+            node = node->next;
+          }
+        } while (node != NULL);
+      } else if (TableEntryIsTree(b)) {
+        GOOGLE_DCHECK_EQ(table_[b], table_[b ^ 1]);
+        b &= ~static_cast<size_t>(1);
+        Tree* tree = static_cast<Tree*>(table_[b]);
+        Key* key = const_cast<Key*>(&k);
+        typename Tree::iterator tree_it = tree->find(key);
+        if (tree_it != tree->end()) {
+          return std::make_pair(const_iterator(tree_it, this, b), b);
+        }
+      }
+      return std::make_pair(end(), b);
+    }
+
+    // Insert the given Node in bucket b.  If that would make bucket b too big,
+    // and bucket b is not a tree, create a tree for buckets b and b^1 to share.
+    // Requires count(*KeyPtrFromNodePtr(node)) == 0 and that b is the correct
+    // bucket.  num_elements_ is not modified.
+    iterator InsertUnique(size_type b, Node* node) {
+      GOOGLE_DCHECK(index_of_first_non_null_ == num_buckets_ ||
+             table_[index_of_first_non_null_] != NULL);
+      // In practice, the code that led to this point may have already
+      // determined whether we are inserting into an empty list, a short list,
+      // or whatever.  But it's probably cheap enough to recompute that here;
+      // it's likely that we're inserting into an empty or short list.
+      iterator result;
+      GOOGLE_DCHECK(find(*KeyPtrFromNodePtr(node)) == end());
+      if (TableEntryIsEmpty(b)) {
+        result = InsertUniqueInList(b, node);
+      } else if (TableEntryIsNonEmptyList(b)) {
+        if (GOOGLE_PREDICT_FALSE(TableEntryIsTooLong(b))) {
+          TreeConvert(b);
+          result = InsertUniqueInTree(b, node);
+          GOOGLE_DCHECK_EQ(result.bucket_index_, b & ~static_cast<size_type>(1));
+        } else {
+          // Insert into a pre-existing list.  This case cannot modify
+          // index_of_first_non_null_, so we skip the code to update it.
+          return InsertUniqueInList(b, node);
+        }
+      } else {
+        // Insert into a pre-existing tree.  This case cannot modify
+        // index_of_first_non_null_, so we skip the code to update it.
+        return InsertUniqueInTree(b, node);
+      }
+      index_of_first_non_null_ =
+          std::min(index_of_first_non_null_, result.bucket_index_);
+      return result;
+    }
+
+    // Helper for InsertUnique.  Handles the case where bucket b is a
+    // not-too-long linked list.
+    iterator InsertUniqueInList(size_type b, Node* node) {
+      node->next = static_cast<Node*>(table_[b]);
+      table_[b] = static_cast<void*>(node);
+      return iterator(node, this, b);
+    }
+
+    // Helper for InsertUnique.  Handles the case where bucket b points to a
+    // Tree.
+    iterator InsertUniqueInTree(size_type b, Node* node) {
+      GOOGLE_DCHECK_EQ(table_[b], table_[b ^ 1]);
+      // Maintain the invariant that node->next is NULL for all Nodes in Trees.
+      node->next = NULL;
+      return iterator(static_cast<Tree*>(table_[b])
+                      ->insert(KeyPtrFromNodePtr(node))
+                      .first,
+                      this, b & ~static_cast<size_t>(1));
+    }
+
+    // Returns whether it did resize.  Currently this is only used when
+    // num_elements_ increases, though it could be used in other situations.
+    // It checks for load too low as well as load too high: because any number
+    // of erases can occur between inserts, the load could be as low as 0 here.
+    // Resizing to a lower size is not always helpful, but failing to do so can
+    // destroy the expected big-O bounds for some operations. By having the
+    // policy that sometimes we resize down as well as up, clients can easily
+    // keep O(size()) = O(number of buckets) if they want that.
+    bool ResizeIfLoadIsOutOfRange(size_type new_size) {
+      const size_type kMaxMapLoadTimes16 = 12;  // controls RAM vs CPU tradeoff
+      const size_type hi_cutoff = num_buckets_ * kMaxMapLoadTimes16 / 16;
+      const size_type lo_cutoff = hi_cutoff / 4;
+      // We don't care how many elements are in trees.  If a lot are,
+      // we may resize even though there are many empty buckets.  In
+      // practice, this seems fine.
+      if (GOOGLE_PREDICT_FALSE(new_size >= hi_cutoff)) {
+        if (num_buckets_ <= max_size() / 2) {
+          Resize(num_buckets_ * 2);
+          return true;
+        }
+      } else if (GOOGLE_PREDICT_FALSE(new_size <= lo_cutoff &&
+                               num_buckets_ > kMinTableSize)) {
+        size_type lg2_of_size_reduction_factor = 1;
+        // It's possible we want to shrink a lot here... size() could even be 0.
+        // So, estimate how much to shrink by making sure we don't shrink so
+        // much that we would need to grow the table after a few inserts.
+        const size_type hypothetical_size = new_size * 5 / 4 + 1;
+        while ((hypothetical_size << lg2_of_size_reduction_factor) <
+               hi_cutoff) {
+          ++lg2_of_size_reduction_factor;
+        }
+        size_type new_num_buckets = std::max<size_type>(
+            kMinTableSize, num_buckets_ >> lg2_of_size_reduction_factor);
+        if (new_num_buckets != num_buckets_) {
+          Resize(new_num_buckets);
+          return true;
+        }
+      }
+      return false;
+    }
+
+    // Resize to the given number of buckets.
+    void Resize(size_t new_num_buckets) {
+      GOOGLE_DCHECK_GE(new_num_buckets, kMinTableSize);
+      void** const old_table = table_;
+      const size_type old_table_size = num_buckets_;
+      num_buckets_ = new_num_buckets;
+      table_ = CreateEmptyTable(num_buckets_);
+      const size_type start = index_of_first_non_null_;
+      index_of_first_non_null_ = num_buckets_;
+      for (size_type i = start; i < old_table_size; i++) {
+        if (TableEntryIsNonEmptyList(old_table, i)) {
+          TransferList(old_table, i);
+        } else if (TableEntryIsTree(old_table, i)) {
+          TransferTree(old_table, i++);
+        }
+      }
+      Dealloc<void*>(old_table, old_table_size);
+    }
+
+    void TransferList(void* const* table, size_type index) {
+      Node* node = static_cast<Node*>(table[index]);
+      do {
+        Node* next = node->next;
+        InsertUnique(BucketNumber(*KeyPtrFromNodePtr(node)), node);
+        node = next;
+      } while (node != NULL);
+    }
+
+    void TransferTree(void* const* table, size_type index) {
+      Tree* tree = static_cast<Tree*>(table[index]);
+      typename Tree::iterator tree_it = tree->begin();
+      do {
+        Node* node = NodePtrFromKeyPtr(*tree_it);
+        InsertUnique(BucketNumber(**tree_it), node);
+      } while (++tree_it != tree->end());
+      DestroyTree(tree);
+    }
+
+    Node* EraseFromLinkedList(Node* item, Node* head) {
+      if (head == item) {
+        return head->next;
+      } else {
+        head->next = EraseFromLinkedList(item, head->next);
+        return head;
+      }
+    }
+
+    bool TableEntryIsEmpty(size_type b) const {
+      return TableEntryIsEmpty(table_, b);
+    }
+    bool TableEntryIsNonEmptyList(size_type b) const {
+      return TableEntryIsNonEmptyList(table_, b);
+    }
+    bool TableEntryIsTree(size_type b) const {
+      return TableEntryIsTree(table_, b);
+    }
+    bool TableEntryIsList(size_type b) const {
+      return TableEntryIsList(table_, b);
+    }
+    static bool TableEntryIsEmpty(void* const* table, size_type b) {
+      return table[b] == NULL;
+    }
+    static bool TableEntryIsNonEmptyList(void* const* table, size_type b) {
+      return table[b] != NULL && table[b] != table[b ^ 1];
+    }
+    static bool TableEntryIsTree(void* const* table, size_type b) {
+      return !TableEntryIsEmpty(table, b) &&
+          !TableEntryIsNonEmptyList(table, b);
+    }
+    static bool TableEntryIsList(void* const* table, size_type b) {
+      return !TableEntryIsTree(table, b);
+    }
+
+    void TreeConvert(size_type b) {
+      GOOGLE_DCHECK(!TableEntryIsTree(b) && !TableEntryIsTree(b ^ 1));
+      typename Allocator::template rebind<Tree>::other tree_allocator(alloc_);
+      Tree* tree = tree_allocator.allocate(1);
+      // We want to use the three-arg form of construct, if it exists, but we
+      // create a temporary and use the two-arg construct that's known to exist.
+      // It's clunky, but the compiler should be able to generate more-or-less
+      // the same code.
+      tree_allocator.construct(tree,
+                               Tree(KeyCompare(), KeyPtrAllocator(alloc_)));
+      // Now the tree is ready to use.
+      size_type count = CopyListToTree(b, tree) + CopyListToTree(b ^ 1, tree);
+      GOOGLE_DCHECK_EQ(count, tree->size());
+      table_[b] = table_[b ^ 1] = static_cast<void*>(tree);
+    }
+
+    // Copy a linked list in the given bucket to a tree.
+    // Returns the number of things it copied.
+    size_type CopyListToTree(size_type b, Tree* tree) {
+      size_type count = 0;
+      Node* node = static_cast<Node*>(table_[b]);
+      while (node != NULL) {
+        tree->insert(KeyPtrFromNodePtr(node));
+        ++count;
+        Node* next = node->next;
+        node->next = NULL;
+        node = next;
+      }
+      return count;
+    }
+
+    // Return whether table_[b] is a linked list that seems awfully long.
+    // Requires table_[b] to point to a non-empty linked list.
+    bool TableEntryIsTooLong(size_type b) {
+      const int kMaxLength = 8;
+      size_type count = 0;
+      Node* node = static_cast<Node*>(table_[b]);
+      do {
+        ++count;
+        node = node->next;
+      } while (node != NULL);
+      // Invariant: no linked list ever is more than kMaxLength in length.
+      GOOGLE_DCHECK_LE(count, kMaxLength);
+      return count >= kMaxLength;
+    }
+
+    size_type BucketNumber(const Key& k) const {
+      // We inherit from hasher, so one-arg operator() provides a hash function.
+      size_type h = (*const_cast<InnerMap*>(this))(k);
+      // To help prevent people from making assumptions about the hash function,
+      // we use the seed differently depending on NDEBUG.  The default hash
+      // function, the seeding, etc., are all likely to change in the future.
+#ifndef NDEBUG
+      return (h * (seed_ | 1)) & (num_buckets_ - 1);
+#else
+      return (h + seed_) & (num_buckets_ - 1);
+#endif
+    }
+
+    bool IsMatch(const Key& k0, const Key& k1) const {
+      return std::equal_to<Key>()(k0, k1);
+    }
+
+    // Return a power of two no less than max(kMinTableSize, n).
+    // Assumes either n < kMinTableSize or n is a power of two.
+    size_type TableSize(size_type n) {
+      return n < kMinTableSize ? kMinTableSize : n;
+    }
+
+    // Use alloc_ to allocate an array of n objects of type U.
+    template <typename U>
+    U* Alloc(size_type n) {
+      typedef typename Allocator::template rebind<U>::other alloc_type;
+      return alloc_type(alloc_).allocate(n);
+    }
+
+    // Use alloc_ to deallocate an array of n objects of type U.
+    template <typename U>
+    void Dealloc(U* t, size_type n) {
+      typedef typename Allocator::template rebind<U>::other alloc_type;
+      alloc_type(alloc_).deallocate(t, n);
+    }
+
+    void DestroyNode(Node* node) {
+      alloc_.destroy(&node->kv);
+      Dealloc<Node>(node, 1);
+    }
+
+    void DestroyTree(Tree* tree) {
+      typename Allocator::template rebind<Tree>::other tree_allocator(alloc_);
+      tree_allocator.destroy(tree);
+      tree_allocator.deallocate(tree, 1);
+    }
+
+    void** CreateEmptyTable(size_type n) {
+      GOOGLE_DCHECK(n >= kMinTableSize);
+      GOOGLE_DCHECK_EQ(n & (n - 1), 0);
+      void** result = Alloc<void*>(n);
+      memset(result, 0, n * sizeof(result[0]));
+      return result;
+    }
+
+    // Return a randomish value.
+    size_type Seed() const {
+      // random_device can throw, so avoid it unless we are compiling with
+      // exceptions enabled.
+#if __cpp_exceptions && LANG_CXX11
+      try {
+        std::random_device rd;
+        std::knuth_b knuth(rd());
+        std::uniform_int_distribution<size_type> u;
+        return u(knuth);
+      } catch (...) { }
+#endif
+      size_type s = static_cast<size_type>(reinterpret_cast<uintptr_t>(this));
+#if defined(__x86_64__) && defined(__GNUC__)
+      uint32 hi, lo;
+      asm("rdtsc" : "=a" (lo), "=d" (hi));
+      s += ((static_cast<uint64>(hi) << 32) | lo);
+#endif
+      return s;
+    }
+
+    size_type num_elements_;
+    size_type num_buckets_;
+    size_type seed_;
+    size_type index_of_first_non_null_;
+    void** table_;  // an array with num_buckets_ entries
+    Allocator alloc_;
+    GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(InnerMap);
+  };  // end of class InnerMap
+
+  typedef hash_map<Key, value_type*, hash<Key>, equal_to<Key>,
+                   MapAllocator<std::pair<const Key, MapPair<Key, T>*> > >
+      DeprecatedInnerMap;
 
  public:
   // Iterators
+  class iterator_base {
+   public:
+    // We support "old style" and "new style" iterators for now. This is
+    // temporary.  Also, for "iterator()" we have an unknown category.
+    // TODO(gpike): get rid of this.
+    enum IteratorStyle { kUnknown, kOld, kNew };
+    explicit iterator_base(IteratorStyle style) : iterator_style_(style) {}
+
+    bool OldStyle() const {
+      GOOGLE_DCHECK_NE(iterator_style_, kUnknown);
+      return iterator_style_ == kOld;
+    }
+    bool UnknownStyle() const {
+      return iterator_style_ == kUnknown;
+    }
+    bool SameStyle(const iterator_base& other) const {
+      return iterator_style_ == other.iterator_style_;
+    }
+
+   private:
+    IteratorStyle iterator_style_;
+  };
+
   class const_iterator
-      : public std::iterator<std::forward_iterator_tag, value_type, ptrdiff_t,
+      : private iterator_base,
+        public std::iterator<std::forward_iterator_tag, value_type, ptrdiff_t,
                              const value_type*, const value_type&> {
     typedef typename InnerMap::const_iterator InnerIt;
+    typedef typename DeprecatedInnerMap::const_iterator DeprecatedInnerIt;
 
    public:
-    const_iterator() {}
-    explicit const_iterator(const InnerIt& it) : it_(it) {}
+    const_iterator() : iterator_base(iterator_base::kUnknown) {}
+    explicit const_iterator(const DeprecatedInnerIt& dit)
+        : iterator_base(iterator_base::kOld), dit_(dit) {}
+    explicit const_iterator(const InnerIt& it)
+        : iterator_base(iterator_base::kNew), it_(it) {}
 
-    const_reference operator*() const { return *it_->second; }
-    const_pointer operator->() const { return it_->second; }
+    const_iterator(const const_iterator& other)
+        : iterator_base(other), it_(other.it_), dit_(other.dit_) {}
+
+    const_reference operator*() const {
+      return this->OldStyle() ? *dit_->second : *it_->value();
+    }
+    const_pointer operator->() const { return &(operator*()); }
 
     const_iterator& operator++() {
-      ++it_;
+      if (this->OldStyle())
+        ++dit_;
+      else
+        ++it_;
       return *this;
     }
-    const_iterator operator++(int) { return const_iterator(it_++); }
+    const_iterator operator++(int) {
+      return this->OldStyle() ? const_iterator(dit_++) : const_iterator(it_++);
+    }
 
     friend bool operator==(const const_iterator& a, const const_iterator& b) {
-      return a.it_ == b.it_;
+      if (!a.SameStyle(b)) return false;
+      if (a.UnknownStyle()) return true;
+      return a.OldStyle() ? (a.dit_ == b.dit_) : (a.it_ == b.it_);
     }
     friend bool operator!=(const const_iterator& a, const const_iterator& b) {
-      return a.it_ != b.it_;
+      return !(a == b);
     }
 
    private:
     InnerIt it_;
+    DeprecatedInnerIt dit_;
   };
 
-  class iterator : public std::iterator<std::forward_iterator_tag, value_type> {
+  class iterator : private iterator_base,
+                   public std::iterator<std::forward_iterator_tag, value_type> {
     typedef typename InnerMap::iterator InnerIt;
+    typedef typename DeprecatedInnerMap::iterator DeprecatedInnerIt;
 
    public:
-    iterator() {}
-    explicit iterator(const InnerIt& it) : it_(it) {}
-
-    reference operator*() const { return *it_->second; }
-    pointer operator->() const { return it_->second; }
+    iterator() : iterator_base(iterator_base::kUnknown) {}
+    explicit iterator(const DeprecatedInnerIt& dit)
+        : iterator_base(iterator_base::kOld), dit_(dit) {}
+    explicit iterator(const InnerIt& it)
+        : iterator_base(iterator_base::kNew), it_(it) {}
+
+    reference operator*() const {
+      return this->OldStyle() ? *dit_->second : *it_->value();
+    }
+    pointer operator->() const { return &(operator*()); }
 
     iterator& operator++() {
-      ++it_;
+      if (this->OldStyle())
+        ++dit_;
+      else
+        ++it_;
       return *this;
     }
-    iterator operator++(int) { return iterator(it_++); }
+    iterator operator++(int) {
+      return this->OldStyle() ? iterator(dit_++) : iterator(it_++);
+    }
 
-    // Implicitly convertible to const_iterator.
-    operator const_iterator() const { return const_iterator(it_); }
+    // Allow implicit conversion to const_iterator.
+    operator const_iterator() const {
+      return this->OldStyle() ?
+          const_iterator(typename DeprecatedInnerMap::const_iterator(dit_)) :
+          const_iterator(typename InnerMap::const_iterator(it_));
+    }
 
     friend bool operator==(const iterator& a, const iterator& b) {
-      return a.it_ == b.it_;
+      if (!a.SameStyle(b)) return false;
+      if (a.UnknownStyle()) return true;
+      return a.OldStyle() ? a.dit_ == b.dit_ : a.it_ == b.it_;
     }
     friend bool operator!=(const iterator& a, const iterator& b) {
-      return a.it_ != b.it_;
+      return !(a == b);
     }
 
    private:
     friend class Map;
+
     InnerIt it_;
+    DeprecatedInnerIt dit_;
   };
 
-  iterator begin() { return iterator(elements_.begin()); }
-  iterator end() { return iterator(elements_.end()); }
-  const_iterator begin() const { return const_iterator(elements_.begin()); }
-  const_iterator end() const { return const_iterator(elements_.end()); }
+  iterator begin() {
+    return old_style_ ? iterator(deprecated_elements_->begin())
+                      : iterator(elements_->begin());
+  }
+  iterator end() {
+    return old_style_ ? iterator(deprecated_elements_->end())
+                      : iterator(elements_->end());
+  }
+  const_iterator begin() const {
+    return old_style_ ? const_iterator(deprecated_elements_->begin())
+                      : const_iterator(iterator(elements_->begin()));
+  }
+  const_iterator end() const {
+    return old_style_ ? const_iterator(deprecated_elements_->end())
+                      : const_iterator(iterator(elements_->end()));
+  }
   const_iterator cbegin() const { return begin(); }
   const_iterator cend() const { return end(); }
 
   // Capacity
-  size_type size() const { return elements_.size(); }
-  bool empty() const { return elements_.empty(); }
+  size_type size() const {
+    return old_style_ ? deprecated_elements_->size() : elements_->size();
+  }
+  bool empty() const { return size() == 0; }
 
   // Element access
   T& operator[](const key_type& key) {
-    value_type** value = &elements_[key];
+    value_type** value =
+        old_style_ ? &(*deprecated_elements_)[key] : &(*elements_)[key];
     if (*value == NULL) {
       *value = CreateValueTypeInternal(key);
       internal::MapValueInitializer<google::protobuf::is_proto_enum<T>::value,
@@ -696,13 +1522,16 @@ class Map {
 
   // Lookup
   size_type count(const key_type& key) const {
-    return elements_.count(key);
+    if (find(key) != end()) assert(key == find(key)->first);
+    return find(key) == end() ? 0 : 1;
   }
   const_iterator find(const key_type& key) const {
-    return const_iterator(elements_.find(key));
+    return old_style_ ? const_iterator(deprecated_elements_->find(key))
+        : const_iterator(iterator(elements_->find(key)));
   }
   iterator find(const key_type& key) {
-    return iterator(elements_.find(key));
+    return old_style_ ? iterator(deprecated_elements_->find(key))
+                      : iterator(elements_->find(key));
   }
   std::pair<const_iterator, const_iterator> equal_range(
       const key_type& key) const {
@@ -726,13 +1555,22 @@ class Map {
 
   // insert
   std::pair<iterator, bool> insert(const value_type& value) {
-    iterator it = find(value.first);
-    if (it != end()) {
-      return std::pair<iterator, bool>(it, false);
+    if (old_style_) {
+      iterator it = find(value.first);
+      if (it != end()) {
+        return std::pair<iterator, bool>(it, false);
+      } else {
+        return std::pair<iterator, bool>(
+            iterator(deprecated_elements_->insert(std::pair<Key, value_type*>(
+                value.first, CreateValueTypeInternal(value))).first), true);
+      }
     } else {
-      return std::pair<iterator, bool>(
-          iterator(elements_.insert(std::pair<Key, value_type*>(
-              value.first, CreateValueTypeInternal(value))).first), true);
+      std::pair<typename InnerMap::iterator, bool> p =
+          elements_->insert(value.first);
+      if (p.second) {
+        p.first->value() = CreateValueTypeInternal(value);
+      }
+      return std::pair<iterator, bool>(iterator(p.first), p.second);
     }
   }
   template <class InputIt>
@@ -745,33 +1583,31 @@ class Map {
     }
   }
 
-  // Erase
+  // Erase and clear
   size_type erase(const key_type& key) {
-    typename InnerMap::iterator it = elements_.find(key);
-    if (it == elements_.end()) {
+    iterator it = find(key);
+    if (it == end()) {
       return 0;
     } else {
-      if (arena_ == NULL) delete it->second;
-      elements_.erase(it);
+      erase(it);
       return 1;
     }
   }
-  void erase(iterator pos) {
-    if (arena_ == NULL) delete pos.it_->second;
-    elements_.erase(pos.it_);
+  iterator erase(iterator pos) {
+    if (arena_ == NULL) delete pos.operator->();
+    iterator i = pos++;
+    if (old_style_)
+      deprecated_elements_->erase(i.dit_);
+    else
+      elements_->erase(i.it_);
+    return pos;
   }
   void erase(iterator first, iterator last) {
-    for (iterator it = first; it != last;) {
-      if (arena_ == NULL) delete it.it_->second;
-      elements_.erase((it++).it_);
+    while (first != last) {
+      first = erase(first);
     }
   }
-  void clear() {
-    for (iterator it = begin(); it != end(); ++it) {
-      if (arena_ == NULL) delete it.it_->second;
-    }
-    elements_.clear();
-  }
+  void clear() { erase(begin(), end()); }
 
   // Assign
   Map& operator=(const Map& other) {
@@ -782,6 +1618,13 @@ class Map {
     return *this;
   }
 
+  // Access to hasher.  Currently this returns a copy, but it may
+  // be modified to return a const reference in the future.
+  hasher hash_function() const {
+    return old_style_ ? deprecated_elements_->hash_function()
+                      : elements_->hash_function();
+  }
+
  private:
   // Set default enum value only for proto2 map field whose value is enum type.
   void SetDefaultEnumValue(int default_enum_value) {
@@ -816,9 +1659,15 @@ class Map {
   }
 
   Arena* arena_;
-  Allocator allocator_;
-  InnerMap elements_;
   int default_enum_value_;
+  // The following is a tagged union because we support two map styles
+  // for now.
+  // TODO(gpike): get rid of the old style.
+  const bool old_style_;
+  union {
+    InnerMap* elements_;
+    DeprecatedInnerMap* deprecated_elements_;
+  };
 
   friend class ::google::protobuf::Arena;
   typedef void InternalArenaConstructable_;
@@ -839,6 +1688,12 @@ struct hash<google::protobuf::MapKey> {
   size_t
   operator()(const google::protobuf::MapKey& map_key) const {
     switch (map_key.type()) {
+      case google::protobuf::FieldDescriptor::CPPTYPE_DOUBLE:
+      case google::protobuf::FieldDescriptor::CPPTYPE_FLOAT:
+      case google::protobuf::FieldDescriptor::CPPTYPE_ENUM:
+      case google::protobuf::FieldDescriptor::CPPTYPE_MESSAGE:
+        GOOGLE_LOG(FATAL) << "Unsupported";
+        break;
       case google::protobuf::FieldDescriptor::CPPTYPE_STRING:
         return hash<string>()(map_key.GetStringValue());
       case google::protobuf::FieldDescriptor::CPPTYPE_INT64:
@@ -851,11 +1706,6 @@ struct hash<google::protobuf::MapKey> {
         return hash< ::google::protobuf::uint32>()(map_key.GetUInt32Value());
       case google::protobuf::FieldDescriptor::CPPTYPE_BOOL:
         return hash<bool>()(map_key.GetBoolValue());
-      case google::protobuf::FieldDescriptor::CPPTYPE_DOUBLE:
-      case google::protobuf::FieldDescriptor::CPPTYPE_FLOAT:
-      case google::protobuf::FieldDescriptor::CPPTYPE_ENUM:
-      case google::protobuf::FieldDescriptor::CPPTYPE_MESSAGE:
-        GOOGLE_LOG(FATAL) << "Can't get here.";
     }
     GOOGLE_LOG(FATAL) << "Can't get here.";
     return 0;
@@ -863,26 +1713,7 @@ struct hash<google::protobuf::MapKey> {
   bool
   operator()(const google::protobuf::MapKey& map_key1,
              const google::protobuf::MapKey& map_key2) const {
-    switch (map_key1.type()) {
-#define COMPARE_CPPTYPE(CPPTYPE, CPPTYPE_METHOD)             \
-      case google::protobuf::FieldDescriptor::CPPTYPE_##CPPTYPE: \
-        return map_key1.Get##CPPTYPE_METHOD##Value() <           \
-               map_key2.Get##CPPTYPE_METHOD##Value();
-      COMPARE_CPPTYPE(STRING, String)
-      COMPARE_CPPTYPE(INT64,  Int64)
-      COMPARE_CPPTYPE(INT32,  Int32)
-      COMPARE_CPPTYPE(UINT64, UInt64)
-      COMPARE_CPPTYPE(UINT32, UInt32)
-      COMPARE_CPPTYPE(BOOL,   Bool)
-#undef COMPARE_CPPTYPE
-      case google::protobuf::FieldDescriptor::CPPTYPE_DOUBLE:
-      case google::protobuf::FieldDescriptor::CPPTYPE_FLOAT:
-      case google::protobuf::FieldDescriptor::CPPTYPE_ENUM:
-      case google::protobuf::FieldDescriptor::CPPTYPE_MESSAGE:
-        GOOGLE_LOG(FATAL) << "Can't get here.";
-    }
-    GOOGLE_LOG(FATAL) << "Can't get here.";
-    return true;
+    return map_key1 < map_key2;
   }
 };
 GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_END