2
\$\begingroup\$

I implemented a invert-range operation in a (logical) circular vector. A circular vector is a vector without a logical starting and ending object, or, equivalently, the successive element of the element at the last index of the vector is the element at index 0 (similarly for the previous element).

I'm not 100% sure it's correct. If it's correct, any suggestions to improve it (especially in terms of performance)?

#include <cmath>

...

vector<SomeObject> vec;

...

/*
 * Invert the segment starting at object at index i and ending at object at index j.
 * */
void invert(const int i, const int j) {

    // assert i and j are in the bounds

    if (vec.size() < 2 || i == j) {
        return;
    }

    int segment_size;

    if(j < i ){
        segment_size = std::ceil(((vec.size() - i) + j) / 2.0);
    } else {
        segment_size = std::ceil(std::abs(j - i) / 2.0);
    }

    for (int x = 0, k = i, w = j; x < segment_size; ++x) {
        std::swap(vec[k], vec[w]);
        k = next(k);
        w = previous(w);
    }

}

where next and previous are the following procedures:

/*
 * Returns the index to the object after the object at index i.
 * */
int next(const int i) {
    return (i + 1) % vec.size();
}

/*
 * Returns the index to the object before the object at index i.
 * */
int previous(const int i) {
    return (i - 1) % vec.size();
}

Note: these functions were actually methods, i.e. part of a class, and they actually working on a field and not on, e.g., global variable.

\$\endgroup\$
4
\$\begingroup\$

Bug

Your previous() function doesn't wrap around well:

int previous(const int i) {
    return (i - 1) % vec.size();
}

When i reaches 0, this function will return -1, not vec.size() - 1 as you might be expecting. You could either go with:

int previous(const int i) {
    return (i - 1 + vec.size()) % vec.size();
}

or perhaps:

int previous(const int i) {
    if (i == 0)
        return vec.size() - 1;
    return i - 1;
}

Unnecessary use of float

The Floating Point Police™ disapprove of your unnecessary use of floating point here:

if(j < i ){
    segment_size = std::ceil(((vec.size() - i) + j) / 2.0);
} else {
    segment_size = std::ceil(std::abs(j - i) / 2.0);
}

All you are doing is rounding up, so you could just do:

if(j < i ){
    segment_size = (vec.size() - i) + j;
} else {
    segment_size = j - i;
}
segment_size = (segment_size + 1) / 2;

Technically, there could be a problem with the above if your segment size can be INT_MAX. If this is possible, then replace that last line with this instead:

segment_size = (segment_size / 2) + (segment_size & 1);

But if your segment size could be INT_MAX, then your next() function would need to be fixed as well.

\$\endgroup\$
  • \$\begingroup\$ The segment size, in the problem I'm trying to solve, should not be that big, I think.. can you believe that the if statements that you provided without the ceils and so on are exactly my initial code, but then I changed it because I thought there was a bug in it... Indeed it doesn't make sense to call std:abs on j - i (since j >= i in that case)...when you're tired... \$\endgroup\$ – nbro Oct 22 '16 at 0:06

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.