Create Iterator to C++ container that returns a std::pair

Question

I'm trying to implement a container in C++ that uses a flat array to store the data but iterates over that data in pairs. Now I could easily change the implementation such that the container holds a vector of std::pair however I want to iterate through pairs starting at element 0 or at element 1.

To illustrate what I want to achieve, if my underlying array looks like: 1,2,3,4,5,6,7,8

I want to define two iterators, one which returns the pairs: (1,2), (3,4), (5,6), (7,8) and the second iterator to return the pairs: (2,3), (4,5), (6,7)

is this possible to do while still allowing the elements of the iterator to be references of the underlying array?

Answer 1

It is possible to write your own iterator, which iterates over the elements. The following question shows some explanations on how that is done: Custom Iterator in C++.

You can then return the desired values as std::pair and iterate to the next element-pair (by incrementing the counter by 2).

Answer 2

Boost library has got Iterator Adaptor that allows you to wrap other iterator types and change or adapt their functionality. Here's how you could use it for your purpose:

#include <boost/iterator/iterator_adaptor.hpp>
#include <vector>

struct iterator :
    public boost::iterator_adaptor<
        iterator,                    // the name of our class, see docs for details
        std::vector<int>::iterator,  // underlying base iterator
        std::pair<int&, int&>,       // our value type
        boost::forward_traversal_tag // the category you wish to give it
    >
{
     // need this to convert from vector::iterator to ours
    explicit iterator(std::vector<int>::iterator i)
        : iterator::iterator_adaptor_(i) {}

    value_type operator*()
    {
        return value_type(
            *base_reference(),
            *(base_reference()+1)
        );
    }
};

Example of usage:

std::vector<int> v {1,2,3,4};
iterator it(v.begin());
++it;
(*it).first = 0;  // TODO: operator->
(*it).second = 0;

for (int i : v) std::cout << i << ' '; // prints 1 0 0 4

You'll also need to override comparison to properly handle end condition, etc. Hope that helps.

Answer 3

Just thought I'd put in what I actually used in my code. I didn't want to use boost as suggested by @jrok but the type std::pair<int&, int&> in their answer gave me a hint of what was required.

Below is the class that I constructed which uses two iterators. A RepeatIterator that returns pairs starting on even indexes in the underlying data, and a SpacerIterator that returns pairs starting on odd indexes.

class RepeatArray {
    typedef std::vector<int> storage_t;

public:
    class RepeatIterator {
    public:
        typedef RepeatIterator self_t;
        typedef int value_t;
        typedef int& reference_t;
        typedef int* pointer_t;
        typedef std::pair<reference_t, reference_t> return_t;

        RepeatIterator(storage_t::iterator input) : current_pos(input){}

        return_t operator *() {
            return return_t(*(current_pos), *(current_pos + 1 ));
        }

        self_t operator++() { self_t i = *this; current_pos += 2; return i; }
        self_t operator++(int junk) { current_pos+=2; return *this; }


        bool operator==(const self_t& rhs) { return current_pos == rhs.current_pos; }
        bool operator!=(const self_t& rhs) { return current_pos != rhs.current_pos; }
        bool operator<(const self_t& rhs) { return current_pos < rhs.current_pos; }
        bool operator<=(const self_t& rhs) { return current_pos <= rhs.current_pos; }
        bool operator>(const self_t& rhs) { return current_pos > rhs.current_pos; }
        bool operator>=(const self_t& rhs) { return current_pos >= rhs.current_pos; }

    private:
        storage_t::iterator current_pos;
    };

    class SpacerIterator {
    public:
        typedef SpacerIterator self_t;
        typedef int value_t;
        typedef int& reference_t;
        typedef int* pointer_t;
        typedef std::pair<reference_t, reference_t> return_t;

        SpacerIterator(storage_t::iterator input) : current_pos(input){}

        return_t operator *() {
            return return_t(*(current_pos), *(current_pos + 1 ));
        }

        self_t operator++() { self_t i = *this; current_pos += 2; return i; }
        self_t operator++(int junk) { current_pos+=2; return *this; }

        bool operator==(const self_t& rhs) { return current_pos == rhs.current_pos; }
        bool operator!=(const self_t& rhs) { return current_pos != rhs.current_pos; }
        bool operator<(const self_t& rhs) { return current_pos < rhs.current_pos; }
        bool operator<=(const self_t& rhs) { return current_pos <= rhs.current_pos; }
        bool operator>(const self_t& rhs) { return current_pos > rhs.current_pos; }
        bool operator>=(const self_t& rhs) { return current_pos >= rhs.current_pos; }


    private:
        storage_t::iterator current_pos;
    };

    void add(int start, int end) {
        positions.push_back(start);
        positions.push_back(end);
    }

    void dump() {
        for (auto i : positions) {
            std::cout <<i<<",";
        }
        std::cout <<std::endl;
    }

    RepeatIterator repeatBegin(){return RepeatIterator(positions.begin());}
    RepeatIterator repeatEnd(){return RepeatIterator(positions.end());}

    SpacerIterator spacerBegin(){return SpacerIterator(positions.begin() + 1);}
    SpacerIterator spacerEnd(){return SpacerIterator(positions.end() - 1);}

protected:
    storage_t positions;
};

And then the tesing program compiled using clang++ -std=c++0x -o testRepeatArray RepeatArray.cpp

int main() {
    RepeatArray r = RepeatArray();
    r.add(1,3);
    r.add(7,12);
    std::cout<<"original:"<<std::endl;
    r.dump();

    std::cout << "Testing Repeat iterator:"<<std::endl;
    for (RepeatArray::RepeatIterator it2 = r.repeatBegin(); it2 != r.repeatEnd(); ++it2) {
        std::cout << (*it2).first <<","<< (*it2).second << std::endl;
    }
    std::cout << "Testing Spacer iterator:"<<std::endl;
    for (RepeatArray::SpacerIterator it3 = r.spacerBegin(); it3 != r.spacerEnd(); ++it3) {
        std::cout << (*it3).first <<","<< (*it3).second << std::endl;
    }

    std::cout<<"Testing modification:"<<std::endl;

    RepeatArray::RepeatIterator it = r.repeatBegin();
    (*it).first = 0;
    (*it).second = 123;

    r.dump();
    return 0;
}