How to check if a class is fully compliant with a given set of traits?

Question

Say I'm writing a custom container and want to provide a RandomAccessIterator for it.

template<class T>
class MyContainer
{
public:
    class RandomAccessIterator
    {
         /*
             ... operators, constructors, etc...
         */
    };
    RandomAccessIterator begin();
    RandomAccessIterator end();

/*
    ... class implementation ...
*/
};

Now, how can I check that the iterator I've just written is 100% compatible with standard library algorithms? One obvious solution is to simply try one:

MyContainer<int> list;
std::sort(list.begin(), list.end());

...and verify whether it compiles and produces desired results.

With that in mind, I am not sure if it's a reliable "trait compliance" test and that's exactly what this question is about. Will the compiler always complain if I forget to provide any of the required methods/operators? If not, what would be the best way to make sure that my types fully implement given traits?

@Edit: the post no longer refers to the standard library as to "the STL", which was incorrect as pointed out in the comments.

Answer 1

I would say it is possible based on C++20 iterator concepts¹:

template<std::input_iterator T>
using validate_input_iterator = T;

This would fail compilation:

struct meow {
    struct iterator{};
private:
    typedef validate_input_iterator<iterator> v; // fails here
};

However the below compiles:

struct meow: private std::string { // string has an input iterator
    // struct iterator{};
private:
    typedef validate_input_iterator<iterator> v; // passes!
};

https://godbolt.org/z/5DwiaT

If you actually want to check you implemented the required functions and traits correctly, this would of course couldn't be checked at compile time and requires writing some tests.

---

Syntactic requirements vs. Semantic requirements

Note that concepts, and specifically iterator concepts, declare both syntactic requirements and semantic requirements. While the syntactic requirements, stated based on the requires syntax, can be statically checked at compile time, the semantic requirements that are merely "notes" to be followed by that type, are not and cannot be checked at compile time. On the other hand algorithms and compiler decisions may be based on the fact that a type said to implement a specific concept follows its semantic requirements.

For example, bidirectional_­iterator is defined as:

23.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]

1. The bidirectional_­iterator concept adds the ability to move an iterator backward as well as forward.

     template<class I>
       concept bidirectional_iterator =
         forward_iterator<I> &&
         derived_from<ITER_CONCEPT(I), bidirectional_iterator_tag> &&
         requires(I i) {
           { --i } -> same_as<I&>;
           { i-- } -> same_as<I>;
         };

2. A bidirectional iterator r is decrementable if and only if there exists some q such that ++q == r. Decrementable iterators r shall be in the domain of the expressions --r and r--.

3. Let a and b be equal objects of type I. I models bidirectional_­iterator only if:

   (3.1) If a and b are decrementable, then all of the following are true:

   (3.1.1) addressof(--a) == addressof(a)

   (3.1.2) bool(a-- == b)

   (3.1.3) after evaluating both a-- and --b, bool(a == b) is still true

   (3.1.4) bool(++(--a) == b)

   (3.2) If a and b are incrementable, then bool(--(++a) == b).

For a given iterator said to implement bidirectional_­iterator as seen above, bullet #1 can be checked at compile time while bullets #2 and #3 cannot.

---

_{¹ Should also be doable pre C++20 implementing your own SFINAE restricted template in a similar manner}

Answer 2

I am not sure if it's a reliable "trait compliance" test

Checking if your iterator works with std::sort is not a reliable test of the iterator. The implementation of std::sort will depend on some (unknown) subset of the requirements imposed by the standard, but not on all.

Will the compiler always complain if I forget to provide any of the required methods/operators?

No, it will not. It might even not complain with one version of the standard library but with another version / implementation; if the code you're using your iterator with has changed and depends on different requirements imposed by the standard.

If not, what would be the best way to make sure that my types fully implement given traits?

You go through the C++ standard and note down each and every behavior it describes about the iterator category you want to implement. Then you devise test cases for each of these requirements which - ideally - rely only on that one requirement.

Finally you test your iterator as well as some standard iterators (e.g. from std::vector) with these test cases. Ideally using multiple different implementations and versions of the standard library.

Last but not least it would be awesome if you'd made this work open source so that others can benefit from it (and contribute to it).