Skip to content

[libc++] Optimizations for algorithms on flat containers #132459

Open
@ldionne

Description

@ldionne

We could do something like this:

template <class Iterator, class Pred>
  requires same_as<Pred, _Compare> &&
           (__desugars_to_v<__less_tag, _Pred, _Reference, _Reference> ||
            __desugars_to_v<__greater_tag, _Pred, _Reference, _Reference> || ...)
bool is_sorted(__ra_iterator<flat_set<_ValueType, _Compare, _Container>, typename _Container::iterator> first,
               __ra_iterator<flat_set<_ValueType, _Compare, _Container>, typename _Container::iterator> last,
               Pred pred) {
  return true;
}

Other things we probably want to do if we go down that route:

  • We might want a typedef for __flat_set_iterator<...> which expands to __ra_iterator?
  • We might want to have some sort of trait instead of matching flat_set directly, maybe something like __is_sorted_with_respect_to<Iterator, Predicate> that we can then specialize for any container that is sorted as an invariant?
  • In std::flat_set::insert(Iter, Iter) & friends, we could add std::sorted_unique_t when we see that Iter is a fellow flat_set iterator (or any kind of sorted iterator, really).

Metadata

Metadata

Assignees

Labels

libc++libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi.performance

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions