10
\$\begingroup\$

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;
}
\$\endgroup\$
11
\$\begingroup\$

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/

\$\endgroup\$
  • \$\begingroup\$ how is obj passed to char *begin(X& obj)? \$\endgroup\$ – user3132457 Aug 24 '18 at 16:19
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin York Aug 24 '18 at 22:14
  • \$\begingroup\$ @user3132457: I have added a new section How to think of range based for to explain how to think of the range based for. \$\endgroup\$ – Martin York Aug 24 '18 at 22:20
12
\$\begingroup\$

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 Iterators 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.

\$\endgroup\$
  • 3
    \$\begingroup\$ 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). \$\endgroup\$ – hoffmale Aug 21 '18 at 23:00
  • \$\begingroup\$ @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. \$\endgroup\$ – Toby Speight Aug 22 '18 at 8:12
  • \$\begingroup\$ @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. \$\endgroup\$ – hoffmale Aug 22 '18 at 8:27
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Toby Speight Aug 22 '18 at 8:49
  • 1
    \$\begingroup\$ Sorry @hoffmale - I'd formed an image in my mind that you'd said int when you hadn't. I was wrong! \$\endgroup\$ – Toby Speight Aug 22 '18 at 17:22
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @TobySpeight what do you mean by "pair f(const T&) with f(T&&)"? \$\endgroup\$ – user3132457 Aug 22 '18 at 17:12
  • \$\begingroup\$ @TobySpeight: thanks for the corrections. I was sloppy. \$\endgroup\$ – Cris Luengo Aug 22 '18 at 17:15
  • \$\begingroup\$ @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. \$\endgroup\$ – Toby Speight Aug 22 '18 at 17:17
  • \$\begingroup\$ how can i put the updated code on here? \$\endgroup\$ – user3132457 Aug 22 '18 at 18:23
  • 1
    \$\begingroup\$ @user3132457, here's some helpful advice that mentions how to present your updated code: what you may and may not do after receiving answers. \$\endgroup\$ – Toby Speight Aug 22 '18 at 19:52
0
\$\begingroup\$

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(T *pData) : m_ptr(pData) {}

        reference       operator*()                     { return *m_ptr; }
        const reference &operator*()            const   { return *m_ptr; }
        pointer         operator->()                    { return m_ptr; }
        const pointer   operator->()            const   { return m_ptr; }
        reference       operator[](int offset)          { return m_ptr[offset]; }
        const reference operator[](int offset)  const   { return m_ptr[offset]; }

        Iterator &operator++()      { ++m_ptr; return *this; }
        Iterator &operator--()      { --m_ptr; return *this; }
        Iterator operator++(int)    { Iterator it(*this); ++m_ptr; return *this; }
        Iterator operator--(int)    { Iterator it(*this); --m_ptr; return *this; }

        Iterator &operator+=(int offset) { m_ptr += offset; return *this; }
        Iterator &operator-=(int offset) { m_ptr -= 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_ptr - other.m_ptr; }

        // 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_ptr < other.m_ptr; }
        bool operator<= (const Iterator &other) const   { return m_ptr <= other.m_ptr; }
        bool operator>  (const Iterator &other) const   { return m_ptr > other.m_ptr; }
        bool operator>= (const Iterator &other) const   { return m_ptr >= other.m_ptr; }
        bool operator== (const Iterator &other) const   { return m_ptr == other.m_ptr; }
        bool operator!= (const Iterator &other) const   { return m_ptr != other.m_ptr; }

    private:
        T *m_ptr{ nullptr };
    };

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::shared_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{ m_pData.get() };
}

template <typename T>
typename Vector<T>::Iterator Vector<T>::end()
{
    return Vector<T>::Iterator{ m_pData.get() + 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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Cris Luengo Aug 31 '18 at 13:11
  • \$\begingroup\$ Oh right, I just updated the code and now I see how much simpler it is. \$\endgroup\$ – user3132457 Sep 9 '18 at 7:18
  • \$\begingroup\$ I have made a few changes to your Iterator class so you can see what I meant. You don't need to store a pointer the data and an index. A single pointer can do it all. Click on the "edited" link to see the changes. Feel free to revert the edits, I just thought editing your code directly would be the easiest way to show what I meant. I hope you don't mind. :) \$\endgroup\$ – Cris Luengo Sep 10 '18 at 4:36
  • \$\begingroup\$ Thanks, that makes sense. Only one thing seems incorrect to me - in comparison operators the values of pointers are compared, not actual indexes. \$\endgroup\$ – user3132457 Sep 10 '18 at 6:14
  • \$\begingroup\$ Yes, that is the exact same behavior, though. If the two pointers point to addresses within the same memory block, then the comparisons and pointer arithmetic do exactly as you would want. \$\endgroup\$ – Cris Luengo Sep 10 '18 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.