0
\$\begingroup\$

I implemented a function to shift an element after another in a logical circular array. Shifting in this case simply means moving element at position i to in front of element at position j. Of course I can't simply swap the elements at position i and next(j), because I would alter the positions of two elements in this circular array.

Here's the code I came up with:

std::vector<SomeType> circular_container;

/*
 * Move node at index i in front of node j
 * by shifting all nodes by 1 behind until j.
 * */
void shift(int i, const int j) {

    if (circular_container.size() < 2) {
        return;
    }

    int n = next(i);
    while(i != j) {
        std::swap(circular_container[i], circular_container[n]);
        i = n;
        n = next(i);
    }

}

And the next function looks like:

/*
 * Returns the index of the node after the node at index i.
 * */
int next(const int i) {
    return (i + 1) % circular_container.size();
}

Is the shift operation correct? If it is, any way to improve it?

\$\endgroup\$
  • 1
    \$\begingroup\$ The standard library already has std::rotate to do what you seem to be trying to accomplish. You just need to supply it with "circular iterators" (which should be fairly trivial to implement). \$\endgroup\$ – Jerry Coffin Oct 28 '16 at 16:18
2
\$\begingroup\$

Don't get me wrong. The function currently is almost useless, since you are rotating only circular_container. People would like to rotate any container on pair of iterators, as mentioned by @Jerry. But lets put those things aside, and have a look at your code.

Code Review

std::vector<SomeType> circular_container;

Global variable, very bad. Here's why. You could at least write template variable (don't do that!).

void shift(int i, const int j)

OK lets imagine for a minute that someone really filled the global variable and wants to rotate now. But then that someone gets upset, because apparently int is not large enough to hold the index he/she wants to rotate. Always use at least std::size_t defined in <cstddef>, or better use std::vector<SomeType>::size_type. This guarantees you that the type will be large enough to hold the biggest possible index.

if (circular_container.size() < 2) {
    return;
}

You are creating a branch that should be taken care of by the loop (it actually does, I believe). If the size of the container is 1, caller should provide equal i and j (you are not performing range check anyway). If the size of the container is zero, caller shouldn't even call your function at all! So the above if is redundant.

Conclusion:

It does the needed job. Sometimes. In a very clumsy way. I would arguably say that this is better than nothing, but there is a huge room for improvement.

Suggestions on better implementation:

As @Jerry noted, you should create iterator that performs the logic of your next() function. Probably you'll want to provide one version for forward, another for bidirectional, and the last one for random access iterators. The only thing you need to do is to move the logic from next() to the operator++(), for example.

I would also like to have a function that returns me circular iterator range taking pair of begin and end iterators, so that I could pass it into the function which does similar things to your shift function, and then specify by how much I want to shift, like the count of shifts to the right. You can also provide bool parameter that specifies the direction, if iterator supports it. Also, you could harness the power of random access iterators to make count shifts at once, rather than calling the shift in the loop.

\$\endgroup\$
  • \$\begingroup\$ Regarding the global variable. This is actually a method of a class. I just wrote it as it's in order to simplify the question. Regarding range checking, actually, in my really code I'm using assertions. This code actually was not designed to be used outside of the project I'm developing, so that's why I'm not making it very flexible for changes, but I appreciate your feedback. \$\endgroup\$ – nbro Oct 29 '16 at 0:05
  • \$\begingroup\$ @nbro, then you should post the real code, otherwise you'll keep getting answer like the one above. \$\endgroup\$ – Incomputable Oct 29 '16 at 0:06
  • \$\begingroup\$ It's ok, because I would like also to hear new ideas and suggestions, in general. Moreover, I could not have posted all the code. \$\endgroup\$ – nbro Oct 29 '16 at 0:35

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.