1

For example:

b = [T T F F T F], then the function return 3 .

I can do that by a for-loop program. But, is there function return " the number of true value in a boolean vector " to do that faster than for-loop program ?

Thanks.

sinoky
  • 71
  • 1
  • 2
  • 3
    There are several different ways, but none of them will be faster than `O(n)`, where `n` is the length of your input vector. So a `for` loop is pretty much the best you can hope for on the aspect of runtime performance. – goodvibration Jan 03 '18 at 08:57
  • 4
    Maybe not "faster" (there's no way around O(n)) but that's a perfect fit for [`std::count`](http://en.cppreference.com/w/cpp/algorithm/count). – Some programmer dude Jan 03 '18 at 08:57
  • std::count (or more generally std::count_if) is probably what you are looking for. – falopsy Jan 03 '18 at 11:45
  • You should not use `std::vector` for this - it is broken by design. Operation you are looking for is called "population count" or "Hamming weight". Check this: https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer –  Jan 03 '18 at 15:23
  • @StaceyGirl, which is exactly what `std::count` does for a `std::vector`. – Johan Dec 30 '20 at 10:06
  • @Johan In a horribly inefficient way, yes. –  Dec 30 '20 at 12:33
  • @StaceyGirl, nope, it's as efficient as could possibly be: `... for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) __r += _VSTD::__libcpp_popcount(*__first.__seg_); ...`. – Johan Dec 30 '20 at 15:54
  • @Johan My assembly for both GCC and Clang says otherwise. –  Dec 30 '20 at 16:11
  • @StaceyGirl, you need to tell the compiler that popcnt is availble: "-march=nehalem" or newer and the latest version of clang 12.0.0. Then it works. – Johan Dec 30 '20 at 16:47
  • @Johan I don't t know where you took that source code, but mine implementation of `std::count` doesn't do that. I suspect you took the code from `std::bitset::count` instead. –  Dec 30 '20 at 16:52
  • Nope, did not. It's from clang 12.0.0 on the mac, also with this clang it produces popcnt in the assembly. right click, goto def on `std::vector test(16000, false); const auto a = std::count(test.begin(), test.end(), true);` – Johan Dec 30 '20 at 17:01

2 Answers2

14

std::count(b.begin(), b.end(), true);

Might be a good idea. More detailed if you want to try:

Code

#include <vector>     // std::vector
#include <algorithm>  // std::count
#include <iostream>   // std::cout, std::endl

int main(){

    std::vector<bool> b = { true, true, false, true, false, true };

    auto count = std::count(b.begin(), b.end(), true);

    std::cout << "Count = " << count << std::endl;

    return 0;
}

Output

Count = 4

alseether
  • 1,889
  • 2
  • 24
  • 39
  • 3
    Technically, std::count will return `ptrdiff_t` (or, more precisely, std::vector::iterator::difference_type which in practise will be `ptrdiff_t`. That will be a signed type (which is crazy - std::count should return an unsigned value), but it may not be int. This can all be avoided with `auto count`. – Martin Bonner supports Monica Jan 03 '18 at 11:11
-1

The space saving implementation of std::vector<bool> is ... implementation defined, so there is no portable way of doing it.

But if you really really need to be fast here and don't mind rewriting your program each time a new patch/version of your compiler, cpu, OS comes out, there is a way for most implementation.

Most implementations will probably implement it as an array of some type of int, if you can get access to that array you can use your cpu's popcount/simd instructions to count it in potentially O(n/m) instead of O(n), where m is the max wordlength that can be popcounted on your cpu.

Evil minds will postulate that O(n/m) is O(n) but that speed up can be significant.

Edit: I forgot there is another possibility, namely std::bitset if you don't really need a vector of bool. std::bitset has a count, but again its implementation defined how count is done.

Surt
  • 15,501
  • 3
  • 23
  • 39
  • 1
    Given that `m` is a constant for a particular implementation, it's not merely a *postulate* that O(n/m) is O(n), it's a fact (implied by the definition of O(n)). Of course, constant factors can be (very) important. – Martin Bonner supports Monica Jan 03 '18 at 11:13
  • `std::count` uses the CPUs popcount internally for `vector` so you're not going to get that * m speedup by writing your own non-portable code. – Johan Dec 30 '20 at 10:03
  • That requires that your implementation has that specialization, which is not guaranteed. – Surt Dec 30 '20 at 17:26
  • @Johan I don't think std::count uses popcount, see https://stackoverflow.com/a/57310059/459714 – Seth Mar 23 '21 at 10:27
  • The c++20 implementation does, earlier versions do not. – Johan Mar 24 '21 at 14:27