Bidirectional iterator implementation

Question

By some reasons I need to implement a bidirectional iterator, after some time, I got this result (add parameter tells what the side the iterator should move to (to avoid code duplication, when implementing reverse_iterator)):

#include <iterator>

namespace gph {
    template <typename T, int add> class BidirectionalIterator;

    template<typename T, int add>
    void swap(BidirectionalIterator<T, add>& it1, BidirectionalIterator<T, add>& it2) {
        it1.swap(it2);
    }

    template<typename T, int add>
    class BidirectionalIterator {
    private:
        T *currentPosition, *begin, *end;
    public:
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;
        using iterator_category = std::bidirectional_iterator_tag;

        inline BidirectionalIterator(T* currentPosition, T* begin, T* end):currentPosition(currentPosition), begin(begin), end(end) {}

        //copy constructor
        inline BidirectionalIterator(const BidirectionalIterator& iterator)
            :BidirectionalIterator(iterator.currentPosition, iterator.begin, iterator.end) {}

        //move constructor
        inline BidirectionalIterator(BidirectionalIterator&& iterator) noexcept
            :BidirectionalIterator(iterator.currentPosition, iterator.begin, iterator.end) {}

        //copy and move assignment statement
        inline BidirectionalIterator& operator=(BidirectionalIterator iterator) {
           gph::swap(*this, iterator);
        }

        inline void swap(BidirectionalIterator& iterator) {
            std::swap(currentPosition, iterator.currentPosition);
            std::swap(begin, iterator.begin);
            std::swap(end, iterator.end);
        }

        inline reference operator*() const {
            return *currentPosition; //dangerous if the iterator is in not-dereferenceable state
        }

        inline BidirectionalIterator& operator++() {
            if (currentPosition != end) currentPosition += add;

            return *this;
        }

        inline bool operator==(const BidirectionalIterator& iterator) const {
            return currentPosition == iterator.currentPosition;
        }

        inline bool operator!=(const BidirectionalIterator& iterator) const {
            return !(*this == iterator);
        }

        inline BidirectionalIterator operator++(int) {
            BidirectionalIterator past = *this;

            ++*this;

            return past;
        }

        inline BidirectionalIterator& operator--() {
            if (currentPosition != begin) currentPosition -= add;

            return *this;
        }

        inline BidirectionalIterator operator--(int) {
            BidirectionalIterator past = *this;

            --*this;

            return past;
        }
    };
}

I've tried to satisfy MoveAssignable, MoveConstructible, CopyAssignable, CopyConstructible, Swappable, EqualityComparable, LegacyIterator, LegacyInputIterator, LegacyForwardIterator, LegacyBidirectionalIterator named requirements.

Some of their requirements are expressed in operators overloading, but some ones from them I do not know how to implement (perhaps, they are automatically implemented by other ones?), for instance: i->m or *i++ (from here). First question: how should I implement them?

Second question: is my iterator implementation good? What are its drawbacks, where did I make mistakes?

P.S. The questions are on edge of unconstructiveness, but I really need help with it. Sorry for my english.

Lukas-T · Accepted Answer · 2019-11-01T15:58:17.450

1

I find it hard to find a definitive answer to this, so just some thoughts, which may be uncomplete and are open to discussion.

i->m can be implemented by inline pointer operator->() { return this->currentPosition; }
*i++ should already be covered by your implementation
I don't see any reason to swap all the pointers in operator=. For three reasons:
1. You are swapping the values with a local variable
2. The move constructor doesn't swap any values (would be inconsistent behaviour between BidirectionalIterator newIt=oldIt; and BidirectionalIterator newIt(oldIt);, but it actually isn't because of the previous point)
3. Those pointers are not unique resources, so there is no problem in copying them and sharing them between multiple instances
operator= is missing a return.
You have using difference_type = std::ptrdiff_t; but don't implement operator- which would return difference_type, why not implement it?
Reverse iterators can be implemented easier by std::reverse_iterator which will just wrap your iterator and invert ++ and -- and so on.
You probably want to find an easy way to implement a const version of the iterator (a version that always returns a const T& or const T*). I saw three versions of this:
- duplicating all the code
- using const cast
- using an additional template parameter bool TIsConst and using pointer = std::conditional_t<TIsConst, const T*, T*>;
- using a templated iterator with parameter const T on the other hand might appear easy, but fails to satisfy a requirement, see this question

edited Nov 01 '19 at 15:58

answered Oct 31 '19 at 22:23

Lukas-T

11,133
3
20
30

I thought I can implement const iterator just by passing i.e. const char to template. Can I do so? – wcobalt Nov 01 '19 at 07:12
Also, I'm swapping pointers with a local variable, because I'm implementing copy and swap idiom, so local variable is that copy – wcobalt Nov 01 '19 at 07:45
@wcobalt When assigning, you copy the right hand side of the assignment (using copy constructor), then you swap the values with some local variable. But the local variable will go out of scope and the original rhs of = will be unchanged. So the whole swapping is unneccesary there. Basically does the same as just copying the values. – Lukas-T Nov 01 '19 at 08:36
@wcobalt as for the idea to use essentially `const T` as template parameter - I'm not sure _why_ this isn't done, but there has to be some problem with it, since you don't find this pattern anywhere, I'm going to do some research on this. – Lukas-T Nov 01 '19 at 08:39
" When assigning, you copy the right hand side..." but if in move-constructor I would make swap then everything would be fine, right? – wcobalt Nov 01 '19 at 09:18
@wcobalt no, I think you don't need to swap anything, neither in the move-constructor nor in `operator=`. There is simply no reason to do this. The requirements for `MoveConstrutible` and `MoveAssignable` state, that the new value of rhs is undefined. So copying those values will also satisfy this condition. – Lukas-T Nov 01 '19 at 09:48
If I got it right, here (and at second answer too) ( https://stackoverflow.com/a/3582733/11681638 ) it suggests to implement `const iterator` through passing `const T` to template. So I see no reason why it is bad – wcobalt Nov 01 '19 at 13:25
I too was unsure now and asked it myself, using `const T` makes it harder to convert a iterator to a const_iterator. You can read everything in [this question](https://stackoverflow.com/questions/58661203/what-is-the-correct-way-to-implement-iterator-and-const-iterator-in-c17/58661978#58661978) – Lukas-T Nov 01 '19 at 15:56

Bidirectional iterator implementation

1 Answers1