Generating vertices of the rectified hypercube

The following piece of code generates the vertices of the rectified hypercube in arbitrary dimensions. The 3D case of the rectified hypercube is a cuboctahedron with 12 vertices (±1,±1,0), (±1,0,±1), (0,±1,±1).

The code below works perfectly, I only want to know what optimizations should I consider and/or if faster approaches exist.

#include 
#include 
#include 

template 
void generate_rectified_hypercube(std::vector> &vertices)
{
    std::array set;
    std::array temp;

    // Initialize set { 2, 1, ..., 1 }

    set[0] = T(2);
    for (size_t i = 1; i < N; i++)
    {
        set[i] = T(1);
    }

    // Generate vertices

    for (size_t i = 0; i < N; i++)
    {
        // Modify set

        set[i] -= T(2);
        std::copy(set.begin(), set.end(), temp.begin());
        std::sort(temp.begin(), temp.end());

        // Add all possible permutations of current set

        do
        {
            vertices.push_back(temp);
        }
        while (std::next_permutation(temp.begin(), temp.end()));
    }
}

Generally I'm quite fine with your original source, looks nice.

If you are pursuing absolutely top performance (what is the reason? This looks like a function, which should be used only few times trough life cycle of application) - you would have to dig into std::next_permutation first, to see if for your special case of various sets of {-1, 0, 1} values you can generate permutations "manually" in a faster way, then the general purpose permutation generator does. Maybe there is a way, but the source will become substantially longer and more complicated.

If you want to stay with std::next_permutation, there's little room for improvement, especially without losing some readability of the source.

For example with understanding how the set is modified by last next_permutation, you can cut out some initializations and sorting like this:

#include 
#include 
#include 

template 
std::vector> generate_rectified_hypercube()
{
    std::vector> vertices;  // result data
    std::array set; // set to permute upon
    // Initialize set to { 0, 1, ..., 1 }
    set[0] = T(0);
    for (size_t i = 1; i ();
}

As you can see, I removed the temp array (std::copy not needed) and I use the know state after last next_permutation to avoid std::sort. So this is certainly more efficient, but also harder to read and comprehend.

One note about your original code:

You don't clear the vertices input, which doesn't feel right to me. If the function is named generate_rectified_hypercube, it sounds quite functional to me, so calling it twice with the same vector I would expect it to contain only single copy of vertices (your code would add another set after the first one).

For your code probably some name along add_generated_rectified_hypercube would be more precise.

In my code I avoided this completely by creating new instance of vertices inside the function, and letting the C++11-post era compilers to optimize "return by value" situation.

And you can still do twice vertices.push_back(generate_rectified_hypercube()); to get two sets of vertices, to simulate behaviour of your original code (if desired). So the change in API is not limiting such usage, but it shouldn't happen by accident, reusing some non empty vertices.

Another edit:

Couldn't resist from showing off, how the function can be further cleaned up for better performance (unrolling the loop for i == 0 special case, getting rid of if (0 < i) in for loop).

The real world benefit is of course useless, as the loop is done only N-times (vs permuting N size array inside, which is much more complex).

So just for your fun ;). (BTW, OCD is evil thing, even partial ... hard to dismiss some things from head)

StackExchange Code Review Q#134142, answer score: 3