4
\$\begingroup\$

I saw some question on SO lately involving circular buffer, like a chain of descriptors for data transfer. All solutions involved lots of lines.

I wanted an implementation with as few lines as possible, as inspired by this answer. The idea is not to have a circular buffer but a usual container and a specific iterator able to wrap.

Question: Is it possible to achieve this with as few lines as in the example below or are there hidden pitfalls ?

Additional information after first answers / comments

Similar 2009 question on SO mentioned by Mercury Dime (the question uses the term cyclic or circulator and not circular)

EDIT: Corrections of the more evident errors / typos based on incomputable's answer

#include <iostream>
#include <list>

template <class BaseIter>
class CircularIterator:public BaseIter {
        //inspired from https://stackoverflow.com/a/947754/3972710
        BaseIter begin,end;
    public:
        CircularIterator(BaseIter b, BaseIter e ):BaseIter(b), begin(b), end(e) {}
        CircularIterator & operator ++(void)
        {
            BaseIter::operator++();
            if(*this == end)
                BaseIter::operator=(begin);
            return *this;
        }
        const CircularIterator   operator ++(int)
        {
            const auto oldValue = *this;
            this->operator++();
            return oldValue;
        };

        CircularIterator & operator --(void) = delete;
        const CircularIterator   operator --(int)  = delete;
};

int main()
{
    std::list<int> intList = { 1, 2, 3};
    CircularIterator<std::list<int>::iterator> circIter(intList.begin(),intList.end());

    auto it = circIter++;

    std::cout << *(it++) << "\n";
    std::cout << *(it++) << "\n";
    std::cout << *(it++) << "\n";
    std::cout << *(it++) << "\n";
    std::cout << "..." << "\n";
    std::cout << "Hello world!\n";
    return 0;
}

Original Code

#include <iostream>
#include <list>
using namespace std;
//C++11 at least

template <class baseIter>
class circularIterator:public baseIter {
        //inspired from https://stackoverflow.com/a/947754/3972710
        baseIter begin,end;
    public:
        circularIterator(baseIter b, baseIter e ):baseIter(b), begin(b), end(e) {}
        baseIter & operator ++(void) {  baseIter::operator++();
                                        if(*this == end) baseIter::operator=(begin);
                                        return *this;}
        baseIter & operator ++(int) = delete;
};

int main()
{
    list<int> intList = { 1, 2, 3};
    circularIterator<list<int>::iterator> circIter(intList.begin(),intList.end());

    cout << *circIter << endl;
    cout << *(++circIter) << endl;
    cout << *(++circIter) << endl;
    cout << *(++circIter) << endl;
    cout << *(++circIter) << endl;
    cout << "..." << endl;

    cout << "Hello world!" << endl;
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ std::list uses bidirectional iterators. *(--circIter) with circIter = begin will cause problems in your example. std::vector uses random access iterators, which will introduce even more problems. \$\endgroup\$ – Mercury Dime Jun 16 '17 at 1:55
  • \$\begingroup\$ @MercuryDime, I don't see how that is relevant (I'm not OP). Getting out of the range is problem of the user. \$\endgroup\$ – Incomputable Jun 17 '17 at 10:32
  • \$\begingroup\$ You're right, I'm getting confused as to what should happen internally with memory (wrap around end), and what should happen with the iterators. (they don't wrap) This is what I was thinking of: link \$\endgroup\$ – Mercury Dime Jun 17 '17 at 19:20
  • \$\begingroup\$ @MercuryDime, I'm not really sure what you wanted to say about the linked post. Could you please clarify? \$\endgroup\$ – Incomputable Jun 18 '17 at 6:46
  • \$\begingroup\$ In my first post, my thinking was - "the iterator needs to wrap around both ends". (as shown in Thomas Witt's code in the link) I was wrong. \$\endgroup\$ – Mercury Dime Jun 18 '17 at 15:39
2
\$\begingroup\$

High level overview:

The idea is solid, but creating an iterator adapter to make the container behave differently just sounds weird. It would be better to have container adapters, as std::stack<> and std::queue<> do.

Implementation overview:

The code has a serious issues. Mainly the following:

  • It has a chance to break on some algorithms:

    auto second = ++first;
    

where first is circularIterator<> will make second to be baseIter. The most dangerous ones are sorting algorithms, especially those that use divide and conquer. The template type parameter is usually only one, e.g. only one type of iterators are allowed, as a result the compiler will issue substitution failure error.

  • Will not work on idiomatic while (*first++ != last) or similar.

The postfix increment is deleted, thus it disables probably most of the standard library.

  • The class pretends to be an iterator, but is a range.

Usually iterator should know about its own internal state only. Knowing end iterator should be last resort. Actually, the reason for storing the range is because the code doesn't provide a function to create a pair of circularIterators. If such function would be provided, the operator==() of parent iterator would still work, as they mostly take it by reference.

Cosmetics:

Not really important, but here they are:

  • Usually people name types (and classes, as a result) in CamelCase or snake_case. camelCase starting from regular letter are used for variable names.

  • Template type parameters are named using CamelCase, since in the future they will probably become Concepts.

  • Indentation and brace placing is very weird.

Misc:

\$\endgroup\$
  • \$\begingroup\$ I hope I corrected the most evident errors / typos I made, like returning BaseIter instead of CircularIterator for the ++ operator. I added a few lines even if I had "packed" my code so that length was minimal. As I am only looking for forward iterator in my case I deleted the -- operators... Let me time to think about your other architectural proposals \$\endgroup\$ – NGI Jun 18 '17 at 21:32
  • 1
    \$\begingroup\$ @NGI, on CodeReview changing code means invalidating answers. Please post a follow up instead when you're fully ready. \$\endgroup\$ – Incomputable Jun 18 '17 at 21:34
  • \$\begingroup\$ My excuses. I put again the original code at the end of the question. Some errors were big enough to be corrected so that I prefer to leave this update anyway, but I take into account your advice to publish the new code only when fully done \$\endgroup\$ – NGI Jun 18 '17 at 21:51
  • \$\begingroup\$ @NGI, there is nothing with original code. It works, though may lead to traps. \$\endgroup\$ – Incomputable Jun 18 '17 at 21:53

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.