I’m going to answer your questions first, then get into the actual code review.
Questions
How can “it” [the code/the design] be improved?
I’ll get into details in the review, but the broad answer to this question is: I don’t know.
The reason I don’t know is two-fold:
- you don’t provide even a single comment to explain the logic of what this code is doing; and
- you don’t provide even a single example to show what the intended usage is.
Without any clue about what the code is supposed to be doing or how it’s supposed to be used, how can anyone answer the question of whether it can be improved? Maybe it’s absolute perfection; maybe there is no possible way to make this code any better for what it was written for. Or maybe it’s the absolute worst possible solution for what it’s for. All that depends on what it’s for.
Obviously I’m going to try to review the code anyway, but to do so I’ll have to make a lot of assumptions about what you mean in your very brief, wildly unclear description of what the purpose of this wrapper is. I may guess wrong—that’s very likely, in fact—which means a lot of what I say may be incorrect, or even gibberish. For that I apologize, but it can’t be helped; I have to work with what I have.
So I guess one way to answer the question is: documentation… lots of documentation, and some example usage code. For something this small, there’s really no reason one couldn’t provide a complete, compile-able test program (even if you want to keep that algorithm secret; you could just include a stub or dummy implementation just for the purposes of illustration and testing).
Do I have to use the rule of 3 or 5 in such case?
Yes. You always✻ have to. That’s why they call it a “rule”.
✻ (Okay, technically the rule says “almost always”. But that just means that unless you’re 100% sure you don’t need to follow the rule, then the answer is yes.)
The only question is which rule: 3, 5, or 0?
Unfortunately, I can’t really give a coherent answer to that without making some guesses. So… just looking at what you’ve got there, and going by your description, I don’t… think… you need the rule of 3 or 5 (that is, you can use the rule of 0).
BUT…
I suspect that if the intended usage is more than what you explicitly say it is—that is, if I have to guess at practical usage of this wrapper, at least in my imagination—then the answer is that you do need to use the rule of 3 or 5. In fact, I think this wrapper is dangerously broken, and I’ll explain why in the review.
Does it make sense to create a generic iterator wrapper class and a specialization for each iterator type?
Absolutely. It’s not a bad idea at all. In fact, I wouldn’t be surprised if there were already “type-erased iterator” types out there. You could even make an argument for including one in the standard library. It would be hella useful.
Now, does it make sense to do it this way? Mm, maybe? Impossible to say for sure. For the general use case I’d say no, but for the specific use case of random-access iterators only—with some additional caveats on both the iterator and algorithm characteristics—then maybe.
So, onto the code review.
Code review
I’m going to skip the type traits, because I’ll talk about them when we get to the constructor that uses them.
template <typename T>
class WrapperRandomAccessIterator
Okay, so, here’s the first point of confusion. The type is called WrapperRandomAccessIterator… but it doesn’t look like you’re actually wrapping a random-access iterator. It looks like you’re trying to create a random-access iterator (actually, technically a contiguous iterator, but if you’re still stuck with C++11, then you don’t have that concept yet—seriously, though, who’s still using C++11 in 2020… almost 2021!) to a value sequence, and you’re trying to do so by stealing the value out from under a random-access iterator, and creating a pointer directly to it.
The point is… the name is misleading. This is not an iterator wrapper. It does not wrap an iterator. It just transforms an iterator to a pointer.
using this_type = WrapperRandomAccessIterator<T>;
As type aliases go, this is really… kinda useless. So long as you’re inside the class body, you can omit the template arguments. Sure WrapperRandomAccessIterator is a little longer than this_type… but you really shouldn’t need to repeat it so often that it becomes a problem.
using difference_type = std::ptrdiff_t;
using value_type = T;
using pointer = T*;
using reference = T&;
using iterator_category = std::random_access_iterator_tag;
These are all okay, but I would suggest defining value_type as:
using value_type = typename std::remove_cv<T>::type;
This is to bring it in line with the way people expect to use value_type. If you have a case like this…:
template <typename Iterator>
void max_value(Iterator first, Iterator last)
{
using type = typename iterator_traits<Iterator>::value_type;
type val = *first;
while (++first != last)
if (*first > val)
val = *first;
return val;
}
// used with:
const vector<string> vec{"string1", "string2", ... };
string v = max_value(vec.begin(), vec.end());
… you would normally expect this to work because val should be a copy of whatever *first references, and that copy is not const. (And that would be true if you’d just used auto instead of type.) But with your WrapperRandomAccessIterator, it won’t work, because value_type will be const string, not string.
(It’s correct to use plain T for pointer and reference, because that makes them const string* and const string&… which is what you want.)
template <typename RandomAccessIter, typename = typename
std::enable_if<iter_same_category<this_type, RandomAccessIter>() &&
iter_same_value_type<this_type, RandomAccessIter>()>::type>
constexpr explicit WrapperRandomAccessIterator(RandomAccessIter iter)
: ptr_(&*iter)
{}
Now, here’s where the problems start. What exactly is the purpose of iter_same_category and iter_same_value_type? Let’s look at the first one to show you what I mean:
iter_same_category<this_type, RandomAccessIter>
Now, this expands to:
std::is_same<
typename std::iterator_traits<this_type>::iterator_category,
typename std::iterator_traits<RandomAccessIter>::iterator_category>
And this_type is just WrapperRandomAcessIterator<T>. But why all the shenanigans going through iterator_traits to get the iterator_category of this_type? There’s no mystery; it’s iterator_category. typename std::iterator_traits<this_type>::iterator_category is always iterator_category.
So you could just do:
std::is_same<
iterator_category,
typename std::iterator_traits<RandomAccessIter>::iterator_category>
… and there’s no need for iter_same_category at all.
Same goes for iter_same_value_type.
That gives:
template <
typename RandomAccessIter,
typename = typename std::enable_if<
std::is_same<
iterator_category,
typename std::iterator_traits<RandomAccessIter>::iterator_category>()
&& std::is_same<
value_type,
typename std::iterator_traits<RandomAccessIter>::value_type>()>::type
>
constexpr explicit WrapperRandomAccessIterator(RandomAccessIter iter)
: ptr_(&*iter)
{}
Also, iterator_category is always going to be std::random_access_iterator_tag. That’s kinda the point of the class.
To be safe, it might be wise to use remove_cv on the RandomAccessIterator’s value_type. You shouldn’t need to, because most well-behaved containers and iterators will already have removed the const/volatile… but it pays to be safe, just in case. (I think, for example, there was a bug in the standard in C++11 that raw pointers didn’t behave properly.)
There is another nasty little bug lurking here with types that overload the address-of operator (unary operator&). To avoid that, you should use std::address_of(). Note that means you can’t be constexpr anymore in C++11, because address_of() wasn’t constexpr until C++17, but… 🤷🏼. Can’t be helped. constexpr wasn’t really well-supported in C++11.
But even in C++11, this can be noexcept, and there’s no reason it shouldn’t be.
operator* is okay, though it too should be noexcept. And it should probably be const. You’re not changing the iterator (wrapper) with this function, or with returned value (which is a pointer to something else entirely, not the iterator). That is why the next function is superfluous.
// Warning says "const has no effect on type reference"
const T& /*reference*/ operator*() const
{
return *ptr_;
}
Okay, to understand what this warning is telling you, I first have to break your misconception of const. const (and volatile, for that matter), does NOT apply to what’s on its RIGHT; it applies to what’s on its LEFT.
In other words, const T is WRONG. T const is correct. This is the subject of religious fights in the C++ community, but there is an objectively correct answer, and it really matters… as you’ve discovered.
Now, C++ has a silly little loophole that allows you to write const T&, and the compiler will understand that you REALLY mean T const&. Same for const T*; it gets quietly translated to T const*. So most of the time, you don’t notice that you’re using const wrong. But in this case, you’ve hit one of the cases where the mistake actually causes a problem.
reference is T&. When you const reference… or, better, when you write it CORRECTLY as reference const, that expands to T& const… NOT T const& (or const T&).
Now do you understand the warning?
You can’t have a “const reference”, or thing& const. You can have a “reference to a const (thing)”, or thing const&. The thing-being-referenced can be const, but the reference itself cannot. References are always const, because unlike pointers, you can’t change what they are referenced to.
Note that pointers CAN be const. You can have a T const * const, which is a const pointer to a const T (which is basically T const&, except it can be nullptr and you have to use * everywhere). You can have a T const* which is a non-const pointer to a const T. You can have a T* const, which is a const pointer to a non-const T (basically T&). And of course you can have T*, a non-const pointer to a non-const T.
I suggest to people I teach C++ to that they read the type backwards. So T& is a “reference to T”, and T const& is a “reference to const T”. (And T const * const is a const pointer to a const T, and so on.)
So to silence the warning, you have tried to replace reference const with T const&. But that’s wrong. Those are two completely different things. That’s similar to trying to replace a T* const with a T const*. It “works” (without a warning for pointers) only because dropping the const on the pointer doesn’t matter when you’re doing with a copy, and adding the const on the T is always allowed—you’re always allowed to add const. Assigning the former to the latter “works”… but T const* and const T* still are very different things. Assigning T& const to T const& “works” for references too; the only reason you get the warning is because T& const is gibberish.
All this, by the way, is why CONTAINERS have reference (which is usually T&) and const_reference (which is usually T const&). (And pointer and const_pointer.) If reference was just reference const, there wouldn’t be any need for const_reference.
reference is T&reference const would be T& const (which is gibberish); andconst_reference is T const&.
Similarly, for CONTAINERS:
pointer is T*pointer const is T* const; andconst_pointer is T const*.
ITERATORS don’t have const_reference or const_pointer because they don’t make any sense for iterators. Instead, there are iterators and const_iterators:
iterator::reference is T&iterator::pointer is T*const_iterator::reference is T const&; andconst_iterator::pointer is T const*.
So let’s circle back to the operator functions here:
reference operator*() const // <- I recommend both const (and noexcept)
{
return *ptr_;
}
// Warning says "const has no effect on type reference"
const T& /*reference*/ operator*() const
{
return *ptr_;
}
Notice now that the two functions are literally identical? That’s because you don’t need a non-const version, and because the correct return type for the const version is just reference (not reference const or T const&).
So all you need is:
reference operator*() const noexcept
{
return *ptr_;
}
And maybe constexpr, though I don’t know if C++11’s constexpr rules will allow it. (C++17+ will, though.)
const this_type& operator++()
{
ptr_ = std::next(ptr_);
return *this;
}
You mentioned that clang-tidy gave a warning about const for the postfix increment operator… are you sure it wasn’t for this function, the prefix increment operator? Because returning a const reference is wrong here. Try doing ++ ++i for this type; it won’t compile. The correct form for this operator is to return a non-const reference.
As for the postfix increment operator, I don’t really see anything wrong with it.
Now, I’m honestly not sure what you think std::next() is doing here. ptr_ is a T*. std::next() for any pointer p is just ++p. All this function needs to be is:
WrappedRandomAccessIterator operator++() noexcept
{
++ptr_;
return *this;
}
Alright, that’s it for the code as written. Now I’m going to go on to do a design review.
Design review
Ceci n’est pas un iterator
Okay, this first problem here is that you claim this to be a random-access iterator… but it’s not. It’s not even a bidirectional iterator. It can’t possibly be any better than a forward iterator… except it’s not even that! It’s not even a legal iterator at all!
Why? Because an iterator needs more than just operator++ (prefix and postfix) and unary operator*. At the bare minimum, the most basic kinds of iterators—input, output, and forward iterators—also require equality operators… that is, both operator== and operator!=. How can you possibly even implement the simplest algorithms, like std::for_each(), without them?
template <typename Iterator, typename Func>
void example_for_each(Iterator first, Iterator last, Func&& func)
{
while (first != last) // won't work without operator !=
func(*first++);
}
I’d have to check, but I’m pretty sure that the most basic iterators also need operator->, too.
A random-access operator also needs operator-- (prefix and postfix). And it needs operator+= and operator-= with difference_type. AND it needs binary operator+ and binary operator- with difference_type (both ways around). AND it ALSO needs operator- between two iterators, returning a difference_type. And I’m probably forgetting a bunch of other stuff, too. There’s actually quite a lot of operations a random-access iterator can do.
You need to add a whole lot of extra operators to this class to make it a random-access iterator.
Random-access ≠ contiguous
Okay, so, here is where I really have to guess at what the real purpose of this class is. I imagine you have some function, call it foo(), that takes a pair of iterators to a sequence—let’s assume it’s a sequence of ints. To actually think this problem concretely through without resorting to vague and nebulous hand-waving, I’m going to assume that foo() actually does something real: I’m going to assume foo() does what std::minmax_element() does.
Now the tricky thing here is that you want foo() to NOT be a function template. You want only the declaration in the header, and the definition in a source file:
// foo.hpp
auto foo(??? first, ??? last) -> std::pair<???, ???>;
// foo.cpp
auto foo(??? first, ??? last) -> std::pair<???, ???>
{
auto result = std::pair<???, ???>{first, first};
for (; first != last; ++first)
{
if (*first < *(result.first))
result.first = first;
if (*(result.second) == *first or *(result.second) < *first)
result.second = first;
}
return result;
}
Now we need to figure out what the type ??? is. This is what I presume you intend WrapperRandomAccessIterator for. You want to do:
// foo.hpp
auto foo(WrapperRandomAccessIterator<int> first, WrapperRandomAccessIterator<int> last)
-> std::pair<WrapperRandomAccessIterator<int>, WrapperRandomAccessIterator<int>>;
// foo.cpp
auto foo(WrapperRandomAccessIterator<int> first, WrapperRandomAccessIterator<int> last)
-> std::pair<WrapperRandomAccessIterator<int>, WrapperRandomAccessIterator<int>>
{
auto result =
std::pair<WrapperRandomAccessIterator<int>, WrapperRandomAccessIterator<int>>{
first, first};
for (; first != last; ++first)
{
if (*first < *(result.first))
result.first = first;
if (*(result.second) == *first or *(result.second) < *first)
result.second = first;
}
return result;
}
And you want to be able to call it with a vector of ints like this:
auto int_vec = std::vector<int>{};
// ... fill it with ints somehow...
auto result = foo(
WrapperRandomAccessIterator<int>{int_vec.begin()},
WrapperRandomAccessIterator<int>{int_vec.end()});
Something like that, right?
So the question is… will this work? Yes. Once you add operator!= to the class, then yes, this will work.
So all good, right?
No. In fact, you have some nasty bugs lurking, which could easily lead to a segfault, but just as easily not while doing catastrophic damage to your machine… almost certainly not for a machine running a modern desktop OS, of course, but who knows? That’s the problem with UB. Anything could happen.
Here’s the problem. You assume that given a pair of random-access iterators to a sequence, you can degrade them to pointers, and then treat them the same as the original iterators. For example:
auto sequence = std::vector<int>{};
// ... fill sequence with a million ints...
// You assume that this...:
auto iter_beg = sequence.begin();
auto iter_end = sequence.end();
std::for_each(iter_beg, iter_end, [](int i) { std::cout << i << ' '; });
// ... is basically the same as this...:
auto ptr_beg = &(*(sequence.begin()));
auto ptr_end = &(*(sequence.end()));
std::for_each(ptr_beg, ptr_end, [](int i) { std::cout << i << ' '; });
For a vector, you’d be right. The two cases above are functionally identical, and your WrapperRandomAccessIterator would work just fine, no problems. It would also work for std::array, std::string, and C arrays (and std::valarray, but who even uses that anymore?).
But you know what? It won’t work for std::deque.
Why not? Because you have confused the concept of “random-access iterator” with the concept of “contiguous iterator”. Not all random-access iterators are contiguous iterators:
| Container |
Random access? |
Contiguous? |
std::vector |
✓ |
✓ |
std::array |
✓ |
✓ |
std::string |
✓ |
✓ |
| C array |
✓ |
✓ |
std::deque |
✓ |
✗ |
Internally, a deque is an vector of pointers to arrays. This structure makes appending to the front and back fast—if there’s no space, just add another array chunk, at either the beginning or the end. It also allows for random access—element N is at position “num_elements_in_first_chunk + ((chunk_number * chunk_size) + n)”, and you just solve for chunk_number and n (which is just subtracting num_elements_in_first_chunk from N, then doing N / chunk_size to get chunk_number and N % chunk_size to get n).
But while random-access is possible in a deque, that doesn’t mean that the elements are contiguous. They are if they all happen to be in the same array chunk. But if the elements are in two different chunks, all bets are off.
So if you did the example above with a deque…:
auto sequence = std::deque<int>{};
// ... fill sequence with a million ints...
// No problems:
auto iter_beg = sequence.begin();
auto iter_end = sequence.end();
std::for_each(iter_beg, iter_end, [](int i) { std::cout << i << ' '; });
// Boom, UB, possible segfault:
auto ptr_beg = &(*(sequence.begin()));
auto ptr_end = &(*(sequence.end()));
std::for_each(ptr_beg, ptr_end, [](int i) { std::cout << i << ' '; });
So you might think that, okay, if random-iterators won’t work, you could just use contiguous iterators instead. Well, sorry. There are no contiguous iterators in C++11. (Well, there are, but the concept wasn’t standardized.) Contiguous iterators didn’t come around until C++17… but you couldn’t actually use them until C++20.
So… what does that mean?
Well, it means your WrapperRandomAccessIterator won’t actually work for all random-access iterators. Sure, it will work for most random-access iterators (if you actually implement all the required functions)… but not all. And there’s no safe way to detect which iterators will cause a crash (not until C++20).
So you have two options:
- throw the whole design out; or
- accept the limitations, accept that it will only work for some types and maybe add checks to make sure only those types are used, and just live with that.
HOWEVER… if you chose option 2, there is one more thing to consider…
Going contiguous? Don’t over-engineer; just use pointers
Contiguous iterators are really just pointers. Your misnamed WrapperRandomAccessIterator is actually WrapperContiguousIterator, because it only works for contiguous iterators, because it uses pointers internally.
But… here’s the thing… if you’re just going to use pointers internally… why not just use them externally, too?
Let's go back to the foo() function:
// foo.hpp
auto foo(WrapperRandomAccessIterator<int> first, WrapperRandomAccessIterator<int> last)
-> std::pair<WrapperRandomAccessIterator<int>, WrapperRandomAccessIterator<int>>;
// foo.cpp
auto foo(WrapperRandomAccessIterator<int> first, WrapperRandomAccessIterator<int> last)
-> std::pair<WrapperRandomAccessIterator<int>, WrapperRandomAccessIterator<int>>
{
auto result =
std::pair<WrapperRandomAccessIterator<int>, WrapperRandomAccessIterator<int>>{
first, first};
for (; first != last; ++first)
{
if (*first < *(result.first))
result.first = first;
if (*(result.second) == *first or *(result.second) < *first)
result.second = first;
}
return result;
}
// Usage in other.cpp
auto int_vec = std::vector<int>{};
// ... fill it with ints somehow...
auto result = foo(
WrapperRandomAccessIterator<int>{int_vec.begin()},
WrapperRandomAccessIterator<int>{int_vec.end()});
Since WrapperRandomAccessIterator<int> is ultimately just an int*… why not do:
// foo.hpp
auto foo(int* first, int* last) -> std::pair<int*, int*>;
// foo.cpp
auto foo(int* first, int* last) -> std::pair<int*, int*>
{
auto result = std::pair<int*, int*>{first, first};
for (; first != last; ++first)
{
if (*first < *(result.first))
result.first = first;
if (*(result.second) == *first or *(result.second) < *first)
result.second = first;
}
return result;
}
// Usage in other.cpp
auto int_vec = std::vector<int>{};
// ... fill it with ints somehow...
auto result = foo(&(*(int_vec.begin())), &(*(int_vec.end())));
// or:
auto result = foo(int_vec.data(), int_vec.data() + int_vec.size());
Note that if you were going this route, rather than taking a pair of pointers, a safer option might be to take a pointer and a size. It’s easy to mix up pointers, or to one pointer from one sequence and another pointer from another sequence. It’s a lot harder to screw up using a pointer and a size.
Actual type-erased iterators…?
Okay, so pointers work fine for contiguous iterators, but let’s say you really, really want to use random-access iterators. Or maybe even bidirectional or forward iterators. Can it be done? How?
Well, I’m not going to put any real thought into solving this problem right now… but if I had to just barf something up, I might do something like this:
Rather than trying to degrade iterators to pointers, I would ask what are the fundamental operations an iterator needs. A basic iterator—input, output, and forward—needs to be able to do 3 things:
- dereferencing (so
*i returns a possibly-const reference)
- movement (so
++i advances the i); and
- equality (so
i == j returns true if they reference the same thing).
A bidirectional iterator only adds the ability to do “negative movement”; movement backwards via decrement.
A random-access iterator adds a TON of stuff… but it really boils down to:
- really big movement (
i += n or i -= n)
- distance measuring (
i - j); and
- comparison (
i < j).
“Really big movement” is just movement, as is “negative movement”. And we can join equality and comparison if we keep track of what kind of comparison we’re actually doing.
So we can boil this down to 4 operations. Assuming p and q are type-erased (std::any—I know this requires C++17, but you can always use boost::any) iterators:
deref(std::any p) handles dereferencing (returns a possibly-const reference to whatever the iterator references);advance(std::any p, std::ptrdiff_t n) handles movement (normally n must be 1, but can be -1 for bidirectional iterators, and any number for random-access iterators);compare(std::any p, std::any q, bool eq) returns int(i == j) if eq is true using the iterators under p and q, or 1, 0, or −1 if eq is false doing a standard 3-way compare between i and j, handling both equality and comparison; anddistance(std::any p, std::any q) handles distance measurement.
Then we define a class that holds functions:
template <typename T, typename IterCat>
class type_erased_iterator
{
private:
std::any _iter;
std::function<T& (std::any&)> _deref;
std::function<void (std::any&, std::ptrdiff_t)> _advance;
std::function<int (std::any const&, std::any const&, bool)> _compare;
std::function<std::ptrdiff_t (std::any const&, std::any const&)> _distance;
public:
using difference_type = std::ptrdiff_t;
using value_type = typename std::decay_cv<T>::type;
using pointer = T*;
using reference = T&;
using iterator_category = IterCat;
template <typename Iterator>
explicit type_erased_iterator(Iterator it) :
_iter{it},
_deref{[](std::any& p) -> T& { return *std::any_cast<Iterator>(p); }},
_advance{[](std::any& p, std::ptrdiff_t n) { std::advance(std::any_cast<Iterator>(p), n); }},
// you get the idea...
{}
template <typename Iterator>
type_erased_iterator(
Iterator it,
std::function<T& (std::any&)> deref,
std::function<void (std::any&, std::ptrdiff_t)> advance,
std::function<int (std::any const&, std::any const&, bool)> compare,
std::function<std::ptrdiff_t (std::any const&, std::any const&)> distance
) :
_iter{it},
_deref{std::move(deref)},
_advance{std::move(advance)},
_compare{std::move(compare)},
_distance{std::move(distance)}
{}
// Now just implement the iterator ops in terms of the core functions.
auto operator++() -> type_erased_iterator&
{
_advance(_iter, 1);
return *this;
}
auto operator*() -> T&
{
return _deref(_iter);
}
// and so on...
};
// usage:
auto int_vec = std::vector<int>{};
// ... fill it with ints somehow...
auto result = foo(
type_erased_iterator<int, std::random_access_iterator_tag>{int_vec.begin()},
type_erased_iterator<int, std::random_access_iterator_tag>{int_vec.end()});
As you can see, it’s used pretty much exactly like the way I assumed WrapperRandomAccessIterator would be used. You could even make a helper function to make it simpler:
auto result = foo(
make_type_erased_iterator(int_vec.begin()),
make_type_erased_iterator(int_vec.end()));
Given that most iterators are small (often just pointers), and that the functions will probably never be closures, there shouldn’t be any dynamic allocation required. This class won’t be fast, but it will allow you to type-erase ANY iterator. Not just random-access; you can even type erase input or output iterators.
If you really just want to support random-access iterators, that eliminates much of the complexity of SFINAE-ing away illegal iterator operations (like preventing operator-- for forward iterators).
Summary
WrapperRandomAccessIterator is unfortunately named, because it is not a wrapper, and it does not work with random-access iterators.
It does work with contiguous iterators, and ONLY contiguous iterators… or at least it would if you added all the required iterator operations. However, contiguous iterators aren’t really a thing until C++17, and not a practical thing until C++20.
But if you really only want it to work with contiguous iterators, you might as well just use pointers.
If you really need other iterator categories (including actual random-access iterators), you will need a much more advanced type-erasure system.
