1
\$\begingroup\$

I was trying to create a function to delete the node at index i from its current position and insert it after node at index j from a std::vector<Node> nodes. These container is logically a circular container of nodes, that is there's no actual first or last node, i.e. after nodes.back() comes nodes[0].

I really need this function not to have bugs and to be as performant as possible, so I'm asking here your help to a further check and for eventual suggestions to improve its performance.

So, this is the function:

/*
 * Delete the node at index i from its current position
 * and insert it after node at index j.
 * */
void SimpleSolution::shift(const int i, const int j) {

    assert_not_out_of_bounds({i, j});

    int x;

    if (j < i) { // ranges [i, end] and [start, j]

        for (x = i; x < nodes.size() - 1; ++x) {
            std::swap(nodes[x], nodes[x + 1]);
        }

        std::swap(nodes[0], nodes.back());

        for (x = 0; x < j; ++x) {
            std::swap(nodes[x], nodes[x + 1]);
        }

    } else { // range [i, j]

        if (i != j) {

            for (x = i; x < j; ++x) {
                std::swap(nodes[x], nodes[x + 1]);
            }

        } else { // i == j

            // i and j are the last elements
            if (i == (nodes.size() - 1)) {
                std::swap(nodes[0], nodes.back());
            } else { // equivalent to std::swap(nodes[i], nodes[i + 1])
                std::swap(nodes[i], nodes[j + 1]);
            }
        }

    }

}

I'm not looking for "idiomatic" C++, but for correctness and performance, but if idiomatic also means correctness and performance, then perfect.

Here's the assert_not_out_of_bounds method:

void SimpleSolution::assert_not_out_of_bounds(const std::initializer_list<int> indices) const {
    for (int i : indices) {
        if (i < 0 || i >= nodes.size()) {
            throw std::out_of_range("i is out of the range");
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$

This looks quite sane, is there a reason you do not work with iterators?

  1. your assert doesnt use the reference but a copy, so you should use const std::initializer_list<int> &indices

  2. In the equal case, i would make it actually explicit and do std::swap(nodes[i], nodes[i + 1]), which is the same pattern you used all over the code.

  3. It might be ok if your assert is used multiple times, but it is rather confusing, that you pass it i and j and i read only i in the code. Maybe use better names like index1 index2

  4. Any reason you declare x outside of the loops?

\$\endgroup\$
  • \$\begingroup\$ 1. I guess I wanted a const reference... 4. x I was not sure if all compilers would optimize the recreation of the loop variables... \$\endgroup\$ – nbro Oct 16 '16 at 19:45
  • \$\begingroup\$ @nbro The declaration and initialization only happens once, not every single iteration; you might have a case if x was created inside the for loop (but this is very likely to be optimized away). \$\endgroup\$ – user2296177 Oct 16 '16 at 20:15
  • \$\begingroup\$ @nbro "Recreation of the loop variables" isn't a problem you should be concerned with in 2016. Especially when these variables are PODs. Any sane compiler will optimize them away into oblivion. Furthermore, recent versions of GCC and Clang are very likely to inline your assert_not_out_of_bounds and even unroll its loop. \$\endgroup\$ – Nikita Kakuev Oct 17 '16 at 18:01

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.