# Transforming a stl vector according to its neighbors

I have a piece of C++ code that transforms a vector where an element only stays one if itself and both of it's neighbors are one as well. End-points are handled as if the missing element is one. For example:

old: 1 1 0 1 1 1 0 1 1 0
new: 1 0 0 0 1 0 0 0 0 0


The following block of code works, but I'm not sure if it is optimal. We can assume that block and state are of type std::vector<int>, both of size N, and only contain elements 0 or 1:

  // Handle the end-points
block[0]   = state[0]*state[1];
block[N-1] = state[N-2]*state[N-1];

// Set the cooperative behavior
for(int i=1;i<N-1;i++)
block[i] = state[i-1]*state[i]*state[i+1];


Is there a better way to do this? Should I be using some kind of trickery with std::accumulate and the like? Profiling show that this piece of code is in the inner-block of my simulation and takes up a sizable fraction of my runtime.

• Since you're just using 0s and 1s, you could consider std::vector<bool>. On the other hand, the answers here suggest otherwise. – Jamal Oct 30 '13 at 21:01
• @Jamal space is not an issue, speed is. Some implementations of std::vector<bool> are problematic since it is specifically specialized. In general, I've found that I can avoid many of those headaches by using int's instead. – Hooked Oct 30 '13 at 21:03
• @Jamal: std::vector<bool> is not recommended. It is only kept for compatability. It has sever performance issues and does not have the same usage characteristics as other containers. It is considered a bit of a mistake. Prefer std::bitset<> if you want bits. But std::vector<char> is a good compromise of speed and size. – Martin York Oct 30 '13 at 23:21
• @LokiAstari: Yeah, I was hesitant about the vector, but I also wasn't sure about bitset (although not for the same reason). – Jamal Oct 30 '13 at 23:23

If speed really is an issue, I would try this rewrite of your loop:

const int *prev = &state[0];
int *pblock = &block[1];
for (int i = 0; i < N-1; ++i, ++prev, ++pblock) { // hopefully i is a compile-time constant?
*pblock = prev[0] * prev[1] * prev[2];
}


If N is sufficiently large, this could reduce how much you have to jump around in memory, since you're only ever looking ahead 2, instead of potentially N - 1.

• This doesn't actually speed things up, but you've given me an idea that does. I've posted it as an answer, but I'm accepting this one as both answers were useful! – Hooked Oct 31 '13 at 14:57

What you have is probably good enough. If you want to try something crazy, you could always do:

boost::range::transform(boost::irange(0, N), block.begin(), [&](const int i){
int pre = i-1 >= 0 ? state[i-1] : 1;
int post = i+1 < N ? state[i+1] : 1;
return pre * state[i] * post;
});


Not sure I prefer that to the simple loop that you have, but just throwing it out as a potential alternative.

• Thanks, I appreciate the alternative. Wouldn't this be necessarily slower since pre,post have to be check N times rather than once? – Hooked Oct 30 '13 at 21:19

Like the way you're moving the iterators in sync. -Please check but playing around with N=2000000 and a share of 1s over 0s in the state vector between 1/8 and 1/2 gives me a comparative speed advantage of 20 to 10 times respectively, by structuring the loop:

    // ... your loop result; cstate is a copy of the random_shuffle-d state vector
block.clear();
block.assign(N, 0);

block[0]   = cstate[0]*cstate[1];
block[N-1] = cstate[N-2]*cstate[N-1];
block[N-2] = cstate[N-3]*cstate[N-2]*cstate[N-1];
block[N-3] = cstate[N-4]*cstate[N-3]*cstate[N-2];

b_itr = block.begin()+1;
itr0  = cstate.begin();
itr1  = itr0+1;
itr2  = itr1+1;
//end   = cstate.end();

unsigned c(0); // counter in lieu of cstate.end() which may or may not be hit

while(c < N-4) {
if(0 == (*itr2)) {
itr0 += 3; itr1 += 3; itr2 += 3; b_itr += 3; c +=3;
}
else if(0 == (*itr1)) {
itr0 += 2; itr1 += 2; itr2 += 2; b_itr += 2; c +=2;
}
else if(0 == (*itr0)) {
itr0++; itr1++; itr2++; b_itr++; c++;
}
else {
(*b_itr) = 1;
itr0++; itr1++; itr2++; b_itr++; c++;
}
}


The idea is that if the leading value in state is 0, moving the pointers by 1 will result in a 0 in block next, likewise in the following step. (Replacing constantly assigning 0 or 1 with a default 0 block vector and a conditional if == 1 assignment did not make in itself a noticeable difference.)

For completeness, I'm using the solution posted below which is inspired from one of @Barry's answers. The idea is to replace [] with a pointer to dereference. This gives about 10% speedup.

  // Handle the end-points of the chain
block[0]   = state[0]*state[1];
block[N-1] = state[N-2]*state[N-1];

auto b_itr = block.begin()+1;
auto itr0  = state.begin();
auto itr1  = itr0+1;
auto itr2  = itr1+1;
auto end   = state.end();

while(itr2 != end) {
(*b_itr) = (*itr0)*(*itr1)*(*itr2);
itr0++; itr1++; itr2++; b_itr++;
}