Introduce a FlatMap and FlatSet into WTF

third_party/WebKit/Source/wtf/FlatMap.h

+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef WTF_FlatMap_h
+#define WTF_FlatMap_h
+
+#include "base/macros.h"
+#include "wtf/FlatTable.h"
+
+namespace WTF {
+
+template <typename Key, typename Value>
+struct FlatMapDelegate {
+  using key_type = Key;
+  using value_type = std::pair<Key, Value>;
+
+  static inline const Key& ToKey(const value_type& v) { return v.first; }
+};
+
+// A FlatMap is an STL-like associative container backed by a ring buffer. This
+// can offer superior performance and a lower memory overhead when the map has
+// a low number of Elements or it doesn't change much.

[Sami, 2016/10/07 09:49:11]

It'd be useful to quantify what "low" means.

+template <typename Key, typename Value>
+class FlatMap : public FlatTable<FlatMapDelegate<Key, Value>> {
+ public:
+  FlatMap() {}
+
+  using BaseClass = FlatTable<FlatMapDelegate<Key, Value>>;
+  using key_type = typename BaseClass::key_type;
+  using value_type = typename BaseClass::value_type;
+  using iterator = typename BaseClass::iterator;
+  using const_iterator = typename BaseClass::const_iterator;
+  using reverse_iterator = typename BaseClass::reverse_iterator;
+  using const_reverse_iterator = typename BaseClass::const_reverse_iterator;
+
+  using BaseClass::empty;
+  using BaseClass::clear;
+  using BaseClass::insert;
+  using BaseClass::insertUnique;
+  using BaseClass::size;
+
+  iterator begin() { return BaseClass::begin(); }
+  iterator end() { return BaseClass::end(); }
+  const_iterator begin() const { return BaseClass::begin(); }
+  const_iterator end() const { return BaseClass::end(); }
+  reverse_iterator rbegin() { return BaseClass::rbegin(); }
+  const_reverse_iterator rbegin() const { return BaseClass::rbegin(); }
+
+  // Erases an entry corresponding to |key|, if any, from the map.
+  // Invalidates any iterators. O(log n + n / 2)
+  size_t erase(const Key& key) { return BaseClass::erase(key); }
+
+  // Erases |it| from the map, invalidating any iterators. O(n / 2)
+  void erase(const iterator& it) { return BaseClass::erase(it); }
+  void erase(const reverse_iterator& it) { return BaseClass::erase(it); }
+
+  // O(log n)
+  iterator find(const Key& key) { return BaseClass::find(key); }
+
+  // O(log n)
+  const_iterator find(const Key& key) const { return BaseClass::find(key); }
+
+  // O(log n + n / 2)
+  void ChangeKey(const iterator& it, const Key& new_key) {
+    DCHECK(iteratorBelongsToThisTable(it));
+    size_t index;
+    if (BinarySearch(new_key, &index)) {
+      // We are overwriting an existing entry.
+      Element(index).second = std::move(it->second);
+      erase(it);
+      return;
+    }
+
+    ChangeKeyUnique(it, new_key);
+  }
+
+  // O(n / 2)
+  void ChangeKeyUnique(const iterator& it, const Key& new_key) {
+    DCHECK(iteratorBelongsToThisTable(it));
+    size_t i = iteratorPosition(it);
+    if (Element(i).first < new_key) {
+      Value tempValue = std::move(Element(i).second);
+      for (; (i + 1) != back_ && Element(i + 1).first < new_key; i++) {
+        Element(i) = std::move(Element(i + 1));
+      }
+      Element(i).first = new_key;
+      Element(i).second = std::move(tempValue);
+    } else if (new_key < Element(i).first) {
+      Value tempValue = std::move(Element(i).second);
+      for (; i != front_ && new_key < Element(i - 1).first; i--) {
+        Element(i) = std::move(Element(i - 1));
+      }
+      Element(i).first = new_key;
+      Element(i).second = std::move(tempValue);
+    }
+  }
+
+ private:
+  using BaseClass::Element;
+  using BaseClass::iteratorBelongsToThisTable;
+  using BaseClass::BinarySearch;
+  using BaseClass::iteratorPosition;
+  using BaseClass::front_;
+  using BaseClass::back_;
+
+  DISALLOW_COPY_AND_ASSIGN(FlatMap);
+};
+
+}  // namespace WTF
+
+#endif  // WTF_FlatMap_h