Iterate over a list of directions

Question

I have an enumeration of directions with 6 directions (N, NE, SE, S, SW, NW), which are mostly edges of a node on the graph. I often need to iterate over all the neighbors that are currently being executed by iterating from 0-> 5 using only int.

Sometimes it also requires an iteration from, for example, 2-> 1, around which iteration is currently being performed from 2-> 2 + 5 and the use of mod 6 when used.

Is there anything I can do to make it safer / easier to use without losing performance? Fixed-range for loops can be expanded, bound, etc. Vector based approaches cannot (using a static constant vector inside an enumeration)

I already have an enumeration in the circuit like:

struct Direction{ enum Type{ N, NE, ... } unsigned COUNT = ...; Type t_; operator Type(){return t_;} Direction(Type t):t_(t){assert(N<=t<COUNT);} explicit Direction(unsigned t):t_(t%COUNT){} static Direction fromUInt(unsigned t){return Direction(Type(t));} } 

So, I would like to have iterators that allow iterating over the entire set efficiently, and also allow this for arbitrary starting points, in which case the iterator wraps around.

How can this be written? I can’t understand anything, like, for example, start = end for a whole loop that will be invalid. Or do I just need to run = givenStartType, end = start + COUNT and make modulo on each deref iterator?

No C ++ 11, unfortunately

Answer 1

EDIT in response to clarification

Your idea of ​​taking an iterator modulo COUNT for each dereference is a good one. See Inverse Iterative / Iterative Combination below. I checked the build output after compiling with clang using -O3 . The compiler has launched a loop. Output signal 2 1 0 5 4 3 . You can implement a forward iterator or make direction a parameter. You can also do this in a template by type of enumeration.

Unfortunately, in terms of usage syntax, I don’t think it buys you in the whole do - while , as shown by another answer - at least not until C ++ 11, It hides various index variables and helps to avoid errors with by them, but it is much more detailed.

 #include <iostream> struct Direction { enum Type {N, NE, SE, S, SW, NW}; static const unsigned COUNT = 6; Type t_; operator Type() { return t_; } Direction(Type t) : t_(t) { } explicit Direction(unsigned t) : t_(Type(t % COUNT)) { } }; struct ReverseIterable { const unsigned start_; struct iterator { unsigned offset_; explicit iterator(unsigned offset) : offset_(offset) { } Direction operator *() { return Direction(offset_); } iterator& operator++() { --offset_; return *this; } bool operator ==(const iterator &other) { return offset_ == other.offset_; } bool operator !=(const iterator &other) { return !(*this == other); } }; explicit ReverseIterable(Direction start) : start_(start) { } iterator begin() { return iterator(start_ + Direction::COUNT); } iterator end() { return iterator(start_); } }; int main() { ReverseIterable range = ReverseIterable(Direction::SE); for (ReverseIterable::iterator iterator = range.begin(); iterator != range.end(); ++iterator) { std::cout << (int)*iterator << " "; } std::cout << std::endl; return 0; } 

In C ++ 11, a loop can be:

  for (Direction direction : ReverseIterable(Direction::SE)) std::cout << (int)direction << " "; std::cout << std::endl; 

You can (ab?) Use a macro to get something like this in C ++ 98.

I retained the original answer below because it facilitates maintainability if the definition of an enum can change and because it allows sparse ranges. A very similar iterator can be implemented on top of it.

---

Original Security Oriented Answer

This may be a complete excess for your purpose, and it may not be suitable for the reason that I will discuss below. However, you can use this library (disclaimer: I am the author): https://github.com/aantron/better-enums write this code:

 #include <iostream> #include <enum.h> ENUM(Direction, int, N, NE, SE, S, SW, NW) int main() { size_t iterations = Direction::_size(); size_t index = 2; for (size_t count = 0; count < iterations; ++count) { std::cout << Direction::_values()[index] << " "; index = (index + 1) % Direction::_size(); } std::cout << std::endl; return 0; } 

Output:

 SE S SW NW N NE 

(The values ​​were int dimensional enumerations, but were converted to strings for output only to std::cout ).

Shows iteration over the whole set with an arbitrary starting point. You can do this forward or backward and schedule it for any listing.

I think using modulo, as in your question, is a good idea. This code just gives you some reflective information about the number of constants in the enumeration, and also puts them in an array.

The reason this may not be appropriate is because, since you are not using C ++ 11, the Direction::_values() array will be initialized when the program starts. I think that loop unfolding can still happen, but the compiler cannot do anything with the contents of the array. The array will still be allocated statically, but elements will not be available at compile time.

If you will be able to use C ++ 11, the array will be basically the same as the statically initialized int[6] (in fact, Direction[6] , where Direction is a struct literal)).

(In fact, I suppose I could expose an int array instead of Direction s, which would be statically initialized even in C ++ 98).

Answer 2

If you want to avoid creating a custom library, the approach I usually used looks something like this:

 enum Direction { SE, S, SW, NW, N, NE, DIRECTION_FIRST = SE, DIRECTION_LAST = NE, } 

Then you can use DIRECTION_FIRST and DIRECTION_LAST to iterate over the range correctly. There is still room for error if someone adds values ​​to the enumeration without updating the end points of the iteration, but centralizing it in the enumeration should make this less likely.

Now, if you take an arbitrary starting direction start , you can repeat it like this:

 Direction current = start; do { // Do stuff with current... current = (current + 1) % DIRECTION_LAST; } while(current != start); 

(The logic will be a little more complicated, although it is still possible if your enumeration does not start at 0. This is probably the only time you will need to use DIRECTION_FIRST .)