Why doesn't `std::set::find` accept arguments which might be accepted by `Compare` type?

Question

Disclamer: I know, that using std::map solves this problem, but it is not very clean to initialize.

The problem:
Imagine you have an array of large PODs which are rather expencive copy:

struct large_pod
{
   size_t id;
// a lot of members
};

So one would want to use a mapping to an intermediate associative container of pointers/references to large_pod in order to reduce algorithim complexity when searching.

std::vector<large_pod> original{};

std::vector<size_t> ids = ids_to_work_on();

// would rather have an std::set
auto queryMap = map_by<large_pod::id>(original);

for (const auto &i : ids)
{
   auto& pod = queryMap.find(i); // this will not compile, because T is not the same as Key, which is large_pod
}

So I wonder, why doesn't std::set allow to use something other than the Key if the Compare will compile?


struct compare_id
{

  // basic case
  bool operator()(const large_pod& lhs, const large_pod& rhs) const
  {
     return lhs.id < rhs.id;
  }

  // special cases
  bool operator()(const large_pod& pod, size_t id) const
  {
     return pod.id < id;
  }

  bool operator()(size_t id, const large_pod& pod) const
  {
     return id < pod.id;
  }

};

Of course, using std::map<size_t, const large_pod*> would work, but it requires explicit initialization and introducing redundancy (map[pod.id] = &pod);

This doesn't address the question, but algorithmic complexity addresses the **number** of operations, not how expensive the operations are. Faster copying doesn't reduce algorithmic complexity, although it does make any algorithm that copies objects run faster. — Pete Becker, Feb 03 '22 at 16:52
@TedLyngmo basically it is a *magic* function that should return an `std::set`. I don't have an implementation yet. I can later provide it for `std::map` — Sergey Kolesnik, Feb 03 '22 at 16:59
Did you try adding `using is_transparent = size_t;` to `compare_id`? [example](https://godbolt.org/z/Wr7GMTMMj) — Ted Lyngmo, Feb 03 '22 at 17:00
@PeteBecker both `std::map` and `std::set` has log(n) for lookup. The question is about using `std::set` — Sergey Kolesnik, Feb 03 '22 at 17:00
@SergeyKolesnik -- I was responding to "So one would want to use a mapping to an intermediate structure of pointers/references to large_pod **in order to reduce algorithim complexity** when searching." [emphasis added] Switching to pointers or references to large_pod doesn't affect algorithmic complexity. — Pete Becker, Feb 03 '22 at 17:24
@PeteBecker that means I had bad phrasing. What I meant is *using an associative container like `std::map` or `std::set` reduces algorithmic complexity to log(n) for lookups, but map introduces redundancy for Keys*. — Sergey Kolesnik, Feb 03 '22 at 17:31
@TedLyngmo your example is very helpful, since `std::set::find` does not go into detail about using `is_transparent`. It just shows an example with `std::less<>` and global functions... — Sergey Kolesnik, Feb 03 '22 at 17:36
@SergeyKolesnik Glad to hear it. _"does not go into detail"_ - No, and the `find` overloads taking a type other than _Key_ (overloads 3 and 4 on cppreference) was added in C++14, so they haven't been there forever. — Ted Lyngmo, Feb 03 '22 at 17:41
@TedLyngmo it seems like the underlying type of `is_transparent` is **irrelevant** and might as well be `void`. Also there might be as many equivalent types as you want. I think in that case you can go on with just one `template bool operator(const T&, const E&)`. It is sad, however, that you can't declare a typedef within a lambda — Sergey Kolesnik, Feb 03 '22 at 17:51
@SergeyKolesnik _"irrelevant"_ - Oh, that was more than I knew. _"typedef within a lambda"_ - True, but you could make a helper class to pack your lambdas in [example](https://godbolt.org/z/s1E58PTYa) — Ted Lyngmo, Feb 03 '22 at 18:13

Why doesn't `std::set::find` accept arguments which might be accepted by `Compare` type?

0 Answers0