How do I perform a pairwise binary operation between the elements of two containers?

Question

Suppose I have two vectors std::vector<uint_32> a, b; that I know to be of the same size.

Is there a C++11 paradigm for doing a bitwise-AND between all members of a and b, and putting the result in std::vector<uint_32> c;?

Sacrifice

Answer 1

A lambda should do the trick:

#include <algorithm>
#include <iterator>

std::transform(a.begin(), a.end(),     // first
               b.begin(),              // second
               std::back_inserter(c),  // output
               [](uint32_t n, uint32_t m) { return n & m; } ); 

Even better, thanks to @Pavel and entirely C++98:

#include <functional>

std::transform(a.begin(), a.end(), b.begin(),
               std::back_inserter(c), std::bit_and<uint32_t>());

Borszcz

Damn, I totally forgot the double input version! – Rorie

+1 fantastic! This solution looks like it'll still yield a result as long as b is at least as long as a, correct? – Sacrifice

@kfmfe04: Correct. It will advance b.begin() a.end() - a.begin() steps. – Rorie

Yes. If the vectors aren't of the same size, put the shorter one first or it'll be UB. Or better yet resize both to the max of their sizes. ANDing with zero should be appropriate default behaviour. Also reserve the result before running this! – Borszcz

Need #include <iterator> too. ;-] – Hulett

This can be even more concise if you use std::bit_and<uint32_t> (from <functional>) rather than lambda, and it'll then work on C++03 just as well :) – Finitude

@PavelMinaev: Awesome, much better! This should really be your answer! – Borszcz

@PavelMinaev +1 v.nice! Glad to see both your answer and Kerrek's, tho - for your conciseness and for Kerrek's general case - both will be useful - starred. – Sacrifice

+1 For the second solution, lambdas aren't always neccessary. – Braunite

And you can replace uint32_t with decltype(*a.begin()) or decltype(a)::value_type or what have you for genericity. – Roadwork

...and in C++14 you can replace uint32_t with nothing at all, and you'll have full genericity for free! In C++14, std::bit_and<>{} computes the & of any two values, of any two types. – Drud

Answer 2

If you're going to be doing this a lot, on large arrays, check out the linear algebra libraries mentioned in https://stackoverflow.com/search?q=valarray. Many of them will take advantage of special instructions to get the answer faster.

Teuton

Unfortunately this is a quality-of-implementation issue, and most C++ implementations I've seen don't really try to optimize valarray. The only one I know that actually optimizes it to use CPU vector opcodes and such is Intel C++. – Finitude

@Jeffrey +1 interesting - is this meant to replace BLAS? – Sacrifice

@Sacrifice Other way around. valarray is the general idea, but it dates from 1998, and other linear algebra libraries like uBLAS (boost.org/libs/numeric/ublas/doc/index.htm) tend to be better. In the questions mentioned at the search I linked to, people suggest several other libraries. – Teuton

Answer 3

Just an idea, not C++11 specific: Maybe you could step through the arrays 8 bytes at a time using uint_64, even though the actual array is composed of 32-bit integers? Then you would not rely on e.g. SSE, but still get fast execution on many CPUs that have 64-bit wide registers.

Trina