void nextWhileLess(InfoType* info, size_t* idx) const noexcept {
        // unrolling this by hand did not bring any speedups.
        while (*info < mInfo[*idx]) {
            next(info, idx);
        }
    }
 
    // Finds key, and if not already present prepares a spot where to pot the key & value.
    // This potentially shifts nodes out of the way, updates mInfo and number of inserted
    // elements, so the only operation left to do is create/assign a new node at that spot.
    template <typename OtherKey>
    std::pair<size_t, InsertionState> insertKeyPrepareEmptySpot(OtherKey&& key) {
        for (int i = 0; i < 256; ++i) {
            size_t idx{};
            InfoType info{};
            // 找到對(duì)應(yīng)key的info
            keyToIdx(key, &idx, &info);
            // 跳過(guò)distance大于自己的
            nextWhileLess(&info, &idx);
 
            // while we potentially have a match
            while (info == mInfo[idx]) {
                // distance相等的情況需要判key是不是已經(jīng)存在了
                if (WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) {
                    // key already exists, do NOT insert.
                    // see http://en.cppreference.com/w/cpp/container/unordered_map/insert
                    return std::make_pair(idx, InsertionState::key_found);
                }
                next(&info, &idx);
            }
 
            // unlikely that this evaluates to true
            if (ROBIN_HOOD_UNLIKELY(mNumElements >= mMaxNumElementsAllowed)) {
                if (!increase_size()) {
                    return std::make_pair(size_t(0), InsertionState::overflow_error);
                }
                continue;
            }
 
            // key not found, so we are now exactly where we want to insert it.
            // 此時(shí)的位置原來(lái)的distance一定是小于當(dāng)前的distance
            auto const insertion_idx = idx;
            auto const insertion_info = info;
            if (ROBIN_HOOD_UNLIKELY(insertion_info + mInfoInc > 0xFF)) {
                mMaxNumElementsAllowed = 0;
            }
 
            // find an empty spot
            // 找到下一個(gè)空白的位置
            while (0 != mInfo[idx]) {
                next(&info, &idx);
            }
            // 如果當(dāng)前的位置不是空白的，則把當(dāng)前位置->下一個(gè)空白位置的所有元素往后移
            if (idx != insertion_idx) {
                shiftUp(idx, insertion_idx);
            }
            // put at empty spot
            mInfo[insertion_idx] = static_cast<uint8_t>(insertion_info);
            ++mNumElements;
            return std::make_pair(insertion_idx, idx == insertion_idx
                                                     ? InsertionState::new_node
                                                     : InsertionState::overwrite_node);
        }
 
        // enough attempts failed, so finally give up.
        return std::make_pair(size_t(0), InsertionState::overflow_error);
    }
 
 
    template <typename OtherKey, typename... Args>
    std::pair<iterator, bool> try_emplace_impl(OtherKey&& key, Args&&... args) {
        ROBIN_HOOD_TRACE(this)
        auto idxAndState = insertKeyPrepareEmptySpot(key);
        switch (idxAndState.second) {
        case InsertionState::key_found:
            break;
 
        case InsertionState::new_node:
            ::new (static_cast<void*>(&mKeyVals[idxAndState.first])) Node(
                *this, std::piecewise_construct, std::forward_as_tuple(std::forward<OtherKey>(key)),
                std::forward_as_tuple(std::forward<Args>(args)...));
            break;
 
        case InsertionState::overwrite_node:
            mKeyVals[idxAndState.first] = Node(*this, std::piecewise_construct,
                                               std::forward_as_tuple(std::forward<OtherKey>(key)),
                                               std::forward_as_tuple(std::forward<Args>(args)...));
            break;
 
        case InsertionState::overflow_error:
            throwOverflowError();
            break;
        }
 
        return std::make_pair(iterator(mKeyVals + idxAndState.first, mInfo + idxAndState.first),
                              InsertionState::key_found != idxAndState.second);
    }

    T* allocate() {
        T* tmp = mHead;
        if (!tmp) {
            tmp = performAllocation();
        }
 
        mHead = *reinterpret_cast_no_cast_align_warning<T**>(tmp);
        return tmp;    }
 
    ROBIN_HOOD(NOINLINE) T* performAllocation() {
        size_t const numElementsToAlloc = calcNumElementsToAlloc();
 
        // alloc new memory: [prev |T, T, ... T]
        size_t const bytes = ALIGNMENT + ALIGNED_SIZE * numElementsToAlloc;
        ROBIN_HOOD_LOG("std::malloc " << bytes << " = " << ALIGNMENT << " + " << ALIGNED_SIZE
                                      << " * " << numElementsToAlloc)
        add(assertNotNull<std::bad_alloc>(std::malloc(bytes)), bytes);
        return mHead;
    }
 
 
    ROBIN_HOOD(NODISCARD) size_t calcNumElementsToAlloc() const noexcept {
        auto tmp = mListForFree;
        size_t numAllocs = MinNumAllocs;
 
        while (numAllocs * 2 <= MaxNumAllocs && tmp) {
            auto x = reinterpret_cast<T***>(tmp);
            tmp = *x;
            numAllocs *= 2;
        }
 
        return numAllocs;
    }

