Comment by virtualritz

Your mileage may vary.

I tested this on a 3D boolean mesh kernel I am working on (this is swapping out std::BTreeMap, no other code changes):

  ┌────────────────────────────────────┬──────────────────────┐
  │       bench 96..1536 faces         │        change        │
  ├────────────────────────────────────┼──────────────────────┤
  │ union/difference,                  │ +11% to +21% slower  │
  ├────────────────────────────────────┼──────────────────────┤
  │ intersection stage,                │ +16% to +34% slower  │
  └────────────────────────────────────┴──────────────────────┘

Then I thought, maybe this shines when you use big maps. I.e. more dense/complext meshes.

So I used one of my test fixtures, a Nefretiti bust scan with a million vertex IDs:

  ┌──────────────────────────────────────┬───────┬────────┐
  │     cage op (seconds, best of 3)     │  std  │ bbtree │
  ├──────────────────────────────────────┼───────┼────────┤
  │ difference                           │ 84.2  │ 83.0   │
  ├──────────────────────────────────────┼───────┼────────┤
  │ union                                │ 83.2  │ 85.6   │
  ├──────────────────────────────────────┼───────┼────────┤
  │ intersection                         │ 61.3  │ 67.1   │
  ├──────────────────────────────────────┼───────┼────────┤
  │ limit-surface difference (best of 2) │ 123.9 │ 147.2  │
  └──────────────────────────────────────┴───────┴────────┘

I.e. a lot of the claims the post makes probably only hold under a specific and possibly narrow set of use cases the author tested agains.

std::BTreeMap must hold ideally hold up well under any use case for such a map. That always means compromises must be made.