Arthur O'Dwyer wrote:
> On Mon, Jan 22, 2024 at 11:03 AM Phil Endecott via Std-Proposals <
> std-proposals_at_[hidden]> wrote:
>> Ugh, I feel a bit queasy with the idea of doing a binary search through a
>> std::set without using its (private) left/right/parent pointers to do so.
>> Slightly more queasy than finding the size of a std::list without using its
>> size() member. Here's an idea, add a std::set::lower_bound overload that
>> takes an iterator pair (or a single begin iterator); maybe call it a hint,
>> like std::set::insert?
>
> Off the top of my head, I think that might not be efficiently
> implementable. IIRC, the library's red-black trees don't have *parent*
> pointers; they have *next/prev* pointers (for iterator traversal).

I believe you have remembered that wrongly.

Thinking more about this, I believe what's really needed is a std::set-specific
set-intersection algorithm; either a member of std::set or a friend function,
maybe even a friend overload of std::(ranges?)::set_intersection. Using the
tree structure of the set is the right way to do this algorithmically.
Everything else is a hack to work around the fact that the tree
structure is
private.

Sketch of set intersection of two binary trees:

void set_intersection(const tree& a, const tree& b, tree-or-other& out)
{
   if (a.empty() || b.empty()) return;

   // if (a.back() < b.front() || b.back() < a.front()) return;

   if (a.root() < b.root()) {
     set_intersection(a, b.left_subtree(), out);
     set_intersection(a.right_subtree(), b.right_subtree(), out);

   } else if (a.root() == b.root()) {
     set_intersection(a.left_subtree(), b.left_subtree(), out);
     out.insert_at_end(a.root());
     set_intersection(a.right_subtree(), b.right_subtree(), out);

   } else { // a.root() > b.root()
     set_intersection(a.left_subtree(), b, out);
     set_intersection(a.right_subtree(), b.right_subtree(), out);
   }
}


Regards, Phil.