using unordered_map =
    detail::Table<sizeof(robin_hood::pair<Key, T>) <= sizeof(size_t) * 6 &&
                      std::is_nothrow_move_constructible<robin_hood::pair<Key, T>>::value &&
                      std::is_nothrow_move_assignable<robin_hood::pair<Key, T>>::value,
                  MaxLoadFactor100, Key, T, Hash, KeyEqual>;
 
template <bool IsFlat, size_t MaxLoadFactor100, typename Key, typename T, typename Hash,
          typename KeyEqual>
class Table
    : public WrapHash<Hash>,
      public WrapKeyEqual<KeyEqual>,
      detail::NodeAllocator<
          typename std::conditional<
              std::is_void<T>::value, Key,
              robin_hood::pair<typename std::conditional<IsFlat, Key, Key const>::type, T>>::type,
          4, 16384, IsFlat> {}

//
// Created by victorika on 2022/10/14.
//
 
#include "absl/container/flat_hash_map.h"
#include "absl/container/node_hash_map.h"
#include <vector>
#include <cstdio>
#include <iostream>
 
#define ANKERL_NANOBENCH_IMPLEMENT
#include "riemann/3rd/nanobench/nanobench.h"
#include "robin_hood.h"
 
/**
 * 測(cè)試結(jié)構(gòu)
 */
struct TestStruct {
  uint32_t* a;
  std::vector<uint32_t> b, c, d;
  std::string e, f, g;
  uint32_t h, i, j;
};
 
void TestEmplace() {
  ankerl::nanobench::Bench bench;
  bench.minEpochIterations(50);
  bench.title("Benchmarking rare value emplace");
  bench.run("absl_flat", [&] {
    absl::flat_hash_map<uint32_t, TestStruct> m;
    for (int i = 0; i < 10000; i++) {
      m.try_emplace(i, TestStruct());
    }
  });
 
  bench.run("absl_flat_and_set_value_pointer",  [&] {
    absl::flat_hash_map<uint32_t, std::unique_ptr<TestStruct>> m;
    for (int i = 0; i < 10000; i++) {
      m.try_emplace(i, std::make_unique<TestStruct>());
    }
  });
 
  bench.run("absl_node", [&] {
    absl::node_hash_map<uint32_t, TestStruct> m;
    for (int i = 0; i < 10000; i++) {
      m.try_emplace(i, TestStruct());
    }
  });
  bench.run("absl_flat_reserve", [&] {
    absl::flat_hash_map<uint32_t, TestStruct> m;
    m.reserve(20000);
    for (int i = 0; i < 10000; i++) {
      m.try_emplace(i, TestStruct());
    }
  });
 
  bench.run("absl_flat_and_set_value_pointer_reserve",  [&] {
    absl::flat_hash_map<uint32_t, std::unique_ptr<TestStruct>> m;
    m.reserve(20000);
    for (int i = 0; i < 10000; i++) {
      m.try_emplace(i, std::make_unique<TestStruct>());
    }
  });
 
  bench.run("absl_node_reserve", [&] {
    absl::node_hash_map<uint32_t, TestStruct> m;
    m.reserve(20000);
    for (int i = 0; i < 10000; i++) {
      m.try_emplace(i, TestStruct());
    }
  });
 
 
  bench.run("robinhood_flat", [&] {
    robin_hood::unordered_flat_map<uint32_t, TestStruct> m;
    for (int i = 0; i < 10000; i++) {
      m.try_emplace(i, TestStruct());
    }
  });
 
  bench.run("robinhood_flat_and_set_value_pointer",  [&] {
    robin_hood::unordered_flat_map<uint32_t, std::unique_ptr<TestStruct>> m;
    for (int i = 0; i < 10000; i++) {
      m.try_emplace(i, std::make_unique<TestStruct>());
    }
  });
 
  bench.run("robinhood_node", [&] {
    robin_hood::unordered_node_map<uint32_t, TestStruct> m;
    for (int i = 0; i < 10000; i++) {
      m.try_emplace(i, TestStruct());
    }
  });
  bench.run("robinhood_flat_reserve", [&] {
    robin_hood::unordered_flat_map<uint32_t, TestStruct> m;
    m.reserve(20000);
    for (int i = 0; i < 10000; i++) {
      m.try_emplace(i, TestStruct());
    }
  });
 
  bench.run("robinhood_flat_and_set_value_pointer_reserve",  [&] {
    robin_hood::unordered_flat_map<uint32_t, std::unique_ptr<TestStruct>> m;
    m.reserve(20000);
    for (int i = 0; i < 10000; i++) {
      m.try_emplace(i, std::make_unique<TestStruct>());
    }
  });
 
  bench.run("robinhood_node_reserve", [&] {
    robin_hood::unordered_node_map<uint32_t, TestStruct> m;
    m.reserve(20000);
    for (int i = 0; i < 10000; i++) {
      m.try_emplace(i, TestStruct());
    }
  });
}
 
