Comparator aware `flat_set` implementation

Question

I am currently implementing a flat_map like container in C++, and had problems with the comparator used. Thus, I reduced it to the bare minimum which I will present here. (In particular, my code here implements a set instead of a map).

template< typename T, typename Compare = std::less<T> >
class flat_set : private Compare {
public:
 flat_set() = default;
 flat_set( std::initializer_list<T> && init, const Compare & compare_ = Compare() ) 
 : Compare(compare_), values{init}
 {}
 template< typename V >
 [[nodiscard]] bool contains( const V & value ) const noexcept {
 auto it = std::lower_bound( values.begin(), values.end(), value, value_comp_ref() );
 return it != values.end() && eq( value, *it );
 }
 
 [[nodiscard]] Compare value_comp() const noexcept { return *this; } // NOLINT(cppcoreguidelines-slicing)
 [[nodiscard]] const Compare & value_comp_ref() const & noexcept { return *this; } // NOLINT(cppcoreguidelines-slicing)
 [[nodiscard]] Compare & value_comp_ref() & noexcept { return *this; } // NOLINT(cppcoreguidelines-slicing)
 
private:
 template< typename Lhs, typename Rhs >
 [[nodiscard]] bool lt( const Lhs & lhs, const Rhs & rhs ) const noexcept { // less than
 return Compare::operator()( lhs, rhs );
 }
 template< typename Lhs, typename Rhs >
 [[nodiscard]] bool eq( const Lhs & lhs, const Rhs & rhs ) const noexcept { // equivalent
 return (!lt( lhs, rhs )) && (!lt( rhs, lhs ));
 }
 
 std::vector< T > values;
};

and some test code:

int main() {
 flat_set< S, SComp > fs{S{3},S{2},S{1}};
 std::cout << fs.contains( S{2} );
 std::cout << fs.contains( 4 );
 
 auto v2 = fs.value_comp();
 std::cout << v2( S{3}, 2 ); 
 auto & v5 = fs.value_comp_ref();
 std::cout << v5( S{3}, 2 );
 auto & vtmp = flat_set< S, SComp >{S{4},S{3},S{2},S{1}}.value_comp_ref();
 std::cout << flat_set< S, SComp >{S{3},S{2},S{1}}.contains(2);
}

My questions are:

• Do I handle the comparator in a good way. In particular
  • I added the function value_comp_ref because I fear that, when I pass value_comp() to std::lower_bound I get unnecessary copies. Would this be true?
  • My workaround via value_comp_ref to pass the comparator to std::lower_bound actually seems very strange to me, but it was the easiest I could come up with. Which other solutions I could do here?
• Are my noexcept specifiers correct? Are the [[...]] tags ok?
• Is there a more concise way to implement my functions lt and eq?

I do not wish to get feedback onto

• the missing is_transparent tests
• Missing allocator support

• Davislor: I’m unclear what the goal of this is. What was your reason not to use the second template parameter of std::set?
• tommsch: What do you mean? I cant use std::set at all in my flat_map implemention (In particular, I even do not use std::vector there because I need it on Cuda).
• Davislor: I’m a bit confused about what kind of project this is and therefore what feedack you’re looking for. The title says this is a comparator-aware std::set, and it has the tag reinventing-the-wheel, but std::set is already comparator-aware.
• Davislor: Your latest comment also makes me wonder whether a std::vector overloaded with a different allocator could not be used for CUDA. If it can, that’s almost certainly the most practical solution.
• tommsch: 1) There is some strange misunderstanding here. I am reinventing-the-wheel, and therefor I am obviously do NOT want to use std::set in my code, because I want to reinvent it. 2) Regarding std::vector: Cuda has no std:: at all. In particular I cannot use a different allocator, because there even isnt a std::vector. 3) My question is: Is the comparator stuff implemented correctly.

Answer 1

Don't inherit from Compare

Your flat_set does not have an is-a relationship with Compare. Also, who knows what kind of type a caller will pass to flat_set? It might cause problems if you don't have control over it. So it is much better to have it as a private member variable.

If you are worried about it potentially taking up space, consider using C++20's [[no_unique_address]].

This also avoids needing the value_comp() functions to cast *this into a Compare.

Make use of std::binary_search()

std::lower_bound() does more work than necessary; you don't care that you get a reference to the lowest item with the given value, you only want to know whether it exists. It is annoying to use here, because the item returned might not even have the same value, so you need an extra check. Since you sorted the vector, std::binary_search() is doing exactly what you want: it just returns a bool indicating whether the given value was found.

As a bonus, there is no need at all any more for lt() and eq().

What about the allocator?

I do not wish to get feedback onto

• Missing allocator support

I am going to give that feedback anyway, since it might be useful for someone else.

Especially as you are using a flat set, I would think that the programmer is looking to optimize things as much as possible, in which case they might be thinking of using a custom allocator as well. So just like std::set, it might be nice to have a configurable allocator, which is passed to the std::vector used to store the elements.

Incorrect use of noexcept

A good way to check if you can make a function noexcept is to check if all the functions you are calling inside it are also noexcept. If not, it's probably a bad idea to make your function noexcept. Since std::lower_bound() is not noexcept, contains() should not be noexcept.

Also consider that someone might pass a Compare function that is not noexcept, and that since contains() is templated, there might be an implicit cast from V to T when passing value to the comparator, which in turn might also throw.

On the other hand, you could might make the default constructor noexcept, depending on whether Allocator() and Compare() are noexcept, as then the default constructor of std::vector is noexcept as well, at least since C++17, and you are also constructing a new Compare (regardless of whether you inherited from it or whether it's a member value).

You can make things constexpr in C++20

Since C++20, a lot of member functions of std::vector, including many of the constructors, are constexpr. Also, std::binary_search() is constexpr since C++20. So if you raise the minimum supported version of C++ for your code, you could make most of the API of flat_set constexpr as well.

Example code

Here is an example of your code with the above suggestions added, including the ones that only apply if C++20 can be used, although they can easily be removed if necessary.

template< typename T,
 typename Compare = std::less<T>,
 typename Allocator = std::allocator<T> >
class flat_set {
public:
 constexpr flat_set() noexcept(noexcept(Allocator()) && noexcept(Compare()))
 = default;
 constexpr flat_set( std::initializer_list<T> && init,
 const Compare & compare_ = Compare(),
 const Allocator& allocator = Allocator() ) 
 : compare(compare_), values{init, allocator}
 {}
 template< typename V >
 [[nodiscard]] constexpr bool contains( const V & value ) const {
 return std::binary_search( values.begin(), values.end(), value, compare );
 }
 
private:
 [[no_unique_address]] Compare compare{};
 std::vector< T, Allocator > values;
};

• tommsch: Thanks for your review. There are some good points. But you may fix an error: I use private inheritance, which does not mean is-a but is-implemented-in-terms-of.
• G. Sliepen: I don't think I made an error. While private inheritance can indeed be seen as an is-implemented-in-terms-of relationship, it still often is a bad idea if there is not a strong is-a relationship as well. Privately inheriting from a std::vector might have been better: your flat set is implemented as a vector, with some set-like public functions added.
• tommsch: Another remark to the allocator support. This I implemented by templatizing the underlying container.
• G. Sliepen: That's probably a good way to do it. Consider creating a new question on Code Review with the full implementation of your class flat_set.