Introduce a FlatMap and FlatSet into WTF

third_party/WebKit/Source/wtf/FlatSet.h

Index: third_party/WebKit/Source/wtf/FlatSet.h
diff --git a/third_party/WebKit/Source/wtf/FlatSet.h b/third_party/WebKit/Source/wtf/FlatSet.h
new file mode 100644
index 0000000000000000000000000000000000000000..89f8071f81588e6c8e7217fa4ca09f27c858b46d
--- /dev/null
+++ b/third_party/WebKit/Source/wtf/FlatSet.h
@@ -0,0 +1,70 @@
+// 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_FlatSet_h
+#define WTF_FlatSet_h
+
+#include "base/macros.h"
+#include "wtf/FlatTable.h"
+
+namespace WTF {
+
+template <typename Key>
+struct FlatSetDelegate {
+  using key_type = Key;
+  using value_type = Key;
+
+  static inline const Key& ToKey(const value_type& v) { return v; }
+};
+
+// A FlatSet is an STL-like associative container backed by a ring buffer. This
+// can offer superior performance and a lower memory overhead when the set
+// either has a low number of Elements or it doesn't change much.
+template <typename Key>
+class FlatSet : public FlatTable<FlatSetDelegate<Key>> {
+ public:
+  FlatSet() {}
+
+  using BaseClass = FlatTable<FlatSetDelegate<Key>>;
+  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); }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(FlatSet);

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

STL containers are copyable and assignable -- is there a reason to be different
here?

[alex clarke (OOO till 29th), 2016/10/13 14:16:32]

Done.

+};
+
+}  // namespace WTF
+
+#endif  // WTF_FlatSet_h