Iyfjky

Question

On the fly, I just implemented this iterator supporting vector class to understand how range-based for loop works.
It's really basic but let me know what can be improved.

Vector.h

#ifndef VECTOR_H
#define VECTOR_H

#include <stdexcept>

template <typename T>
class Vector

public:
 /* The iterator */
 class Iterator
 
 public:
 Iterator(const Vector<T> *vector, int nIndex);
 const T &operator*() const;
 Iterator &operator++();
 bool operator!=(const Iterator &other) const;

 private:
 const Vector<T> *m_pVector;
 int m_nIndex = -1;
 ;

public:
 // constructors
 Vector() = default;
 explicit Vector(int nSize);

 ~Vector();

 void insert(const T &value);

 int size() const;
 const T &operator(int nIndex) const;

 Iterator begin() const;
 Iterator end() const;

private:
 T *m_pData = nullptr;
 int m_nSize = 0;
 int m_nCapacity = 0;
;

/*
 * Vector methods
 **/
template <typename T>
Vector<T>::Vector(int nCapacity)

 m_nCapacity = nCapacity;
 m_pData = new T[m_nCapacity];


template <typename T>
Vector<T>::~Vector()

 delete m_pData;
 m_nSize = 0;
 m_nCapacity = 0;


template <typename T>
void Vector<T>::insert(const T &value)

 if (m_nSize == m_nCapacity)
 
 if (m_nCapacity == 0)
 m_nCapacity = 1;

 m_nCapacity *= 2;

 // allocate 2x larger memory
 auto pNewMemory = new T[m_nCapacity];

 // copy data to there
 for (auto idx = 0; idx < m_nSize; ++idx)
 pNewMemory[idx] = m_pData[idx];

 delete m_pData;
 m_pData = pNewMemory;
 

 // insert the new element
 m_pData[m_nSize] = value;
 ++m_nSize;


template <typename T>
int Vector<T>::size() const

 return m_nSize;


template <typename T>
const T &Vector<T>::operator(int nIndex) const

 if (nIndex >= m_nSize)
 throw std::exception("Index out of range");

 return m_pData[nIndex];


template <typename T>
typename Vector<T>::Iterator Vector<T>::begin() const

 return Vector<T>::Iterator this, 0 ;


template <typename T>
typename Vector<T>::Iterator Vector<T>::end() const

 return Vector<T>::Iterator this, m_nSize ;


/*
 * Iterator methods
 **/
template <typename T>
Vector<T>::Iterator::Iterator(const Vector<T> *pVector, int nIndex)
 : m_pVector(pVector)
 , m_nIndex(nIndex)



template <typename T>
const T &Vector<T>::Iterator::operator*() const

 return m_pVector->operator(m_nIndex);


template <typename T>
typename Vector<T>::Iterator &Vector<T>::Iterator::operator++()

 ++m_nIndex;
 return *this;


template <typename T>
bool Vector<T>::Iterator::operator!=(const Vector<T>::Iterator &other) const

 return m_nIndex != other.m_nIndex;


#endif // !VECTOR_H

main.cpp

#include <iostream>

#include "Vector.h"

int main()

 try
 
 Vector<int> vector;
 vector.insert(8);
 vector.insert(3);
 vector.insert(1);
 vector.insert(7);
 vector.insert(2);

 for (auto i : vector)
 std::cout << i << std::endl;
 
 catch (const std::exception &e)
 
 std::cerr << e.what() << std::endl;
 

 std::cin.get();
 return 0;

score 12 · Answer 1 · 2018-08-21 20:34:07Z

Use `delete`

You are allocating an array of objects with new, but attempting to delete them with delete, which results in undefined behavior. You should delete the array with delete to ensure that your code functions properly. Do this in both Vector<T>::~Vector() and Vector<T>::insert().

Implement your `Iterator`s as pointers under-the-hood

Since your data is stored sequentially, it makes sense to implement your Iterator members as a simple T const * rather than a pointer to the parent Vector<T> and an index. This cuts down the size of your Iterator, and avoids the awkward m_nIndex = -1 state. You can replace the Iterator's internals in this way without changing its interface.

(As a side note, the range-based for-loop would still function if you completely removed the Iterator class and just returned T const * from Vector<T>::begin() and Vector<T>::end(). I know this is not what you asked, but thought you might like to know! Example)

Construct member variables in the constructor initializer list

You are already using a member initializer list for your Iterator class, so you should do the same for Vector<T>

template <typename T>
Vector<T>::Vector(int nCapacity)
 : m_nCapacity(nCapacity)
 , m_pData(new T[nCapacity])

Use `size_t` for container size

A small detail, but using size_t instead of int for Vector<T>::size more closely resembles the standard library's containers. It is a very standard way of representing sizes.

