357.md

Info

• Did you know that C++23 added standard support for flat_map?

  • https://wg21.link/P0429

Example

int main() {
  stdext::flat_map<int, int> fm{};
  fm.emplace(1, 2);
  fm.emplace(3, 4);
  assert(fm.size() == 2);
  assert(fm[1]==2 and fm[2]==3);
}

https://godbolt.org/z/v7Tf1vj48

Puzzle

• Can you implement benchmark between std::map, std::unordered_map, and std::flat_map?

  • https://quick-bench.com/

Solutions

constexpr int N = 2048;

template <template <class...> typename MapType>
constexpr auto get_values() {
    MapType<int, int> ret;
    for (auto i = 0; i < N; ++i) {
        ret.emplace(std::pair{i, i});
    }
    return ret;
}

const auto values = get_values<std::map>();
void FlatMapInsertion(benchmark::State& state) {
    stdext::flat_map<int, int> m;
    for (auto _ : state) {
        state.PauseTiming();
        m.clear();
        state.ResumeTiming();
        m.insert(values.cbegin(), values.cend());
    }
}

void MapInsertion(benchmark::State& state) {
    std::map<int, int> m;
    for (auto _ : state) {
        state.PauseTiming();
        m.clear();
        state.ResumeTiming();
        m.insert(values.cbegin(), values.cend());
    }
}

void UnorderedMapInsertion(benchmark::State& state) {
    std::unordered_map<int, int> m;
    for (auto _ : state) {
        state.PauseTiming();
        m.clear();
        state.ResumeTiming();
        m.insert(values.cbegin(), values.cend());
    }
}

void FlatMapLookup(benchmark::State& state) {
    const auto m = get_values<stdext::flat_map>();
    for (auto _ : state) {
        for (auto i = 0; i < N; ++i) {
            auto is_present = m.contains(i);
            benchmark::DoNotOptimize(is_present);
        }
    }
}

void MapLookup(benchmark::State& state) {
    const auto m = get_values<std::map>();
    for (auto _ : state) {
        for (auto i = 0; i < N; ++i) {
            auto is_present = m.contains(i);
            benchmark::DoNotOptimize(is_present);
        }
    }
}

void UnorderedMapLookup(benchmark::State& state) {
    const auto m = get_values<std::unordered_map>();
    for (auto _ : state) {
        for (auto i = 0; i < N; ++i) {
            auto is_present = m.contains(i);
            benchmark::DoNotOptimize(is_present);
        }
    }
}

https://quick-bench.com/q/6MCXQDX5VGG2FOt0sO8TWjwhz9A