Input iterator is an abstract concept
I think you are very confused.
“Input iterator” is a concept. A concept is an abstract specification, not a concrete “thing”. You can’t make an “implementation of input iterator”; that’s gibberish. You can implement something that satisfies the input iterator concept, but you can’t implement input iterator itself.
It’s kinda like saying: “I’m making an implementation of container”. The only valid response to that statement is a blank look and the question: “Okay… WHICH container? A linked list? A hash table? A double-ended queue?” You can’t just make ‘container’; it’s an abstract concept. You can implement something that is a container (that is, something that satisfies the abstract specification of “container”), but you can’t actually “implement container”… that’s gibberish.
You say you “need input_iterator for a specific constructor”… I think you mean you need AN input iterator for a specific constructor; you need a type that satisfies the input iterator concept, not specifically a type that “is” input iterator (because that’s gibberish).
If you need an input iterator, you don’t need to make one. It’s a concept. Anything that satisfies the concept will do. For example, in the standard library, std::istream_iterator is an input iterator:
#include <forward_list>
#include <iostream>
#include <iterator>
#include <list>
#include <sstream>
#include <vector>
template <typename T>
void foo(T, T)
{
std::cout << "foo called with some type\n";
}
template <std::forward_iterator T>
void foo(T, T)
{
std::cout << "foo called with forward iterators (or better)\n";
}
template <std::input_iterator T>
void foo(T, T)
{
std::cout << "foo called with input iterators\n";
}
auto main() -> int
{
auto vec = std::vector<int>{};
auto list = std::list<int>{};
auto slist = std::forward_list<int>{};
auto iss = std::istringstream{};
foo(0, 1);
foo(vec.begin(), vec.end());
foo(list.begin(), list.end());
foo(slist.begin(), slist.end());
foo(std::istream_iterator<int>{iss}, std::istream_iterator<int>{});
}
Output:
$ ./a.out
foo called with some type
foo called with forward iterators (or better)
foo called with forward iterators (or better)
foo called with forward iterators (or better)
foo called with input iterators
$
I can’t quite make sense of what you think you mean when you say you “need input_iterator for a specific constructor”, but if you mean you need to test a specific constructor with input iterators, then you can just do:
auto iss = std::istringstream{"5 4 3 2 1"};
auto v = your_vector<int>(std::istream_iterator<int>{iss}, std::istream_iterator<int>{});
// If the above constructor works as expected, v should now contain: 5, 4, 3, 2, 1
If you mean you need to implement a specific constructor with input iterators, then that’s just:
template <typename T>
class your_vector
{
// ... [snip] ...
template <typename T>
constexpr your_vector(T first, T last)
{
while (first != last)
this->push_back(*first++);
}
// ... [snip] ...
};
That’s a constructor that takes input iterators.
Of course, before C++20 it’s standard practice to name the type with something more descriptive than T if you’re using a concept, like:
template <typename T>
class your_vector
{
// ... [snip] ...
template <typename InputIterator>
constexpr your_vector(InputIterator first, InputIterator last)
{
while (first != last)
this->push_back(*first++);
}
// ... [snip] ...
};
And as of C++20, you can now actually check that the type satisfies the input iterator concept, because the standard library has a std::input_iterator concept defined already:
template <typename T>
class your_vector
{
// ... [snip] ...
template <std::input_iterator It>
constexpr your_vector(It first, It last)
{
while (first != last)
this->push_back(*first++);
}
// ... [snip] ...
};
That’s it. That’s all you need. That’s implementing a constructor with input iterators, and above I show you how to test a constructor with input iterators. You don’t need to make an “input iterator” type, because the standard library already has input iterator types (and, as of C++20, a std::input_iterator concept to check them, to make sure they really are valid input iterators).
Your type is dangerous and buggy
So what you’re trying to do is take a plain pointer—which is a contiguous iterator—and strip its power, to reduce its capability until it looks like an input iterator.
In VERY limited circumstances, this isn’t a terrible idea. For example, if you’re making an algorithm that works differently with input iterators than with forward iterators or better, and you want to test that the right implementation is being used, you could use a type like this to take the pointers to an array or vector data, and forcibly pretend they’re only input iterators.
Of course… you could also just use actual input iterators, for example, by creating an istringstream, and then using istream_iterators. That would be less work, and zero chance of bugs and other headaches.
Where this type gets dangerous is that it will only work for very limited circumstances… and where it won’t work, it will silently trigger undefined behaviour.
This is okay:
auto data = std::vector<int>{};
// fill data with values...
auto first = input_iterator<int>(&data.front());
auto last = input_iterator<int>(&data.front() + data.size());
any_algorithm(first, last);
This is not:
auto data = std::deque<int>{};
// fill data with values...
auto first = input_iterator<int>(&data.front());
auto last = input_iterator<int>(&data.front() + data.size());
any_algorithm(first, last);
The only thing that changed is the type of the container. But while std::deque is random-access, it is NOT contiguous, so trying to iterate through it using pointer arithmetic (which input_iterator does internally) is a quick path to UB.
(In fact, the code above will not work for any container except std::vector. Trying it with std::list or anything else is asking for UB.)
Iterators are attached to specific container types for a reason; you can’t just make an iterator out of the æther with no associated container. Again, that’s nonsensical. An iterator needs to know the correct way to move from one element to the next… no, simply skipping to the next address in memory is NOT the correct way to do it, usually.
It is possible to implement an iterator adaptor that can take an iterator and fake it as a more restrictive category. But if you’re going to do that, you have to do it carefully. Simply degrading to a pointer is not the right way to do it.
Your type is not an input iterator… or an iterator at all
Okay, so you can’t implement an abstract concept. But you can implement something that models the abstract concept. You can’t “implement input iterator”, but you can implement something that models input iterator. Does your class model input iterator?
No. It’s closer to a forward iterator, but it isn’t even that.
To see what I mean, here’s a simple program that just prints the name of an iterator’s category, tested with simple pointers, std::istream_iterator, and your input_iterator:
#include <iostream>
#include <iterator>
#include <string_view>
#include <type_traits>
#include <your-input-iterator-declaration>
namespace detail_ {
template <typename T, typename = void>
struct iter_cat_impl_2_
{ using type = std::iterator_traits<T>::iterator_category; };
#if defined(__cpp_lib_ranges) and __cpp_lib_ranges >= 201911L
template <typename T>
struct iter_cat_impl_2_<T, std::void_t<typename std::iterator_traits<T>::iterator_concept>>
{ using type = std::iterator_traits<T>::iterator_concept; };
#endif // defined(__cpp_lib_ranges) and __cpp_lib_ranges >= 201911L
struct dummy_t {};
template <typename T, typename = void>
struct iter_cat_impl_1_ { using type = dummy_t; };
template <typename T>
struct iter_cat_impl_1_<T, std::void_t<typename std::iterator_traits<T>::iterator_category>> : iter_cat_impl_2_<T> {};
using namespace std::string_view_literals;
template <typename T>
inline constexpr auto iter_cat_name = "<not an iterator>"sv;
template <>
inline constexpr auto iter_cat_name<std::input_iterator_tag> = "input iterator"sv;
template <>
inline constexpr auto iter_cat_name<std::output_iterator_tag> = "output iterator"sv;
template <>
inline constexpr auto iter_cat_name<std::forward_iterator_tag> = "forward iterator"sv;
template <>
inline constexpr auto iter_cat_name<std::bidirectional_iterator_tag> = "bidirectional iterator"sv;
template <>
inline constexpr auto iter_cat_name<std::random_access_iterator_tag> = "random access iterator"sv;
#if defined(__cpp_lib_ranges) and __cpp_lib_ranges >= 201911L
template <>
inline constexpr auto iter_cat_name<std::contiguous_iterator_tag> = "contiguous iterator"sv;
#endif // defined(__cpp_lib_ranges) and __cpp_lib_ranges >= 201911L
} // namespace detail_
template <typename T>
inline constexpr auto iter_cat_name = detail_::iter_cat_name<typename detail_::iter_cat_impl_1_<T>::type>;
auto main() -> int
{
std::cout << "int* = " << iter_cat_name<int*> << '\n';
std::cout << "istream_iterator<int> = " << iter_cat_name<std::istream_iterator<int>> << '\n';
std::cout << "input_iterator<int> = " << iter_cat_name<input_iterator<int>> << '\n';
}
Output:
$ ./a.out
int* = contiguous iterator
istream_iterator<int> = input iterator
input_iterator<int> = <not an iterator>
$
As you can see, your type is not an iterator.
The reason your type fails to be detected as an iterator is because you are missing some key typedefs. It looks like you have confused the typedefs necessary for a CONTAINER with the typedefs necessary for an ITERATOR. An ITERATOR does not need const_pointer or const_reference… those make no sense for an iterator. It does need difference_type and iterator_category.
Once you define those typedefs, this type will “work” as an input iterator. But it will also “work” as a forward iterator (though, a well-designed algorithm will still treat it as an input iterator).
Okay, let’s dive into the actual code review.
The review
I’ll skip down to the typedefs, because everything prior to that is cool:
using reference = T&;
using const_reference = const T&; // <- nonsense typedef
using value_type = T;
using pointer = T*;
using const_pointer = const T*; // <- nonsense typedef
The two typedefs I’ve marked are nonsense for an iterator. You have confused the typedefs required for a container with the typedefs required for an iterator.
To understand why those typedefs are nonsensical, consider std::vector<int>::iterator::const_pointer. What do you think that means? std::vector<int>::iterator basically means: “I want a mutable pointer to the elements of an int vector (treated as a plain pointer)”. So std::vector<int>::iterator::const_pointer basically means: “I want a mutable pointer to the elements of an int vector no wait I changed my mind I want a const pointer to those elements (treated as a plain pointer)”. Meanwhile, there’s std::vector<int>::const_iterator, which actually means: “I want a const pointer to the elements of an int vector (treated as a plain pointer)”.
That’s another reason why const_pointer and const_reference make no sense in an iterator: that’s what const_iterators are.
In addition, if you want your type to work as an iterator, there are some other typedefs you need. You need to define difference_type, and you need to define iterator_category. The former could be std::ptrdiff_t, and the latter, since you want it to be an input iterator, should be std::input_iterator_tag.
pointer and reference should also probably be defined differently, but I’ll explain why later.
constexpr explicit input_iterator(const input_iterator& other) noexcept : input_iter{ other.input_iter } {}
~input_iterator() noexcept = default;
These are kinda pointless. If you don’t need to declare the destructor, don’t bother. And in the case of the copy constructor, defining it like this means the type is no longer trivially copyable (or movable). (The explicit keyword is also meaningless here, because a copy constructor is not a converting constructor. It makes no sense to “explicitly copy”.)
constexpr reference operator=(const input_iterator& other){
if (input_iter != other.input_iter)
input_iter = other.input_iter;
return *this;
}
As above, this is kinda pointless, and it means the type is no longer trivially assignable. The implementation is also overly complicated, too, because there’s no need to check for equality before doing the assignment. What exactly would go wrong if the two pointers are the same, yet you did the assignment anyway?
constexpr const_reference operator*() const {
return *this;
}
constexpr const_pointer operator->() const {
return this;
}
Seems to me like all these operations, and the increment ops, too, could be noexcept.
However, both of these are wrong. Did you test the type? I can’t imagine it compiled. The reason why is that operator* on an iterator is supposed to return a reference to whatever is being pointed to. But you return *this. That’s a reference to the iterator… not to what the iterator is pointing to.
The same problem exists for operator->. You’re supposed to return the address the iterator is pointing… but you return the address of the iterator.
operator* should probably just be returning *input_iter, and operator-> should be probably returning input_iter itself.
But there’s a much deeper issue: you’re seeing cracks in your conceptual model. An iterator is basically a pointer—the abstraction is just to allow more powerful pointers; ones that can handle iterating in ways other than merely jumping to the next memory address. So you can mentally replace any iterator with T* to get a grasp on how operator* and operator-> should work.
So if you have int*, what should operator* return? The answer is int&… NOT int const&.
If you have int* const, what should operator* return? Again, int&… NOT int const&.
So with input_iterator<int>, operator* should return int&… NOT int const&.
With input_iterator<int> const, operator* should also return int&… NOT int const&.
In other words, this is the correct way to implement operator* for iterators:
constexpr reference operator*() const noexcept { return *input_iter; }
Note that it returns reference, and not const_reference (which is not a thing; iterators don’t have const_reference because it’s nonsensical). Similarly, operator-> should return pointer, not const_pointer.
Ah, but input iterators offer only read-only views of what they point to, so they should return const pointers and references. The correct way to handle this is to properly define reference and pointer… not to invent new typedefs.
reference should be defined as T const&, not T&, because if the iterator is an input iterator, a reference will be read-only. Having reference defined as T& makes no sense for an input iterator. Similarly, pointer should be T const*, not T*. If I do input_iterator<int>::pointer p = &(*i);, that should compile… that’s the point of the pointer typedef. It won’t if pointer is T* while operator* returns const&.
So your typedefs really need to be:
using value_type = T;
using reference = T const&;
using pointer = T const*;
using difference_type = std::ptrdiff_t;
using iterator_category = std::input_iterator_tag;
That’s about it, except for:
constexpr bool operator==(const input_iterator& other) const noexcept {
return (input_iter == other.input_iter);
}
constexpr bool operator!=(const input_iterator& other) const {
return !(input_iter == other.input_iter);
}
You’re missing the noexcept for the inequality operator.
Standard practice is to use non-member functions for binary operators, and to define only one operator where possible and then all others in terms of that one. So:
friend constexpr bool operator==(const input_iterator& lhs, const input_iterator& rhs) noexcept {
return lhs.input_iter == rhs.output_iter;
}
friend constexpr bool operator!=(const input_iterator& lhs, const input_iterator& rhs) noexcept {
return not (lhs == rhs);
}
(It’s also a good idea, even though they’re non-member functions, to define them in the class as friends. This is called the “hidden friends” pattern, and it has several benefits, but it’s too much to go into here.)
Summary
The main problem here is conceptual confusion. “Input iterator” is an abstract idea. It’s a concept. You can’t make an implementation of input iterator any more than you can make an implementation of “equality comparable”. You can implement something that is equality comparable, but can’t implement the abstract concept “equality comparable”. (As of C++20, you can describe the concept, and use that to check that types satisfy the concept, but you still can’t implement the abstract concept as a type.)
So saying you are “implementing input iterator” is gibberish. Saying that you need “input iterator” for some constructor is also gibberish. Unfortunately, that’s all you’ve given, so I’m forced to guess what you really mean when you’re saying these things.
If you mean you need a constructor that takes input iterators… well, that’s just a template constructor, with a type that satisfies the input iterator concept. The type could be anything; it doesn’t need to be some concrete input_iterator type. It just needs to satisfy the concept.
The standard library has a couple types that satisfy the input iterator concept: istream_iterator and istreambuf_iterator are the two that spring to mind. So if you’re making a constructor that takes input iterators, just make a constructor template, and make sure it works with istream_iterators (and/or istreambuf_iterators).
For example, this is actually Clang 11’s implementation of std::vector’s input iterator constructor:
template <class _Tp, class _Allocator>
template <class _InputIterator>
vector<_Tp, _Allocator>::vector(_InputIterator __first,
typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&
!__is_cpp17_forward_iterator<_InputIterator>::value &&
is_constructible<
value_type,
typename iterator_traits<_InputIterator>::reference>::value,
_InputIterator>::type __last)
{
#if _LIBCPP_DEBUG_LEVEL >= 2
__get_db()->__insert_c(this);
#endif
for (; __first != __last; ++__first)
__emplace_back(*__first);
}
Ignoring the enable_if and the debug stuff, and pretending it’s defined within the class body rather than outside, that’s just:
template <class _InputIterator>
vector(_InputIterator __first, _InputIterator __last)
{
for (; __first != __last; ++__first)
__emplace_back(*__first);
}
That’s all there is to it.
(The enable_if just makes sure that _InputIterator actually satisfies the input iterator concept, but not the forward iterator concept. That’s because the forward iterator version uses std::distance() to figure out how many elements there are, so it can preallocate enough memory. You can’t do that with input iterators, because you only get one pass; you can’t first count the elements, allocate the size, then copy the elements, because that second pass won’t work for input iterators. It’s a neat optimization you might consider, though it’s much easier with C++20 concepts than with enable_if.)
And you can test that constructor with input iterators like this:
auto iss = std::istringstream{"42 69 57"};
auto const vec = std::vector<int>(std::istream_iterator<int>{iss}, std::istream_iterator<int>{});
TEST(vec.size() == 3);
TEST(vec.at(0) == 42);
TEST(vec.at(1) == 69);
TEST(vec.at(2) == 57);
Another issue with your design is that “generic” iterators make no sense. Iterators are tightly bound to containers (or views, or other such things). You can’t simply make an iterator that just works with any container. Indeed the only standard containers your iterator works with are std::vector and std::array. For all other containers, it will trigger UB.
And finally, if you want this type to be an actual (input) iterator, you need to add some extra typedefs, modify the existing typedefs, and fix some problems in your dereferencing operators.
But honestly, I would suggest just throwing the whole thing out, because:
- It’s poorly conceived (it is trying to be a concrete implementation of an abstract idea).
- It’s dangerously buggy (it only works with certain containers).
- It’s unnecessary (if you want an input iterator, there are already input iterators in the standard).
