# Input Iterator implementation

I need some review on my implementation of input iterator. I am currently re-implementing std::vector, and need input_iterator for a specific constructor.

Any criticism is much appreciated! Thank you.

#ifndef INPUT_ITERATOR
#define INPUT_ITERATOR

template<typename T>
class input_iterator
{
private:
T* input_iter;

public:
using reference = T&;
using const_reference = const T&;
using value_type = T;
using pointer = T*;
using const_pointer = const T*;

constexpr input_iterator() noexcept : input_iter{ nullptr } {}

constexpr explicit input_iterator(pointer inputIter) noexcept : input_iter{ inputIter } {}

constexpr explicit input_iterator(const input_iterator& other) noexcept : input_iter{ other.input_iter } {}

~input_iterator() noexcept = default;

constexpr reference operator=(const input_iterator& other){
if (input_iter != other.input_iter)
input_iter = other.input_iter;
return *this;
}

constexpr const_reference operator*() const {
return *this;
}

constexpr const_pointer operator->() const {
return this;
}

constexpr input_iterator& operator++() {
++input_iter;
return *this;
}

constexpr input_iterator& operator++(int) {
input_iterator current{ input_iter };
++(*this);
return current;
}

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);
}

};

#endif
$$$$

• The iterator for a constructor is normally just a templated type that implements the iterator concept. All standard iterators implement this concept o why do you need a special one for your version of the vector? – Martin York Jan 2 at 20:11
• Hope this series on the vector helps: lokiastari.com/series – Martin York Jan 2 at 20:12
• Not sure why you want this. A pointer already implements the iterator concept so you don't need to wrap it. – Martin York Jan 2 at 20:29
• I have rolled back the last edit. Please see What to do when someone answers. – Edward Jan 3 at 17:51

# 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:

1. It’s poorly conceived (it is trying to be a concrete implementation of an abstract idea).
2. It’s dangerously buggy (it only works with certain containers).
3. It’s unnecessary (if you want an input iterator, there are already input iterators in the standard).
• Put the summary first. – Martin York Jan 2 at 23:51
• Amazing and very deep explaination. Thank you a lot. In fact, I was very confused - and I realized (thanks to your answer) that whatever I attempted to do was actual nonsense.Thanks for your time! – user235054 Jan 3 at 17:25
• Very nice and thorough! I'll just add to "[an iterator] does need difference_type and iterator_category" that these are not required in the iterator class. Pointers don't have them and still work as iterators. How? The standard notes: Either the iterator type must provide the typedef-names directly (in which case iterator_­traits pick them up automatically), or an iterator_­traits specialization must provide them. – Felix Dombek Jan 4 at 2:42

## Overview

Not sure why you want to wrap a point to be an iterator. A pointer already implements the iterator concept (if fact it implements the random accesses iterator concept the most advanced type of iterator). By using this wrapper you are stunting the iterator implementation used.

## Code Review

A bit generic. I would be afraid that another header was using this.

#ifndef INPUT_ITERATOR
#define INPUT_ITERATOR


I usually include the namespace as part of the guard macro.

Don't think you need to be explicit here.

     ~input_iterator() noexcept = default;


Don't see the need for a self assignment test!

    constexpr reference operator=(const input_iterator& other){
if (input_iter != other.input_iter)
input_iter = other.input_iter;
return *this;
}


There are no resources to worry about. Simply overwrite every time. This will prevent branch prediction failures (and ultimately be quicker).

Close.

constexpr input_iterator& operator++(int) {
input_iterator current{ input_iter };
++(*this);
return current;
}


But you are returning a reference to a local here. Remove the & from the interface. Return a copy. Iterators are supposed to be cheap to copy.

You only have a version that returns a const reference. What about a version that returns a reference?

    constexpr const_reference operator*() const {
return *this;
}


Also the thing you are returning is not the correct type. Does this even compile?

Again only a const pointer version. Why no pointer version?

    constexpr const_pointer operator->() const {
return this;
}


Also the thing you are returning is not the correct type. Does this even compile?

• Thanks for the quick reply! I haven't even noticed these mistakes, so thank you a lot ^^ – user235054 Jan 2 at 20:34

# Use default constructors and assignment operators where possible

Keep the number of user-defined constructors and operators to a minimum, and use = default if necessary. You only need the default constructor and the one that takes a pointer as an argument, the other constructors, assignment operators and even the destructor will already be provided for free. So:

template<typename T>
class input_iterator {
...
public:
constexpr input_iterator() noexcept : input_iter{} {}
constexpr explicit input_iterator(pointer inputIter) noexcept : input_iter{ inputIter } {}

/* no other constructors, destructors or assignment operators */
...
};


# Fix the dereferencing operators

The dereferencing operators should not return this or *this, but rather input_iter or *input_iter:

constexpr const_reference operator*() const {
return *input_iter;
}

constexpr const_pointer operator->() const {
return input_iter;
}


# The post-increment operator is wrong

Your post-increment operator returns a reference to a local variable. This is wrong of course, you should return by value instead. Here is how to do it in a one-liner:

constexpr input_iterator operator++(int) {
return input_iterator(input_iter++);
}

• Thank you for replying quickly. I'll make sure to fix the mentioned issues ^^ – user235054 Jan 2 at 20:34
• std::input_iterator does not require a difference operator. Only random access or better iterators require difference operators. The only difference between std::input_iterator and LegacyInputIterator that I’m aware of is that the former has relaxed some equality requirements since C++20 now uses an iterator/sentinel model, rather than an iterator/iterator model. – indi Jan 2 at 21:39
• @indi Hm, but std::input_iterator requires std::input_or_output_iterator, which requires std::weakly_incrementable, which in turn requires /*is-signed-integer-like*/<std::iter_difference_t<I>>, and I was only able to have OP's class match the concept std::input_iterator when using GCC 10 if it has an operator-(). Is there a way to add a tag or something to make it pass if there is no difference operator? – G. Sliepen Jan 3 at 0:22
• @G.Sliepen That type has several issues that disqualify it from std::input_iterator. std::iter_difference_t<I> only requires iterator_traits<I>::difference_type, not operator-(I, I). It’s also not movable (required by std::weakly_incrementable). I can get it to pass minimally on GCC by adding difference_type and defaulted move construction/assignment. It’s still wrong—it won’t even compile if instantiated—but at least the concept will pass. – indi Jan 3 at 0:49
• As an aside, std::forward_iterator is even stricter. If you want to satisfy that, then in addition to satisfying std::input_iterator, you’d need to fix the copy constructor (remove the explicit) and fix the return types for the assignment operator and the post-increment op. That should do it; that would make it a minimal iterator, in my book (at which point you can restrict it back down to std::input_iterator` by adding the iterator category tag). – indi Jan 3 at 1:04