void TestSearch() {
  absl::flat_hash_map<uint32_t, TestStruct> m1;
  absl::flat_hash_map<uint32_t, std::unique_ptr<TestStruct>> m2;
  absl::node_hash_map<uint32_t, TestStruct> m3;
 
  robin_hood::unordered_flat_map<uint32_t, TestStruct> m4;
  robin_hood::unordered_flat_map<uint32_t, std::unique_ptr<TestStruct>> m5;
  robin_hood::unordered_node_map<uint32_t, TestStruct> m6;
  for (int i = 0; i < 10000; i++) {
    m1.try_emplace(i, TestStruct());
    m2.try_emplace(i, std::make_unique<TestStruct>());
    m3.try_emplace(i, TestStruct());
 
    m4.try_emplace(i, TestStruct());
    m5.try_emplace(i, std::make_unique<TestStruct>());
    m6.try_emplace(i, TestStruct());
  }
  ankerl::nanobench::Bench bench;
  bench.minEpochIterations(50);
  std::vector<uint32_t> key_v;
  key_v.resize(10000);
  bench.title("Benchmarking rare value search");
  bench.run("absl_flat_normal", [&] {
    for (int i = 0; i < 10000; i++) {
      auto it = m1.find(i);
      key_v[i] = it->first;
    }
  });
  bench.run("absl_flat_unique_ptr", [&] {
    for (int i = 0; i < 10000; i++) {
      auto it = m2.find(i);
      key_v[i] = it->first;
    }
  });
  bench.run("absl_node", [&] {
    for (int i = 0; i < 10000; i++) {
      auto it = m3.find(i);
      key_v[i] = it->first;
    }
  });
 
  bench.run("robinhood_flat_normal", [&] {
    for (int i = 0; i < 10000; i++) {
      auto it = m4.find(i);
      key_v[i] = it->first;
    }
  });
  bench.run("robinhood_unique_ptr", [&] {
    for (int i = 0; i < 10000; i++) {
      auto it = m5.find(i);
      key_v[i] = it->first;
    }
  });
  bench.run("robinhood_node", [&] {
    for (int i = 0; i < 10000; i++) {
      auto it = m6.find(i);
      key_v[i] = it->first;
    }
  });
}
 
void TestIterator() {
  absl::flat_hash_map<uint32_t, TestStruct> m1;
  absl::flat_hash_map<uint32_t, std::unique_ptr<TestStruct>> m2;
  absl::node_hash_map<uint32_t, TestStruct> m3;
 
  robin_hood::unordered_flat_map<uint32_t, TestStruct> m4;
  robin_hood::unordered_flat_map<uint32_t, std::unique_ptr<TestStruct>> m5;
  robin_hood::unordered_node_map<uint32_t, TestStruct> m6;
  for (int i = 0; i < 10000; i++) {
    m1.try_emplace(i, TestStruct());
    m2.try_emplace(i, std::make_unique<TestStruct>());
    m3.try_emplace(i, TestStruct());
 
    m4.try_emplace(i, TestStruct());
    m5.try_emplace(i, std::make_unique<TestStruct>());
    m6.try_emplace(i, TestStruct());
  }
  ankerl::nanobench::Bench bench;
  bench.minEpochIterations(50);
  std::vector<uint32_t> key_v;
  key_v.resize(10000);
  bench.title("Benchmarking rare value iterator");
  bench.run("absl_flat_normal", [&] {
    int i = 0;
    for (auto &[key, value] : m1) {
      key_v[i] = key;
    }
  });
  bench.run("absl_flat_unique_ptr", [&] {
    int i = 0;
    for (auto &[key, value] : m2) {
      key_v[i] = key;
    }
  });
  bench.run("absl_node", [&]() {
    int i = 0;
    for (auto &[key, value] : m3) {
      key_v[i] = key;
    }
  });
 
  bench.run("robinhood_flat_normal", [&] {
    for (int i = 0; i < 10000; i++) {
      auto it = m4.find(i);
      key_v[i] = it->first;
    }
  });
  bench.run("robinhood_flat_unique_ptr", [&] {
    for (int i = 0; i < 10000; i++) {
      auto it = m5.find(i);
      key_v[i] = it->first;
    }
  });
  bench.run("robinhood_node", [&] {
    for (int i = 0; i < 10000; i++) {
      auto it = m6.find(i);
      key_v[i] = it->first;
    }
  });
}
 
int main() {
  std::cout << "size=" << sizeof(TestStruct) << std::endl;
  TestEmplace();
  TestSearch();
  TestIterator();
}