[clang-tidy] Add performance-expensive-flat-container-operation check

[nicovank]

Summary

This check has been enabled internally at Facebook for a few months now (with OnlyWarnInLoops disabled), where folly::sorted_vector_map is pretty widely used.

I saw std::flat_(map|set) and std::flat_multi(map|set) will appear in C++23, at which point this check can be updated to include these.

folly::heap_vector_(map|set) is another example of such containers, though still relatively new so not included here yet.

[nicovank]

Rename second test file

[Eugene.Zelenko]

clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.h

32

Please add isLanguageVersionSupported.

clang-tools-extra/docs/clang-tidy/checks/performance/expensive-flat-container-operation.rst

7

Please synchronize first statement with Release Notes.

[nicovank]

Add isLanguageVersionSupported.

[nicovank]

Ping.

[nicovank]

Ping.

I feel like Phabricator is not sending notifications for this patch like it usually does (I'm not getting any emails).
I'll create a new, identical patch tomorrow if there's still no activity.

[Eugene.Zelenko]

I got notification.

[nicovank]

In D131939#3755399, @Eugene.Zelenko wrote:

I got notification.

Thank you. I got an email for this message but not my own updates, which usually also CC me 🤷.
Thanks!

[nicovank]

Ping.

[nicovank]

Mid-CppCon ping.

[nicovank]

Rebase.

[nicovank]

Ping.

[nicovank]

Ping.

[njames93]

I have a feeling the default should be to only warm in loops otherwise this could get noisy. Though setting it as the default you'd likely want to change the name to something along the lines of WarmOutsideLoops.

clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.cpp

70

Rather than checking for an ancestor. Use the mapAnyOf matcher to check for a descendant in a loops body, this would remove the need for the false positive check below.
Also you aren't checking a ranged for.

[nicovank]

Rename OnlyWarnInLoops to WarnOutsideLoops, cover missed cxxForRangeStmt

[nicovank]

Thank you for the feedback!

In D131939#3822766, @njames93 wrote:

I have a feeling the default should be to only warm in loops otherwise this could get noisy.

Agreed, the less noisy version was already the default, renaming it is a good idea to avoid confusions.

clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.cpp

70

Thank you for catching the missing cxxForRangeStmt. Didn't know of mapAnyOf.

The idea is to not warn in cases such as below, where the declaration is in the same loop block as the insert/erase operation. Here, relatively, the insert is not in the loop. Of course, it's not possible to check the lifetime of the object in every case to make sure it's constrained to the loop, but from what I've seen this is the main false-positive case.

while(...) {
    flat_set<...> s;
    s.insert(...);
}

I don't think mapAnyOf makes expressing this any simpler (still need to check that the declaration is not within the same loop) so I kept the current version. If you really prefer mapAnyOf I can look into it again.

[nicovank]

Ping.

[nicovank]

Ping.

@njames93 If you have a minute, could you please take a second look at this? Let me know what's needed to get this change landed.

[nicovank]

Ping.

[nicovank]

Ping :)

