Fastest way to find out if all elements in a vector are false or true c++?

Question

I was wondering if there was a quick way to find out if all elements in a vector are false or true? Like instead of checking each element using a loop?

Jun

Not really, other than picking another container, e.g. bitset, but look into any_of and all_of. – Extreme

No. That would penalize far more useful operations. The standard algorithms might be specialized for your case though. Or not. – Nato

If you can treat true\false as 1\0, try turning it into a k-th order statistic problem. Find just the first and last values in O(log.n) time. If they're same, you know they are all one value. – Restitution

Brushed up on my memory and you actually need an order statistic tree structure to get these in O(log.n). Without specialized structures it would be O(n). Worth a thought if you're really after the fastest possible way but perhaps overkill otherwise. – Restitution

Answer 1

I'd take advantage of the new algorithms for clarity:

// all true
std::all_of(vec.begin(), vec.end(), [](bool v) { return v; });

// all false
std::all_of(vec.begin(), vec.end(), [](bool v) { return !v; });
std::none_of(vec.begin(), vec.end(), [](bool v) { return v; });

You can't find out if all the elements in a vector are true without actually checking every element of the vector. Best-case, you reinterpret the memory differently and check more than 1 element at a time, but you still have to check everything until you find one that fails your test.

Elsa

so if all of my values in vec are true it returns true? – Jun

@Jun Which syntax? This only works with C++11 lambdas and algorithms. For non-C++11, I would check out either Cyber's answer or MSalters' – Elsa

Instead of [](bool v) { return v; }, you can also #include <functional> and do std::all_of(vec.begin(), vec.end(), std::identity); – Maclay

std::identity is available only in c++20. – Everrs

Answer 2

Easiest IMO is the free find function

if (std::find(begin(v), end(v), true) == end(v)) // All false

Ichthyornis

Answer 3

You can also use std::accumulate():

int sum = std::accumulate(std::begin(v), std::end(v), 0);

if (sum == v.size()) {
    // All true
}
else if (sum) {
    // Any true, any false
}
else {
    // All false
}

Sheff

This won't tell you if all elements are true. – Lashawn

@Lashawn Right. You can compare it with its size: if (accu..() == v.size()) – Sheff

Answer 4

A more efficient option for large vectors is to replace your vector<bool> with a vector<bitset>. Then you can simply combine the any_of() algorithm with a lambda function invoking the bitset member function any() (or similarly for all_of() and all()).

    int n = 2000000000, i = 623;
    vector<bitset<256>> bits((n + 255) / 256);
    bits[i >> 8][i & 0xFF] = true;
    cout << bits[i >> 8][i & 0xFF] << endl;
    if (any_of(bits.begin(), bits.end(),
            [](const bitset<256>& bs) { return bs.any(); })) {
        cout << "at least one bit set" << endl;
    }
    for (auto& bs : bits) {
        bs.set();
    }
    if (all_of(bits.begin(), bits.end(),
            [](const bitset<256>&bs) { return bs.all(); })) {
        cout << "all bits set" << endl;
    } 

In my timing tests with 2 billion elements (release build VS2022), either any_of() or all_of() above took 20ms (faster if any_of() breaks out early). Whereas with vector<bool> they required 2200ms. About 100x speedup. Setting all bits took 36ms, as compared to 1930ms for a vector<bool>, about 50x speedup.

The interface is slightly messy so you can wrap it in a template class if you want to to clean it up:

template <size_t bits_per_bitset, int lg_bits_per_bitset>
class dynamic_bitset {
public:
    dynamic_bitset(int n)
        : v((n + bits_per_bitset - 1)/ bits_per_bitset) { }
    
    constexpr bool operator[](int i) const {
        return v[i >> lg_bits_per_bitset][i & ((1 << lg_bits_per_bitset) - 1)];
    }
    auto operator[](int i) {
        return v[i >> lg_bits_per_bitset][i & ((1 << lg_bits_per_bitset) - 1)];
    }
    bool any() {
        return any_of(v.begin(), v.end(),
            [](const std::bitset<bits_per_bitset>& bs) { return bs.any(); });
    }
    bool all() {
        return all_of(v.begin(), v.end(),
            [](const std::bitset<bits_per_bitset>& bs) { return bs.all(); });
    }
    void set()   { for (auto& bs : v) bs.set(); }
    void reset() { for (auto& bs : v) bs.reset(); }
    void flip()  { for (auto& bs : v) bs.flip(); }
private:
    std::vector<std::bitset<bits_per_bitset>> v;
};

Now using it is as simple as this:

    int n = 2000000000, i = 623;
    dynamic_bitset<256, 8> bits(n);
    bits[i] = true;
    cout << bits[i] << endl;
    if (bits.any()) {
        cout << "at least one bit set" << endl;
    }
    bits.set();
    if (bits.all()) {
        cout << "all bits set" << endl;
    }

If I increase the template parameters, it gets a bit faster, but increases the wasted space if n is not divisible by bits_per_bitset. In my experiments there were no further returns beyond <1024,10>, which occupies a minimum of 32 words of 32 bits each.

You can add a bunch of other operations to dynamic_bitset easily including push_back(), bitwise operators, begin()/end(), etc.

Tog

Answer 5

This requires looping, but will at least take advantage of short-ciruiting behavior.

bool all = true;
std::vector<bool>::iterator it = myVec.begin();

while(all && it != myVec.end())  // Stops early if it hits a false
{
    all &= *it;
    ++it;
}

If all is true, all elements in the vector were true. If all is false, at least one element was not true.

Unexacting

Correction: "if all is false, at least one element was not true". (or at least one element was false) – Untoward

@Untoward Good catch :) "Do as I do, not as I say"... or something like that. – Unexacting

This won't tell you if all elements are false. – Lashawn

@Lashawn Correct, this would be the analog to Python's all function. The complement any would tell you if all elements are false, which would be similar to this code but with a few slight modifications. – Unexacting

Answer 6

I also agree that worst case one will have to check every individual element but for all other cases I suggest rephrasing the question:

Are all elements in my collection equal? If so, to what value.

This will return early in both cases and you are done. Else one additionally will have to check the value of the element (true or false).

For this I would suggest to look here.

I want to generalize my answer a bit more: This can be done with any N mutually exclusive predicates A1, ... , AN that I want to check for my collection. For this I will need a function that, given an element of my collection, returns some identifier of the predicate Ai that holds for the element (and a way to check the predicates for equality).

Then again I can apply the above scheme.

Festal

Answer 7

I think the most efficient would be:

if(v.find(v.begin(), v.end(), true) == v.end())
// All false  

if(v.find(v.begin(), v.end(), false) == v.end())
// All true

Namely