Actually, many consider unsigned integer types for sizes one of the bigger mistakes of the standard library because of how they interact with signed values (e.g. for(int i = 0; i < vec.size() - 5; ++i) contains a serious bug). Unsigned size values got introduces as a hack/workaround to allow one more bit worth of possible storage space. It cannot be officially fixed now, because it would break backwards compatibility. But for new containers? There's no precedent, so I'd actually suggest using signed values for sizes (we don't need that extra bit for modern 64.bit architectures). — Aug 21 at 23:00
@hoffmale, do you have any guarantee that the code will only ever be built for "modern 64.bit architectures"? 16-bit int hasn't just stopped existing, you know. — Aug 22 at 8:12
@TobySpeight: Well, yes, 8-bit and 16-bit platforms still do exist. However, most of those have some kind of advanced addressing mode to allow for addressing more than 256 Bytes/65.536 Bytes respectively (e.g. far pointers). Unless your usage scenario requires you to have 50%+ of the addressable memory in a container of 1 Byte sized objects, that one extra bit of size information isn't needed. And if that is your usage scenario, it might be advisable to rethink your platform choice and/or write a specialized container, since you're likely to have very harsh memory constraints anyways. — Aug 22 at 8:27
My point is that int isn't necessarily wide enough to represent the size of the container - you might need long, for example (common on machines with 16-bit word size and 32-bit addressing for example). std::size_t is automatically the right width for the size of any object. — Aug 22 at 8:49
Sorry @hoffmale - I'd formed an image in my mind that you'd said int when you hadn't. I was wrong! — Aug 22 at 17:22

score 11 · Answer 2 · 2018-08-24 22:28:51Z

The range-based `for` loop

This works via the begin() and end() functions.

So for any class X if there are stand alone functions begin(X&) and end(X&) the range based for will work. Normally this will default to the std::begin() and std::end() but if you have written explicit versions of these functions in the same namespace as X these will be used.

Example:

#include <iostream>

namespace Y

 class X
 
 public:
 char data[14] = "This is text";
 ;

 char* begin(X& obj) 
 return obj.data;
 

 char* end(X& obj) 
 return obj.data + 10;
 


int main()

 Y::X x;
 for(auto const& a: x) 
 std::cout << a;

OK. So what happens if you don't write your own begin() and end() functions?

In this case it will use the standard versions of these functions. std::begin() which will call the begin() method on the object and std::end() which will call the end() method on the object.

Example 2:

#include <iostream>

namespace Y

 class X
 
 char data[14] = "This is text";
 public:
 char* begin() 
 return data;
 

 char* end() 
 return data + 10;
 
 ;


int main()

 Y::X x;
 for(auto const& a: x) 
 std::cout << a;

How to think of range based for

You can think of ranged based for as a compiler shortcut.

for(<Type> <Var> : <Obj>) 
 <CODE>

Is just short hand for:


 using std::begin;
 using std::end;

 auto __end = end(<Obj>);

 for(auto __loop = begin(<Obj>); __loop != __end; ++__loop) 
 <Type> <Var> = *__loop;
 <CODE>

Implementation of Iterators

The implementation of an iterator is based on the "Iterator Concept". There are actually five types of iterator in C++. But since you are using vector as your example implementation we should consider the "Random Access Iterator Concept".

To qualify as a random access iterator you have to uphold a specific contract. Here is some documentation on it.

https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator

Not only does the iterator need to define certain methods (with specific requirements on how they work together). But your type also needs to define certain types via std::iterator_traits.

Types

You need to define the following types:

value_type:

When the iterator is de-referenced this is the type you get.

difference_type:

When you subtract two iterators this is the type of the result

pointer:

A type that points at type value_type

reference:

A type that can be used as a reference to a value of type value_type

iterator_category:

A type that represents the category of the iterator.

So you could have written your own specialization of the iterator_traits class

namespace std

 template<typename T>
 class iterator_traits<Vector<T>::Iterator>
 
 using value_type = T;
 using difference_type = std::ptrdiff_t;
 using pointer = T*;
 using reference = T&;
 using iteratory_category = std::random_access_iterator_tag;
 ;

But that is a little bit like actual hard work. The designers of the STL actually got smart and the default implementation of this type refer back to the iterator type to get these types. So you can define these types in your iterator (and not define a specialization of the iterator_traits class).

Rather do this:

template<typename T>
class Vector

 class Iterator
 
 using value_type = T;
 using difference_type = std::ptrdiff_t;
 using pointer = T*;
 using reference = T&;
 using iterator_category = std::random_access_iterator_tag;
 ;
 ....

Note: If you follow the advice above and use a pointer as your iterator. The iterator_traits for pointer types are well defined in the standard and no work is required.

Properties of an Iterator

The basic properties of an iterator are:

Default Constructible *** Currently not supported.

Copy Constructible

Copy Assignable

Destructible

Swappable *** Currently not supported.

Equality Comparable *** Currently not supported (you need ==)

objects returned via de-referencing need to be mutable (not supported)

Supported actions for a random access iterator:

*i // returns the current value
*i = v // Assign value `v` to the value dererenced.
++i // increments the iterator (returns a reference)
--i // See above
i++ // increments the iterator (but returns a reference to the original)
i-- // See above
*i++ // returns the current value and increments the iterator
*i-- // See above

i += n // Moves the iterator forward
i -= n // Same as last one
i + n // Creates a new iterator moved forward from i
n + i // Same as last one
i - n // Same as last one

i1 - i2 // returns the distance between the iterators.

i[n] // returns the item n steps forward from this iterator.
i->m // Access the member `m` referenced by i

i1 < i2 // Compare iterators
i1 > i2
i1 <= i2
i1 >= i2
i1 == i2
i1 != i2

OK So I have dumped an all lot of requirements on iterators here. But it is not as bad as it seems. Have a look at an iterator I built for a stack overflow question.

https://stackoverflow.com/a/1120224/14065

This iterator is only a forward iterator (so it has fewer requirements). But it shows you how to implement the main basic requirements very quickly. The rest should not be too hard to implement for random accesses iterator.

Got bored so here:

class Iterator

public:
 using value_type = T;
 using pointer = T*;
 using reference = T&;
 using difference_type = std::ptrdiff_t;
 using iterator_category = std::random_access_iterator_tag;

 Iterator(): v(nullptr), i(0) 
 Iterator(Vector<T>* v, int i): v(v), i(i) 
 // Default Copy/Move Are Fine.
 // Default Destructor fine.

 reference operator*() return (*v)[i];
 const reference operator*() const return (*v)[i];
 pointer operator->() return &((*v)[i]);
 const pointer operator->() const return &((*v)[i]);
 reference operator(int m) return (*v)[i + m];
 const reference operator(int m) const return (*v)[i + m];


 Iterator& operator++() ++i;return *this;
 Iterator& operator--() --i;return *this;
 Iterator operator++(int) Iterator r(*this);++i;return r;
 Iterator operator--(int) Iterator r(*this);--i;return r;

 Iterator& operator+=(int n) i += n;return *this;
 Iterator& operator-=(int n) i i= n;return *this;

 Iterator operator+(int n) const Iterator r(*this);return r += n;
 Iterator operator-(int n) const Iterator r(*this);return r -= n;

 difference_type operator-(Iterator const& r) const return i - r.i;

 // Note: comparing iterator from different containers
 // is undefined behavior so we don't need to check
 // if they are the same container.
 bool operator<(Iterator const& r) const return i < r.i;
 bool operator<=(Iterator const& r) const return i <= r.i;
 bool operator>(Iterator const& r) const return i > r.i;
 bool operator>=(Iterator const& r) const return i >= r.i;
 bool operator!=(const Iterator &r) const return i != r.i;
 bool operator==(const Iterator &r) const return i == r.i;

private:
 Vector<T>* v;
 int i;
;

The Container.

Since you were asking about Iterators I will not give input on the Vector just yet (but lets say it needs work).

I have written a couple of articles on implementing the vector that you can have a look at.

http://lokiastari.com/series/

The definition of the range based for is to use Koenig lookup (also know as ADNL) to see if there is an appropriate version of the function begin(). If the compiler does not find an appropriate function it will use std::begin() instead. — Aug 24 at 22:14
@user3132457: I have added a new section How to think of range based for to explain how to think of the range based for. — Aug 24 at 22:20

score 6 · Answer 3 · 2018-08-22 17:15:04Z

In cariehl's answer you've already learned about implementing your iterator as a pointer, which would simplify the class significantly. Iterators were originally designed to mimic pointers, a pointer is an iterator. But it's nice to have a dedicated class as your iterator, because C++ is all about types, you want to let the compiler check your types and give error messages if things don't match.

Style

class Vector is a common name, and likely to clash. So is VECTOR_H as an include guard. I would suggest that you always use namespaces, even if you don't think you'll re-use the code later in a larger project.

In C++, it is preferred to write const T& value (or even T const& value) rather than const T &value. The & is part of the type, and so should be close to the type, not to the variable name.

Constructor

Your constructor Vector(int nCapacity) sets the capacity, and leaves size at 0. This is not the behavior of std::vector, and therefore could be confusing. If you call Vector(0) you'll allocate an array of size 0, which is UB (as far as I know).

Destructor

Your destructor:

template <typename T>
Vector<T>::~Vector()

 delete m_pData;
 m_nSize = 0;
 m_nCapacity = 0;

sets member variable values. This is unnecessary, as the destructor is called when the object ceases to exist. There is no need to leave it in a consistent state. You also have the bug that cariehl's answer mentioned: delete m_pData.

However, ideally you don't have a destructor at all. If you store your pointer in a std::unique_ptr<T> instead of T*, you can skip writing a destructor.

By not writing a destructor, the compiler will automatically generate a move assignment and a move constructor for you. Currently, your class is not copyable or movable. To make it copyable, you'll have to explicitly write a copy constructor and assignment operator, since std::unique_ptr is not copyable.

Insertion

The Vector::insert method uses a loop to copy data:

for (auto idx = 0; idx < m_nSize; ++idx)
 pNewMemory[idx] = m_pData[idx];

This could be inefficient. For one, you should be moving the data, not copying it. For T==int it doesn't matter, but for more complex types it does. You can use the algorithm std::move effectively to move the data (which is implemented as a fast memcpy if data is trivially copyable):

std::move(m_pData, m_pData + m_nSize, pNewMemory);

You'll need to include <algorithm> for this.

Now you need to change the signature for your insert(const T &value) function to be insert(T value). Then:

m_pData[m_nSize] = value;

becomes:

m_pData[m_nSize] = std::move(value);

Now the copy is made when you call the function, rather than inside the function. The advantage is that if the value used when calling the function is temporary, or you explicitly std::move it, no copy will be made at all.

Exceptions

throw std::exception("Index out of range");

is not legal C++, as std::exception doesn't have such a constructor. Instead, use std::runtime_error or std::logic_error, or even std::range_error, which is derived from std::runtime_error and used by the standard library exactly for this type of error.

@TobySpeight what do you mean by "pair f(const T&) with f(T&&)"? — Aug 22 at 17:12
@user3132457, sorry for being too terse; I meant an overloaded pair: e.g. f(const T&) (which copies from its argument) and f(T&&) (which moves from its argument). It's simpler to write a single function f(T) (move from the argument), as that reduces duplication. — Aug 22 at 17:17
@user3132457, here's some helpful advice that mentions how to present your updated code: what you may and may not do after receiving answers. — Aug 22 at 19:52

user3132457 514 · Answer 4 · 2018-08-24 17:15:22Z

Thanks everyone for answers. I have added/changed my code based on your advice. Please find the updated version below.

Vector.h

#ifndef VECTOR_H
#define VECTOR_H

#include <stdexcept>
#include <cstddef>
#include <algorithm>

namespace Simple


template <typename T>
class Vector

 using value_type = T;
 using difference_type = std::ptrdiff_t;
 using pointer = T *;
 using reference = T &;

public:
 /* The iterator */
 class Iterator
 
 using value_type = T;
 using difference_type = std::ptrdiff_t;
 using pointer = T *;
 using reference = T &;
 using iterator_category = std::random_access_iterator_tag;

 public:
 Iterator() = default;
 Iterator(Vector<T> *pVector, std::size_t nIndex) : m_pVector(pVector), m_nIndex(nIndex) 

 reference operator*() return (*m_pVector)[m_nIndex]; 
 const reference &operator*() const return (*m_pVector)[m_nIndex]; 
 pointer operator->() return &((*m_pVector)[m_nIndex]); 
 const pointer operator->() const return &((*m_pVector)[m_nIndex]); 
 reference operator(int offset) return (*m_pVector)[m_nIndex + offset]; 
 const reference operator(int offset) const return (*m_pVector)[m_nIndex + offset]; 

 Iterator &operator++() ++m_nIndex; return *this; 
 Iterator &operator--() --m_nIndex; return *this; 
 Iterator operator++(int) Iterator it(*this); ++m_nIndex; return *this; 
 Iterator operator--(int) Iterator it(*this); --m_nIndex; return *this; 

 Iterator &operator+=(int offset) m_nIndex += offset; return *this; 
 Iterator &operator-=(int offset) m_nIndex -= offset; return *this; 

 Iterator operator+(int offset) const Iterator it(*this); return it += offset; 
 Iterator operator-(int offset) const Iterator it(*this); return it -= offset; 

 difference_type operator-(const Iterator &other) const return m_nIndex - other.m_nIndex; 

 // Note: comparing iterator from different containers
 // is undefined behavior so we don't need to check
 // if they are the same container.
 bool operator< (const Iterator &other) const return m_nIndex < other.m_nIndex; 
 bool operator<= (const Iterator &other) const return m_nIndex <= other.m_nIndex; 
 bool operator> (const Iterator &other) const return m_nIndex > other.m_nIndex; 
 bool operator>= (const Iterator &other) const return m_nIndex >= other.m_nIndex; 
 bool operator== (const Iterator &other) const return m_nIndex == other.m_nIndex; 
 bool operator!= (const Iterator &other) const return m_nIndex != other.m_nIndex; 

 private:
 Vector<value_type> *m_pVector = nullptr;
 std::size_t m_nIndex = 0;
 ;

public:
 // constructors
 Vector() = default;
 explicit Vector(std::size_t nCapacity);

 void insert(value_type value);

 std::size_t size() const;

 reference operator(std::size_t nIndex);
 const reference operator(std::size_t nIndex) const;

 Iterator begin();
 Iterator end();

private:
 void resizeIfRequired();
 void detectCapacity();
 void allocateMemory();

private:
 std::unique_ptr<value_type> m_pData nullptr ;
 std::size_t m_nSize = 0;
 std::size_t m_nCapacity = 0;
;

/*
 * Vector methods
 **/
template <typename T>
Vector<T>::Vector(std::size_t nCapacity)

 if (nCapacity > 0)
 
 m_nCapacity = nCapacity;
 m_pData = std::make_unique<value_type>(nCapacity);
 


template <typename T>
void Vector<T>::insert(value_type value)

 resizeIfRequired();

 // insert the new element
 m_pData[m_nSize] = std::move(value);
 ++m_nSize;


template <typename T>
std::size_t Vector<T>::size() const

 return m_nSize;


template <typename T>
typename Vector<T>::reference Vector<T>::operator(std::size_t nIndex)

 if (nIndex >= m_nSize)
 throw std::exception("Index out of range");

 return m_pData[nIndex];


template <typename T>
typename const Vector<T>::reference Vector<T>::operator(std::size_t nIndex) const

 return operator(nIndex);


template <typename T>
typename Vector<T>::Iterator Vector<T>::begin()

 return Vector<T>::Iterator this, 0 ;


template <typename T>
typename Vector<T>::Iterator Vector<T>::end()

 return Vector<T>::Iterator this, m_nSize ;


template <typename T>
void Vector<T>::resizeIfRequired()

 if (m_nSize == m_nCapacity)
 
 detectCapacity();
 allocateMemory();
 


template <typename T>
void Vector<T>::detectCapacity()

 if (m_nCapacity == 0)
 
 m_nCapacity = 1;
 m_pData = std::make_unique<T>(m_nCapacity);
 
 else
 m_nCapacity *= 2;


template <typename T>
void Vector<T>::allocateMemory()

 // allocate new memory
 auto pNewMemory = new T[m_nCapacity];

 // move data to there
 std::move(m_pData.get(), m_pData.get() + m_nSize, pNewMemory);

 m_pData.reset(pNewMemory);


 // namespace Simple

#endif // !VECTOR_H

main.cpp

#include <iostream>

#include "Vector.h"

int main()

 try
 
 Simple::Vector<int> vector;
 vector.insert(8);
 vector.insert(3);
 vector.insert(1);
 vector.insert(7);
 vector.insert(2);

 for (auto i : vector)
 std::cout << i << std::endl;
 
 catch (const std::exception &e)
 
 std::cerr << e.what() << std::endl;
 

 std::cin.get();
 return 0;

When we suggested you write the iteration using a pointer, we didnÃ¢Â€Â™t mean storing a pointer to the Vector object, but rather a pointer to the data inside the vector. All you need to store inside your iterator is a single value of type pointer. Try that out, youÃ¢Â€Â™ll see how much simpler the iterator becomes. — Aug 31 at 13:11

score 12 · Answer 5 · 2018-08-21 20:34:07Z

Use `delete`

You are allocating an array of objects with new, but attempting to delete them with delete, which results in undefined behavior. You should delete the array with delete to ensure that your code functions properly. Do this in both Vector<T>::~Vector() and Vector<T>::insert().

Implement your `Iterator`s as pointers under-the-hood

Since your data is stored sequentially, it makes sense to implement your Iterator members as a simple T const * rather than a pointer to the parent Vector<T> and an index. This cuts down the size of your Iterator, and avoids the awkward m_nIndex = -1 state. You can replace the Iterator's internals in this way without changing its interface.

(As a side note, the range-based for-loop would still function if you completely removed the Iterator class and just returned T const * from Vector<T>::begin() and Vector<T>::end(). I know this is not what you asked, but thought you might like to know! Example)

Construct member variables in the constructor initializer list

You are already using a member initializer list for your Iterator class, so you should do the same for Vector<T>

template <typename T>
Vector<T>::Vector(int nCapacity)
 : m_nCapacity(nCapacity)
 , m_pData(new T[nCapacity])

Use `size_t` for container size

A small detail, but using size_t instead of int for Vector<T>::size more closely resembles the standard library's containers. It is a very standard way of representing sizes.

Actually, many consider unsigned integer types for sizes one of the bigger mistakes of the standard library because of how they interact with signed values (e.g. for(int i = 0; i < vec.size() - 5; ++i) contains a serious bug). Unsigned size values got introduces as a hack/workaround to allow one more bit worth of possible storage space. It cannot be officially fixed now, because it would break backwards compatibility. But for new containers? There's no precedent, so I'd actually suggest using signed values for sizes (we don't need that extra bit for modern 64.bit architectures). — Aug 21 at 23:00
@hoffmale, do you have any guarantee that the code will only ever be built for "modern 64.bit architectures"? 16-bit int hasn't just stopped existing, you know. — Aug 22 at 8:12
@TobySpeight: Well, yes, 8-bit and 16-bit platforms still do exist. However, most of those have some kind of advanced addressing mode to allow for addressing more than 256 Bytes/65.536 Bytes respectively (e.g. far pointers). Unless your usage scenario requires you to have 50%+ of the addressable memory in a container of 1 Byte sized objects, that one extra bit of size information isn't needed. And if that is your usage scenario, it might be advisable to rethink your platform choice and/or write a specialized container, since you're likely to have very harsh memory constraints anyways. — Aug 22 at 8:27
My point is that int isn't necessarily wide enough to represent the size of the container - you might need long, for example (common on machines with 16-bit word size and 32-bit addressing for example). std::size_t is automatically the right width for the size of any object. — Aug 22 at 8:49
Sorry @hoffmale - I'd formed an image in my mind that you'd said int when you hadn't. I was wrong! — Aug 22 at 17:22

score 11 · Answer 6 · 2018-08-24 22:28:51Z

The range-based `for` loop

This works via the begin() and end() functions.

So for any class X if there are stand alone functions begin(X&) and end(X&) the range based for will work. Normally this will default to the std::begin() and std::end() but if you have written explicit versions of these functions in the same namespace as X these will be used.

Example:

#include <iostream>

namespace Y

 class X
 
 public:
 char data[14] = "This is text";
 ;

 char* begin(X& obj) 
 return obj.data;
 

 char* end(X& obj) 
 return obj.data + 10;
 


int main()

 Y::X x;
 for(auto const& a: x) 
 std::cout << a;

OK. So what happens if you don't write your own begin() and end() functions?

In this case it will use the standard versions of these functions. std::begin() which will call the begin() method on the object and std::end() which will call the end() method on the object.

Example 2:

#include <iostream>

namespace Y

 class X
 
 char data[14] = "This is text";
 public:
 char* begin() 
 return data;
 

 char* end() 
 return data + 10;
 
 ;


int main()

 Y::X x;
 for(auto const& a: x) 
 std::cout << a;

How to think of range based for

You can think of ranged based for as a compiler shortcut.

for(<Type> <Var> : <Obj>) 
 <CODE>

Is just short hand for:


 using std::begin;
 using std::end;

 auto __end = end(<Obj>);

 for(auto __loop = begin(<Obj>); __loop != __end; ++__loop) 
 <Type> <Var> = *__loop;
 <CODE>

Implementation of Iterators

The implementation of an iterator is based on the "Iterator Concept". There are actually five types of iterator in C++. But since you are using vector as your example implementation we should consider the "Random Access Iterator Concept".

To qualify as a random access iterator you have to uphold a specific contract. Here is some documentation on it.

https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator

Not only does the iterator need to define certain methods (with specific requirements on how they work together). But your type also needs to define certain types via std::iterator_traits.

Types

You need to define the following types:

value_type:

When the iterator is de-referenced this is the type you get.

difference_type:

When you subtract two iterators this is the type of the result

pointer:

A type that points at type value_type

reference:

A type that can be used as a reference to a value of type value_type

iterator_category:

A type that represents the category of the iterator.

So you could have written your own specialization of the iterator_traits class

namespace std

 template<typename T>
 class iterator_traits<Vector<T>::Iterator>
 
 using value_type = T;
 using difference_type = std::ptrdiff_t;
 using pointer = T*;
 using reference = T&;
 using iteratory_category = std::random_access_iterator_tag;
 ;

But that is a little bit like actual hard work. The designers of the STL actually got smart and the default implementation of this type refer back to the iterator type to get these types. So you can define these types in your iterator (and not define a specialization of the iterator_traits class).

Rather do this:

template<typename T>
class Vector

 class Iterator
 
 using value_type = T;
 using difference_type = std::ptrdiff_t;
 using pointer = T*;
 using reference = T&;
 using iterator_category = std::random_access_iterator_tag;
 ;
 ....

Note: If you follow the advice above and use a pointer as your iterator. The iterator_traits for pointer types are well defined in the standard and no work is required.

Properties of an Iterator

The basic properties of an iterator are:

Default Constructible *** Currently not supported.

Copy Constructible

Copy Assignable

Destructible

Swappable *** Currently not supported.

Equality Comparable *** Currently not supported (you need ==)

objects returned via de-referencing need to be mutable (not supported)

Supported actions for a random access iterator:

*i // returns the current value
*i = v // Assign value `v` to the value dererenced.
++i // increments the iterator (returns a reference)
--i // See above
i++ // increments the iterator (but returns a reference to the original)
i-- // See above
*i++ // returns the current value and increments the iterator
*i-- // See above

i += n // Moves the iterator forward
i -= n // Same as last one
i + n // Creates a new iterator moved forward from i
n + i // Same as last one
i - n // Same as last one

i1 - i2 // returns the distance between the iterators.

i[n] // returns the item n steps forward from this iterator.
i->m // Access the member `m` referenced by i

i1 < i2 // Compare iterators
i1 > i2
i1 <= i2
i1 >= i2
i1 == i2
i1 != i2

OK So I have dumped an all lot of requirements on iterators here. But it is not as bad as it seems. Have a look at an iterator I built for a stack overflow question.

https://stackoverflow.com/a/1120224/14065

This iterator is only a forward iterator (so it has fewer requirements). But it shows you how to implement the main basic requirements very quickly. The rest should not be too hard to implement for random accesses iterator.

Got bored so here:

class Iterator

public:
 using value_type = T;
 using pointer = T*;
 using reference = T&;
 using difference_type = std::ptrdiff_t;
 using iterator_category = std::random_access_iterator_tag;

 Iterator(): v(nullptr), i(0) 
 Iterator(Vector<T>* v, int i): v(v), i(i) 
 // Default Copy/Move Are Fine.
 // Default Destructor fine.

 reference operator*() return (*v)[i];
 const reference operator*() const return (*v)[i];
 pointer operator->() return &((*v)[i]);
 const pointer operator->() const return &((*v)[i]);
 reference operator(int m) return (*v)[i + m];
 const reference operator(int m) const return (*v)[i + m];


 Iterator& operator++() ++i;return *this;
 Iterator& operator--() --i;return *this;
 Iterator operator++(int) Iterator r(*this);++i;return r;
 Iterator operator--(int) Iterator r(*this);--i;return r;

 Iterator& operator+=(int n) i += n;return *this;
 Iterator& operator-=(int n) i i= n;return *this;

 Iterator operator+(int n) const Iterator r(*this);return r += n;
 Iterator operator-(int n) const Iterator r(*this);return r -= n;

 difference_type operator-(Iterator const& r) const return i - r.i;

 // Note: comparing iterator from different containers
 // is undefined behavior so we don't need to check
 // if they are the same container.
 bool operator<(Iterator const& r) const return i < r.i;
 bool operator<=(Iterator const& r) const return i <= r.i;
 bool operator>(Iterator const& r) const return i > r.i;
 bool operator>=(Iterator const& r) const return i >= r.i;
 bool operator!=(const Iterator &r) const return i != r.i;
 bool operator==(const Iterator &r) const return i == r.i;

private:
 Vector<T>* v;
 int i;
;

The Container.

Since you were asking about Iterators I will not give input on the Vector just yet (but lets say it needs work).

I have written a couple of articles on implementing the vector that you can have a look at.

http://lokiastari.com/series/

The definition of the range based for is to use Koenig lookup (also know as ADNL) to see if there is an appropriate version of the function begin(). If the compiler does not find an appropriate function it will use std::begin() instead. — Aug 24 at 22:14
@user3132457: I have added a new section How to think of range based for to explain how to think of the range based for. — Aug 24 at 22:20

score 6 · Answer 7 · 2018-08-22 17:15:04Z

In cariehl's answer you've already learned about implementing your iterator as a pointer, which would simplify the class significantly. Iterators were originally designed to mimic pointers, a pointer is an iterator. But it's nice to have a dedicated class as your iterator, because C++ is all about types, you want to let the compiler check your types and give error messages if things don't match.

Style

class Vector is a common name, and likely to clash. So is VECTOR_H as an include guard. I would suggest that you always use namespaces, even if you don't think you'll re-use the code later in a larger project.

In C++, it is preferred to write const T& value (or even T const& value) rather than const T &value. The & is part of the type, and so should be close to the type, not to the variable name.

Constructor

Your constructor Vector(int nCapacity) sets the capacity, and leaves size at 0. This is not the behavior of std::vector, and therefore could be confusing. If you call Vector(0) you'll allocate an array of size 0, which is UB (as far as I know).

Destructor

Your destructor:

template <typename T>
Vector<T>::~Vector()

 delete m_pData;
 m_nSize = 0;
 m_nCapacity = 0;

sets member variable values. This is unnecessary, as the destructor is called when the object ceases to exist. There is no need to leave it in a consistent state. You also have the bug that cariehl's answer mentioned: delete m_pData.

However, ideally you don't have a destructor at all. If you store your pointer in a std::unique_ptr<T> instead of T*, you can skip writing a destructor.

By not writing a destructor, the compiler will automatically generate a move assignment and a move constructor for you. Currently, your class is not copyable or movable. To make it copyable, you'll have to explicitly write a copy constructor and assignment operator, since std::unique_ptr is not copyable.

Insertion

The Vector::insert method uses a loop to copy data:

for (auto idx = 0; idx < m_nSize; ++idx)
 pNewMemory[idx] = m_pData[idx];

This could be inefficient. For one, you should be moving the data, not copying it. For T==int it doesn't matter, but for more complex types it does. You can use the algorithm std::move effectively to move the data (which is implemented as a fast memcpy if data is trivially copyable):

std::move(m_pData, m_pData + m_nSize, pNewMemory);

You'll need to include <algorithm> for this.

Now you need to change the signature for your insert(const T &value) function to be insert(T value). Then:

m_pData[m_nSize] = value;

becomes:

m_pData[m_nSize] = std::move(value);

Now the copy is made when you call the function, rather than inside the function. The advantage is that if the value used when calling the function is temporary, or you explicitly std::move it, no copy will be made at all.

Exceptions

throw std::exception("Index out of range");

is not legal C++, as std::exception doesn't have such a constructor. Instead, use std::runtime_error or std::logic_error, or even std::range_error, which is derived from std::runtime_error and used by the standard library exactly for this type of error.

@TobySpeight what do you mean by "pair f(const T&) with f(T&&)"? — Aug 22 at 17:12
@user3132457, sorry for being too terse; I meant an overloaded pair: e.g. f(const T&) (which copies from its argument) and f(T&&) (which moves from its argument). It's simpler to write a single function f(T) (move from the argument), as that reduces duplication. — Aug 22 at 17:17
@user3132457, here's some helpful advice that mentions how to present your updated code: what you may and may not do after receiving answers. — Aug 22 at 19:52

user3132457 514 · Answer 8 · 2018-08-24 17:15:22Z

Thanks everyone for answers. I have added/changed my code based on your advice. Please find the updated version below.

Vector.h

#ifndef VECTOR_H
#define VECTOR_H

#include <stdexcept>
#include <cstddef>
#include <algorithm>

namespace Simple


template <typename T>
class Vector

 using value_type = T;
 using difference_type = std::ptrdiff_t;
 using pointer = T *;
 using reference = T &;

public:
 /* The iterator */
 class Iterator
 
 using value_type = T;
 using difference_type = std::ptrdiff_t;
 using pointer = T *;
 using reference = T &;
 using iterator_category = std::random_access_iterator_tag;

 public:
 Iterator() = default;
 Iterator(Vector<T> *pVector, std::size_t nIndex) : m_pVector(pVector), m_nIndex(nIndex) 

 reference operator*() return (*m_pVector)[m_nIndex]; 
 const reference &operator*() const return (*m_pVector)[m_nIndex]; 
 pointer operator->() return &((*m_pVector)[m_nIndex]); 
 const pointer operator->() const return &((*m_pVector)[m_nIndex]); 
 reference operator(int offset) return (*m_pVector)[m_nIndex + offset]; 
 const reference operator(int offset) const return (*m_pVector)[m_nIndex + offset]; 

 Iterator &operator++() ++m_nIndex; return *this; 
 Iterator &operator--() --m_nIndex; return *this; 
 Iterator operator++(int) Iterator it(*this); ++m_nIndex; return *this; 
 Iterator operator--(int) Iterator it(*this); --m_nIndex; return *this; 

 Iterator &operator+=(int offset) m_nIndex += offset; return *this; 
 Iterator &operator-=(int offset) m_nIndex -= offset; return *this; 

 Iterator operator+(int offset) const Iterator it(*this); return it += offset; 
 Iterator operator-(int offset) const Iterator it(*this); return it -= offset; 

 difference_type operator-(const Iterator &other) const return m_nIndex - other.m_nIndex; 

 // Note: comparing iterator from different containers
 // is undefined behavior so we don't need to check
 // if they are the same container.
 bool operator< (const Iterator &other) const return m_nIndex < other.m_nIndex; 
 bool operator<= (const Iterator &other) const return m_nIndex <= other.m_nIndex; 
 bool operator> (const Iterator &other) const return m_nIndex > other.m_nIndex; 
 bool operator>= (const Iterator &other) const return m_nIndex >= other.m_nIndex; 
 bool operator== (const Iterator &other) const return m_nIndex == other.m_nIndex; 
 bool operator!= (const Iterator &other) const return m_nIndex != other.m_nIndex; 

 private:
 Vector<value_type> *m_pVector = nullptr;
 std::size_t m_nIndex = 0;
 ;

public:
 // constructors
 Vector() = default;
 explicit Vector(std::size_t nCapacity);

 void insert(value_type value);

 std::size_t size() const;

 reference operator(std::size_t nIndex);
 const reference operator(std::size_t nIndex) const;

 Iterator begin();
 Iterator end();

private:
 void resizeIfRequired();
 void detectCapacity();
 void allocateMemory();

private:
 std::unique_ptr<value_type> m_pData nullptr ;
 std::size_t m_nSize = 0;
 std::size_t m_nCapacity = 0;
;

/*
 * Vector methods
 **/
template <typename T>
Vector<T>::Vector(std::size_t nCapacity)

 if (nCapacity > 0)
 
 m_nCapacity = nCapacity;
 m_pData = std::make_unique<value_type>(nCapacity);
 


template <typename T>
void Vector<T>::insert(value_type value)

 resizeIfRequired();

 // insert the new element
 m_pData[m_nSize] = std::move(value);
 ++m_nSize;


template <typename T>
std::size_t Vector<T>::size() const

 return m_nSize;


template <typename T>
typename Vector<T>::reference Vector<T>::operator(std::size_t nIndex)

 if (nIndex >= m_nSize)
 throw std::exception("Index out of range");

 return m_pData[nIndex];


template <typename T>
typename const Vector<T>::reference Vector<T>::operator(std::size_t nIndex) const

 return operator(nIndex);


template <typename T>
typename Vector<T>::Iterator Vector<T>::begin()

 return Vector<T>::Iterator this, 0 ;


template <typename T>
typename Vector<T>::Iterator Vector<T>::end()

 return Vector<T>::Iterator this, m_nSize ;


template <typename T>
void Vector<T>::resizeIfRequired()

 if (m_nSize == m_nCapacity)
 
 detectCapacity();
 allocateMemory();
 


template <typename T>
void Vector<T>::detectCapacity()

 if (m_nCapacity == 0)
 
 m_nCapacity = 1;
 m_pData = std::make_unique<T>(m_nCapacity);
 
 else
 m_nCapacity *= 2;


template <typename T>
void Vector<T>::allocateMemory()

 // allocate new memory
 auto pNewMemory = new T[m_nCapacity];

 // move data to there
 std::move(m_pData.get(), m_pData.get() + m_nSize, pNewMemory);

 m_pData.reset(pNewMemory);


 // namespace Simple

#endif // !VECTOR_H

main.cpp

#include <iostream>

#include "Vector.h"

int main()

 try
 
 Simple::Vector<int> vector;
 vector.insert(8);
 vector.insert(3);
 vector.insert(1);
 vector.insert(7);
 vector.insert(2);

 for (auto i : vector)
 std::cout << i << std::endl;
 
 catch (const std::exception &e)
 
 std::cerr << e.what() << std::endl;
 

 std::cin.get();
 return 0;

When we suggested you write the iteration using a pointer, we didnÃ¢Â€Â™t mean storing a pointer to the Vector object, but rather a pointer to the data inside the vector. All you need to store inside your iterator is a single value of type pointer. Try that out, youÃ¢Â€Â™ll see how much simpler the iterator becomes. — Aug 31 at 13:11

Category

Random preview

Basic iterator supporting vector implementation

4 Answers 4

Use delete

Implement your Iterators as pointers under-the-hood

Construct member variables in the constructor initializer list

Use size_t for container size

The range-based for loop

How to think of range based for

Implementation of Iterators

Types

Properties of an Iterator

The Container.

Style

Constructor

Destructor

Insertion

Exceptions

Your Answer

Sign up or log in

Post as a guest

Post as a guest

4 Answers 4

4 Answers 4

Use delete

Implement your Iterators as pointers under-the-hood

Construct member variables in the constructor initializer list

Use size_t for container size

Use delete

Implement your Iterators as pointers under-the-hood

Construct member variables in the constructor initializer list

Use size_t for container size

Use delete

Implement your Iterators as pointers under-the-hood

Construct member variables in the constructor initializer list

Use size_t for container size

Use delete

Implement your Iterators as pointers under-the-hood

Construct member variables in the constructor initializer list

Use size_t for container size

The range-based for loop

How to think of range based for

Implementation of Iterators

Types

Properties of an Iterator

The Container.

The range-based for loop

How to think of range based for

Implementation of Iterators

Types

Properties of an Iterator

The Container.

The range-based for loop

How to think of range based for

Implementation of Iterators

Types

Properties of an Iterator

The Container.

The range-based for loop

How to think of range based for

Implementation of Iterators

Types

Properties of an Iterator

The Container.

Style

Constructor

Destructor

Insertion

Exceptions

Style

Constructor

Destructor

Insertion

Exceptions

Style

Constructor

Destructor

Insertion

Exceptions

4 Answers
4

Use `delete`

Implement your `Iterator`s as pointers under-the-hood

Use `size_t` for container size

The range-based `for` loop

4 Answers
4

4 Answers
4

Use `delete`

Implement your `Iterator`s as pointers under-the-hood

Use `size_t` for container size

Use `delete`

Implement your `Iterator`s as pointers under-the-hood

Use `size_t` for container size

Use `delete`

Implement your `Iterator`s as pointers under-the-hood

Use `size_t` for container size

Use `delete`

Implement your `Iterator`s as pointers under-the-hood

Use `size_t` for container size

The range-based `for` loop

The range-based `for` loop

The range-based `for` loop

The range-based `for` loop