)]}'
{
  "commit": "6fc5746a5e809e4f22f343eb51bb963cd151ee7e",
  "tree": "ec68aeae5431770ce47654d9eb7e707b4bb70adf",
  "parents": [
    "fda1343ae84090a78a40a7c9b34b11c146985061"
  ],
  "author": {
    "name": "Nathan Myers",
    "email": "ncm@cantrip.org",
    "time": "Thu Jun 04 23:42:11 2026 -0400"
  },
  "committer": {
    "name": "Nathan Myers",
    "email": "ncm@cantrip.org",
    "time": "Wed Jul 08 16:32:15 2026 -0400"
  },
  "message": "libstdc++: make trees hetero equal_range O(lg n) [PR118851]\n\nAs shipped, the heterogeneous-key members equal_range of rbtree\ncontainers map, multimap, set, and multiset walk the entire range\ncalling the predicate, in violation of the requirement for\nlogarithmic complexity. This patch revises them to match the\nbehavior of the non-heterogeneous multimap and multiset members,\nand provides tests to verify it.\n\nlibstdc++-v3/Changelog:\n\tPR libstdc++/118851\n\t* include/bits/stl_tree.h (_M_equal_range_tr): Rewrite to match\n\tnon-heterogeneous equal_range implementation.\n\t* testsuite/23_containers/map/operations/hetero/equal_range.cc:\n\tNew test.\n\t* testsuite/23_containers/multimap/operations/hetero/equal_range.cc:\n\tSame.\n\t* testsuite/23_containers/multiset/operations/hetero/equal_range.cc:\n\tSame.\n\t* testsuite/23_containers/set/operations/hetero/equal_range.cc: Same.\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "a7781b72114a48dbe0cb0b4d3cf3a352251390f3",
      "old_mode": 33188,
      "old_path": "libstdc++-v3/include/bits/stl_tree.h",
      "new_id": "313ee8160023d09aed85da20fe5e6eabe51c7a7d",
      "new_mode": 33188,
      "new_path": "libstdc++-v3/include/bits/stl_tree.h"
    },
    {
      "type": "add",
      "old_id": "0000000000000000000000000000000000000000",
      "old_mode": 0,
      "old_path": "/dev/null",
      "new_id": "3ed6ff62ba87b01e94cf922d09d528a0c77a24c4",
      "new_mode": 33188,
      "new_path": "libstdc++-v3/testsuite/23_containers/map/operations/hetero/equal_range.cc"
    },
    {
      "type": "add",
      "old_id": "0000000000000000000000000000000000000000",
      "old_mode": 0,
      "old_path": "/dev/null",
      "new_id": "490407c244dab31bc835e3b8bfb8b6fdb76afdac",
      "new_mode": 33188,
      "new_path": "libstdc++-v3/testsuite/23_containers/multimap/operations/hetero/equal_range.cc"
    },
    {
      "type": "add",
      "old_id": "0000000000000000000000000000000000000000",
      "old_mode": 0,
      "old_path": "/dev/null",
      "new_id": "a9a479a78cd107607eb362ea6793fd3b51ee431f",
      "new_mode": 33188,
      "new_path": "libstdc++-v3/testsuite/23_containers/multiset/operations/hetero/equal_range.cc"
    },
    {
      "type": "add",
      "old_id": "0000000000000000000000000000000000000000",
      "old_mode": 0,
      "old_path": "/dev/null",
      "new_id": "1c9e7a3351815a7118c703fd8ba96db4618c0a01",
      "new_mode": 33188,
      "new_path": "libstdc++-v3/testsuite/23_containers/set/operations/hetero/equal_range.cc"
    }
  ]
}