clang-tools-extra/clang-tidy/performance/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_library(clangTidyPerformanceModule
+  ExpensiveFlatContainerOperationCheck.cpp
   FasterStringFindCheck.cpp
   ForRangeCopyCheck.cpp
   ImplicitConversionInLoopCheck.cpp
   InefficientAlgorithmCheck.cpp
   InefficientStringConcatenationCheck.cpp
   InefficientVectorOperationCheck.cpp
   MoveConstArgCheck.cpp
   MoveConstructorInitCheck.cpp

clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.h

+//===--- ExpensiveFlatContainerOperationCheck.h - clang-tidy ----*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_EXPENSIVEFLATCONTAINEROPERATIONCHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_EXPENSIVEFLATCONTAINEROPERATIONCHECK_H
+
+#include "../ClangTidyCheck.h"
+
+#include <vector>
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+/// Warns when calling an O(N) operation on a flat container.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/performance/expensive-flat-container-operation.html
+class ExpensiveFlatContainerOperationCheck : public ClangTidyCheck {
+public:
+  ExpensiveFlatContainerOperationCheck(StringRef Name,
+                                       ClangTidyContext *Context);
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+  void storeOptions(ClangTidyOptions::OptionMap &Opts) override;
+  bool isLanguageVersionSupported(const LangOptions &LangOpts) const override {
+    return LangOpts.CPlusPlus;
+  }
+
+private:
+  const bool OnlyWarnInLoops;
+  const std::vector<StringRef> FlatContainers;
+};
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_EXPENSIVEFLATCONTAINEROPERATIONCHECK_H

clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.cpp

+//===--- ExpensiveFlatContainerOperationCheck.cpp - clang-tidy ------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "ExpensiveFlatContainerOperationCheck.h"
+
+#include "../utils/OptionsUtils.h"
+
+using namespace clang::ast_matchers;
+
+namespace {
+const auto DefaultFlatContainers =
+    "::folly::sorted_vector_set; ::folly::sorted_vector_map;"
+    "::boost::container::flat_set; ::boost::container::flat_map;";
+} // namespace
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+ExpensiveFlatContainerOperationCheck::ExpensiveFlatContainerOperationCheck(
+    StringRef Name, ClangTidyContext *Context)
+    : ClangTidyCheck(Name, Context),
+      OnlyWarnInLoops(Options.get("OnlyWarnInLoops", true)),
+      FlatContainers(utils::options::parseStringList(
+          Options.get("FlatContainers", DefaultFlatContainers))) {}
+
+void ExpensiveFlatContainerOperationCheck::registerMatchers(
+    MatchFinder *Finder) {
+  const auto SoughtContainerDecl = cxxRecordDecl(
+      hasAnyName(FlatContainers),
+      has(typedefNameDecl(
+          hasName("value_type"),
+          hasType(hasUnqualifiedDesugaredType(type().bind("value_type"))))));
+
+  const auto HasSoughtArrowMemberExpr = has(memberExpr(
+      isArrow(), hasObjectExpression(
+                     hasType(pointerType(pointee(hasUnqualifiedDesugaredType(
+                         recordType(hasDeclaration(SoughtContainerDecl)))))))));
+
+  // We don't need to make sure the MemberExpr is not an arrow call, if it was
+  // the code wouldn't compile anyway.
+  const auto HasSoughtPeriodMemberExpr =
+      has(memberExpr(hasObjectExpression(hasType(hasUnqualifiedDesugaredType(
+          recordType(hasDeclaration(SoughtContainerDecl)))))));
+
+  const auto HasEmplaceCall = callee(cxxMethodDecl(matchesName("emplace")));
+
+  const auto HasInsertCallWithValueTypeArgument =
+      cxxMemberCallExpr(callee(cxxMethodDecl(matchesName("insert"))),
+                        hasAnyArgument(expr(hasType(hasUnqualifiedDesugaredType(
+                            type(equalsBoundNode("value_type")))))));
+
+  const auto HasEraseCallWithOneArgument = cxxMemberCallExpr(
+      callee(cxxMethodDecl(matchesName("erase"))), argumentCountIs(1));
+
+  const auto SoughtFlatContainerOperation =
+      cxxMemberCallExpr(
+          anyOf(HasSoughtArrowMemberExpr, HasSoughtPeriodMemberExpr),
+          anyOf(HasEmplaceCall, HasInsertCallWithValueTypeArgument,
+                HasEraseCallWithOneArgument))
+          .bind("call");
+
+  if (OnlyWarnInLoops) {
+    const auto IsWithinLoop = cxxMemberCallExpr(
+        hasAncestor(stmt(anyOf(forStmt(), whileStmt(), doStmt())).bind("loop")),
+        // An easy false positive case: the variable is declared in the loop.
+        unless(onImplicitObjectArgument(declRefExpr(hasDeclaration(
+            decl(hasAncestor(stmt(equalsBoundNode("loop")))))))));
+
+    Finder->addMatcher(
+        cxxMemberCallExpr(SoughtFlatContainerOperation, IsWithinLoop), this);
+  } else {
+    Finder->addMatcher(SoughtFlatContainerOperation, this);
+  }
+}
+
+void ExpensiveFlatContainerOperationCheck::check(
+    const MatchFinder::MatchResult &Result) {
+  const auto *Call = Result.Nodes.getNodeAs<CXXMemberCallExpr>("call");
+
+  diag(Call->getExprLoc(),
+       "Single element operations are expensive for flat containers. "
+       "Consider using available bulk operations instead.");
+}
+
+void ExpensiveFlatContainerOperationCheck::storeOptions(
+    ClangTidyOptions::OptionMap &Opts) {
+  Options.store(Opts, "OnlyWarnInLoops", OnlyWarnInLoops);
+  Options.store(Opts, "FlatContainers",
+                utils::options::serializeStringList(FlatContainers));
+}
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang

clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp

 //===-- PerformanceTidyModule.cpp - clang-tidy ----------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "../ClangTidy.h"
 #include "../ClangTidyModule.h"
 #include "../ClangTidyModuleRegistry.h"
+#include "ExpensiveFlatContainerOperationCheck.h"
 #include "FasterStringFindCheck.h"
 #include "ForRangeCopyCheck.h"
 #include "ImplicitConversionInLoopCheck.h"
 #include "InefficientAlgorithmCheck.h"
 #include "InefficientStringConcatenationCheck.h"
 #include "InefficientVectorOperationCheck.h"
 #include "MoveConstArgCheck.h"
 #include "MoveConstructorInitCheck.h"
 #include "NoAutomaticMoveCheck.h"
 #include "NoIntToPtrCheck.h"
 #include "NoexceptMoveConstructorCheck.h"
 #include "TriviallyDestructibleCheck.h"
 #include "TypePromotionInMathFnCheck.h"
 #include "UnnecessaryCopyInitialization.h"
 #include "UnnecessaryValueParamCheck.h"
 
 namespace clang {
 namespace tidy {
 namespace performance {
 
 class PerformanceModule : public ClangTidyModule {
 public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
+    CheckFactories.registerCheck<ExpensiveFlatContainerOperationCheck>(
+        "performance-expensive-flat-container-operation");
     CheckFactories.registerCheck<FasterStringFindCheck>(
         "performance-faster-string-find");
     CheckFactories.registerCheck<ForRangeCopyCheck>(
         "performance-for-range-copy");
     CheckFactories.registerCheck<ImplicitConversionInLoopCheck>(
         "performance-implicit-conversion-in-loop");
     CheckFactories.registerCheck<InefficientAlgorithmCheck>(
         "performance-inefficient-algorithm");

clang-tools-extra/docs/ReleaseNotes.rst

 New checks
 ^^^^^^^^^^
 
 - New :doc:`cppcoreguidelines-avoid-const-or-ref-data-members
   <clang-tidy/checks/cppcoreguidelines/avoid-const-or-ref-data-members>` check.
 
   Warns when a struct or class uses const or reference (lvalue or rvalue) data members.
 
+- New :doc:`performance-expensive-flat-container-operation
+  <clang-tidy/checks/performance/expensive-flat-container-operation>` check.
+
+  Warns when calling an O(N) operation on a flat container.
+
 New check aliases
 ^^^^^^^^^^^^^^^^^
 
 - New alias :doc:`cert-msc54-cpp
   <clang-tidy/checks/cert/msc54-cpp>` to
   :doc:`bugprone-signal-handler
   <clang-tidy/checks/bugprone/signal-handler>` was added.
 

clang-tools-extra/docs/clang-tidy/checks/list.rst

.. csv-table::
    `objc-forbidden-subclassing <objc/forbidden-subclassing.html>`_,
    `objc-missing-hash <objc/missing-hash.html>`_,
    `objc-nsdate-formatter <objc/nsdate-formatter.html>`_,
    `objc-nsinvocation-argument-lifetime <objc/nsinvocation-argument-lifetime.html>`_, "Yes"
    `objc-property-declaration <objc/property-declaration.html>`_, "Yes"
    `objc-super-self <objc/super-self.html>`_, "Yes"
    `openmp-exception-escape <openmp/exception-escape.html>`_,
    `openmp-use-default-none <openmp/use-default-none.html>`_,
+   `performance-expensive-flat-container-operation <performance/expensive-flat-container-operation.html>`_,
    `performance-faster-string-find <performance/faster-string-find.html>`_, "Yes"
    `performance-for-range-copy <performance/for-range-copy.html>`_, "Yes"
    `performance-implicit-conversion-in-loop <performance/implicit-conversion-in-loop.html>`_,
    `performance-inefficient-algorithm <performance/inefficient-algorithm.html>`_, "Yes"
    `performance-inefficient-string-concatenation <performance/inefficient-string-concatenation.html>`_,
    `performance-inefficient-vector-operation <performance/inefficient-vector-operation.html>`_, "Yes"
    `performance-move-const-arg <performance/move-const-arg.html>`_, "Yes"
    `performance-move-constructor-init <performance/move-constructor-init.html>`_,

clang-tools-extra/docs/clang-tidy/checks/performance/expensive-flat-container-operation.rst

+.. title:: clang-tidy - performance-expensive-flat-container-operation
+
+performance-expensive-flat-container-operation
+==============================================
+
+Warns when calling an O(N) operation on a flat container.
+
+This check operates on vector-based flat containers such as
+``boost::container::flat_(map|set)`` and ``folly::sorted_vector_(map|set)``.
+While these containers' behavior is identical to usual maps/sets, the insert and
+erase operations are O(N). This check flags such operations, which are a common
+bad pattern, notably in loops.
+
+Below is an example of a typical bad pattern: inserting some values one by one
+into a flat container. This is O(N^2), as the container will need to shift
+elements right after each insertion.
+
+.. code-block:: c++
+
+    std::random_device generator;
+    std::uniform_int_distribution<int> distribution;
+
+    boost::container::flat_set<int> set;
+    for (auto i = 0; i < N; ++i) {
+        set.insert(distribution(generator));
+    }
+
+The code above can be improved using a temporary vector, later inserting all
+values at once into the ``flat_set``.
+
+.. code-block:: c++
+
+    std::vector<int> temporary;
+    for (auto i = 0; i < N; ++i) {
+        temporary.push_back(distribution(generator));
+    }
+    boost::container::flat_set<int> set(temporary.begin(), temporary.end());
+
+For expensive-to-copy objects, ``std::move_iterator`` should be used. It is also
+possible to move the temporary vector and use it directly as the underlying
+container when using folly's ``sorted_vector_(map|set)``.
+
+Other solutions exist, including notably using a different map such as
+``std::unordered_map`` when order is not important, bulk insertion with
+iterators, ``boost::transform_iterator`` and ``erase_if``.
+
+This check is not capable of flagging insertions into a map via ``operator[]``,
+as it is not possible at compile-time to know whether this will trigger an
+insertion. These cases will have to be detected via dynamic profiling.
+
+Options
+-------
+
+.. option:: OnlyWarnInLoops
+
+    When enabled, the check will only warn when the single element operation is
+    directly enclosed by a loop, hence directly actionable. At the very least,
+    these cases can be improved using some temporary container.
+
+    Default is `true`.
+
+.. option:: FlatContainers
+
+    A semicolon-separated list of flat containers, with ``insert``, ``emplace``
+    and/or ``erase`` operations.
+
+    Default includes ``boost::container::flat_(map|set)`` and
+    ``folly::sorted_vector_(map|set)``.

clang-tools-extra/test/clang-tidy/checkers/performance/expensive-flat-container-operation-only-warn-in-loops.cpp

+// RUN: %check_clang_tidy %s performance-expensive-flat-container-operation %t -- \
+// RUN:   -config="{CheckOptions: \
+// RUN:             [{key: performance-expensive-flat-container-operation.OnlyWarnInLoops, \
+// RUN:               value: true}] \
+// RUN:             }"
+
+namespace std {
+template <class T1, class T2>
+struct pair {
+  pair(T1, T2);
+};
+
+template<class T>
+struct initializer_list {
+  initializer_list();
+};
+} // namespace std
+
+// Copied from boost/container/flat_map.hpp and simplified.
+namespace boost {
+namespace container {
+struct ordered_unique_range_t {};
+
+template <typename Key>
+struct flat_set {
+  typedef Key key_type;
+  typedef Key value_type;
+
+  typedef int size_type;
+  typedef struct {} iterator;
+  typedef struct {} const_iterator;
+
+  const_iterator begin() const noexcept;
+  const_iterator end() const noexcept;
+
+  template <class... Args> std::pair<iterator, bool> emplace(Args&&...);
+
+  template <class... Args> iterator emplace_hint(const_iterator, Args&&...);
+
+  std::pair<iterator, bool> insert(const value_type&);
+  std::pair<iterator, bool> insert(value_type&&);
+  iterator insert(const_iterator, const value_type&);
+  iterator insert(const_iterator, value_type&&);
+  template <typename InputIterator> void insert(InputIterator, InputIterator);
+  template <typename InputIterator> void insert(ordered_unique_range_t, InputIterator, InputIterator);
+  void insert(std::initializer_list<value_type>);
+  void insert(ordered_unique_range_t, std::initializer_list<value_type>);
+
+  iterator erase(const_iterator);
+  size_type erase(const key_type&);
+  iterator erase(const_iterator, const_iterator);
+};
+} // namespace container
+} // namespace boost
+
+static boost::container::flat_set<int> gbfs;
+boost::container::flat_set<int>& getGlobalSetRef() {
+  return gbfs;
+};
+
+void TestCheckWithLoops() {
+  boost::container::flat_set<int> bfs;
+  bfs.insert(13);
+  bfs.erase(13);
+
+  for (int i = 0; i < 10; ++i) {
+    bfs.insert(i);
+    // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+    if (i % 2 == 0) {
+      bfs.erase(i);
+      // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+    }
+  }
+
+  while (true) {
+    bfs.erase(bfs.begin());
+    // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+  }
+
+  do {
+    (&bfs)->emplace(13);
+    // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+  } while (false);
+
+  for (int i = 0; i < 10; ++i) {
+    boost::container::flat_set<long> bfs;
+    if (i % 2 == 0) {
+      bfs.insert(i);
+
+      gbfs.insert(i);
+      // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+      getGlobalSetRef().insert(i);
+      // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+      (gbfs).insert(i);
+      // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+    }
+
+    for (int j = 0; j < i; ++j) {
+      bfs.insert(2 * j);
+      // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+    }
+  }
+}

clang-tools-extra/test/clang-tidy/checkers/performance/expensive-flat-container-operation.cpp

+// RUN: %check_clang_tidy %s performance-expensive-flat-container-operation %t -- \
+// RUN:   -config="{CheckOptions: \
+// RUN:             [{key: performance-expensive-flat-container-operation.OnlyWarnInLoops, \
+// RUN:               value: false}] \
+// RUN:             }"
+
+namespace std {
+template <class T1, class T2>
+struct pair {
+  pair(T1, T2);
+};
+
+template<class T>
+struct initializer_list {
+  initializer_list();
+};
+
+template<class T> struct remove_reference      { typedef T type; };
+template<class T> struct remove_reference<T&>  { typedef T type; };
+template<class T> struct remove_reference<T&&> { typedef T type; };
+
+template<class T>
+typename std::remove_reference<T>::type&& move(T&&) noexcept;
+} // namespace std
+
+// Copied from boost/container/flat_map.hpp and boost/container/flat_set.hpp and simplified.
+namespace boost {
+namespace container {
+struct ordered_unique_range_t {};
+
+template <typename Key, typename T>
+struct flat_map {
+  typedef Key key_type;
+  typedef T mapped_type;
+  typedef std::pair<Key, T> value_type;
+
+  typedef int size_type;
+  typedef struct {} iterator;
+  typedef struct {} const_iterator;
+
+  const_iterator begin() const noexcept;
+  const_iterator end() const noexcept;
+
+  template <class... Args> std::pair<iterator, bool> emplace(Args&&...);
+
+  template <class... Args> iterator emplace_hint(const_iterator, Args&&...);
+
+  template <class... Args> std::pair<iterator, bool> try_emplace(const key_type&, Args&&...);
+  template <class... Args> iterator try_emplace(const_iterator, const key_type&, Args&&...);
+  template <class... Args> std::pair<iterator, bool> try_emplace(key_type&&, Args&&...);
+  template <class... Args> iterator try_emplace(const_iterator, key_type&&, Args&&...);
+
+  std::pair<iterator, bool> insert(const value_type&);
+  std::pair<iterator, bool> insert(value_type&&);
+  iterator insert(const_iterator, const value_type&);
+  iterator insert(const_iterator, value_type&&);
+  template <typename InputIterator> void insert(InputIterator, InputIterator);
+  template <typename InputIterator> void insert(ordered_unique_range_t, InputIterator, InputIterator);
+  void insert(std::initializer_list<value_type>);
+  void insert(ordered_unique_range_t, std::initializer_list<value_type>);
+
+  iterator erase(const_iterator);
+  size_type erase(const key_type&);
+  iterator erase(const_iterator, const_iterator);
+};
+
+template <typename Key>
+struct flat_set {
+  typedef Key key_type;
+  typedef Key value_type;
+
+  typedef int size_type;
+  typedef struct {} iterator;
+  typedef struct {} const_iterator;
+
+  const_iterator begin() const noexcept;
+  const_iterator end() const noexcept;
+
+  template <class... Args> std::pair<iterator, bool> emplace(Args&&...);
+
+  template <class... Args> iterator emplace_hint(const_iterator, Args&&...);
+
+  std::pair<iterator, bool> insert(const value_type&);
+  std::pair<iterator, bool> insert(value_type&&);
+  iterator insert(const_iterator, const value_type&);
+  iterator insert(const_iterator, value_type&&);
+  template <typename InputIterator> void insert(InputIterator, InputIterator);
+  template <typename InputIterator> void insert(ordered_unique_range_t, InputIterator, InputIterator);
+  void insert(std::initializer_list<value_type>);
+  void insert(ordered_unique_range_t, std::initializer_list<value_type>);
+
+  iterator erase(const_iterator);
+  size_type erase(const key_type&);
+  iterator erase(const_iterator, const_iterator);
+};
+} // namespace container
+} // namespace boost
+
+// Copied from folly/sorted_vector_types.h and simplified.
+namespace folly {
+template <class Key, class Value> struct sorted_vector_map {
+  typedef Key key_type;
+  typedef Value mapped_type;
+  typedef std::pair<Key, Value> value_type;
+
+  typedef int size_type;
+  typedef struct {} iterator;
+  typedef struct {} const_iterator;
+
+  const_iterator begin() const;
+  const_iterator end() const;
+
+  std::pair<iterator, bool> insert(const value_type&);
+  std::pair<iterator, bool> insert(value_type&&);
+  iterator insert(const_iterator, const value_type&);
+  iterator insert(const_iterator, value_type&&);
+  template <class InputIterator> void insert(InputIterator, InputIterator);
+  void insert(std::initializer_list<value_type>);
+
+  template <typename... Args> std::pair<iterator, bool> emplace(Args&&...);
+  std::pair<iterator, bool> emplace(const value_type&);
+  std::pair<iterator, bool> emplace(value_type&&);
+
+  template <typename... Args> iterator emplace_hint(const_iterator, Args&&...);
+  iterator emplace_hint(const_iterator, const value_type&);
+  iterator emplace_hint(const_iterator, value_type&&);
+
+  size_type erase(const key_type&);
+  iterator erase(const_iterator);
+  iterator erase(const_iterator, const_iterator);
+};
+
+template <class T> struct sorted_vector_set {
+  typedef T value_type;
+  typedef T key_type;
+
+  typedef int size_type;
+  typedef struct {} iterator;
+  typedef struct {} const_iterator;
+
+  const_iterator begin() const;
+  const_iterator end() const;
+
+  std::pair<iterator, bool> insert(const value_type&);
+  std::pair<iterator, bool> insert(value_type&&);
+  iterator insert(const_iterator, const value_type&);
+  iterator insert(const_iterator, value_type&&);
+  template <class InputIterator> void insert(InputIterator, InputIterator);
+  void insert(std::initializer_list<value_type>);
+
+  template <typename... Args> std::pair<iterator, bool> emplace(Args&&...);
+  std::pair<iterator, bool> emplace(const value_type&);
+  std::pair<iterator, bool> emplace(value_type&&);
+
+  template <typename... Args> iterator emplace_hint(const_iterator, Args&&...);
+  iterator emplace_hint(const_iterator, const value_type&);
+  iterator emplace_hint(const_iterator, value_type&&);
+
+  size_type erase(const key_type&);
+  iterator erase(const_iterator);
+  iterator erase(const_iterator, const_iterator);
+};
+} // namespace folly
+
+struct Foo {
+  Foo() {}
+  Foo(const Foo&) = default;
+  Foo(Foo&&) = default;
+};
+
+void TestBoostFlapMap() {
+  boost::container::flat_map<Foo, int> bfm;
+  std::pair<Foo, int> foo(Foo(), 13);
+  boost::container::ordered_unique_range_t bar;
+
+  bfm.emplace(Foo(), 13);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfm.emplace_hint(bfm.begin(), Foo(), 13);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfm.try_emplace(Foo(), 13);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfm.try_emplace(bfm.begin(), Foo(), 13);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfm.try_emplace(Foo(), 13);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfm.try_emplace(bfm.begin(), Foo(), 13);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfm.insert(foo);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfm.insert(std::move(foo));
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfm.insert(bfm.begin(), foo);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfm.insert(bfm.begin(), std::move(foo));
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfm.insert(bfm.begin(), bfm.end());
+  bfm.insert(bar, bfm.begin(), bfm.end());
+  bfm.insert(std::initializer_list<std::pair<Foo, int>>());
+  bfm.insert(bar, std::initializer_list<std::pair<Foo, int>>());
+
+  bfm.erase(Foo());
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfm.erase(bfm.begin());
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfm.erase(bfm.begin(), bfm.end());
+}
+
+void TestBoostFlatSet() {
+  boost::container::flat_set<Foo> bfs;
+  Foo foo;
+  boost::container::ordered_unique_range_t bar;
+
+  bfs.emplace();
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfs.emplace_hint(bfs.begin());
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfs.insert(foo);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfs.insert(std::move(foo));
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfs.insert(bfs.begin(), foo);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfs.insert(bfs.begin(), std::move(foo));
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfs.insert(bfs.begin(), bfs.end());
+  bfs.insert(bar, bfs.begin(), bfs.end());
+  bfs.insert(std::initializer_list<Foo>());
+  bfs.insert(bar, std::initializer_list<Foo>());
+
+  bfs.erase(foo);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfs.erase(bfs.begin());
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  bfs.erase(bfs.begin(), bfs.end());
+}
+
+void TestFollySortedVectorMap() {
+  folly::sorted_vector_map<Foo, int> fsvm;
+  std::pair<Foo, int> foo(Foo(), 13);
+
+  fsvm.insert(foo);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvm.insert(std::move(foo));
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvm.insert(fsvm.begin(), foo);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvm.insert(fsvm.begin(), std::move(foo));
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvm.insert(fsvm.begin(), fsvm.end());
+  fsvm.insert(std::initializer_list<std::pair<Foo, int>>());
+
+  fsvm.emplace(Foo(), 13);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvm.emplace(foo);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvm.emplace(std::move(foo));
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvm.emplace_hint(fsvm.begin(), Foo(), 13);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvm.emplace_hint(fsvm.begin(), foo);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvm.emplace_hint(fsvm.begin(), std::move(foo));
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvm.erase(Foo());
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvm.erase(fsvm.begin());
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvm.erase(fsvm.begin(), fsvm.end());
+}
+
+void TestFollySortedVectorSet() {
+  folly::sorted_vector_set<Foo> fsvs;
+  Foo foo;
+
+  fsvs.insert(foo);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvs.insert(std::move(foo));
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvs.insert(fsvs.begin(), foo);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvs.insert(fsvs.begin(), std::move(foo));
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvs.insert(fsvs.begin(), fsvs.end());
+  fsvs.insert(std::initializer_list<Foo>());
+
+  fsvs.emplace();
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvs.emplace(foo);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvs.emplace(std::move(foo));
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvs.emplace_hint(fsvs.begin());
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvs.emplace_hint(fsvs.begin(), foo);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvs.emplace_hint(fsvs.begin(), std::move(foo));
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvs.erase(foo);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvs.erase(fsvs.begin());
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  fsvs.erase(fsvs.begin(), fsvs.end());
+}
+
+struct A {};
+struct B : A {};
+
+static int key = 13;
+static int value = 31;
+
+void TestPossibleFalseNegatives() {
+  folly::sorted_vector_set<long> fsvs;
+  fsvs.insert(5);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  folly::sorted_vector_set<A> fsvs2;
+  fsvs2.insert(B());
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  folly::sorted_vector_set<std::pair<int, int>> fsvs3;
+  fsvs3.insert(std::pair<int, int>(13, 31));
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  using CustomSortedVectorMapType = folly::sorted_vector_map<int, int>;
+  CustomSortedVectorMapType map;
+  map.insert(std::pair<int, int>(5, 5));
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  folly::sorted_vector_map<int, int>* fsvmp = new folly::sorted_vector_map<int, int>;
+  fsvmp->emplace(std::move(key), value);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  (&(*fsvmp))->emplace(std::move(key), value);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+  auto& fsvmr = *fsvmp;
+  fsvmr.emplace(key, value);
+  // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+}