counting consecutive null characters

[aryan1]

Hi All,

Is there any function in C++ 's standard library or in STL which gives the number of consecutive characters in a stringstream object ?

std::count() and strspn() do not seem to be what I am looking for.

In my case, the sequence of consecutive characters may begin at any location in string stream as opposed to what is checked by strspn(), which returns the length of the "initial" portion of a string containing the consecutive characters.

Performance is my first priority while implementing this task.

Thanks.

[JohnW@Wessex]

What is the criteria for the count?

0, 1,2,3,0,04,5,0,0,0,6,7

What do you want the above to count as? 2? 5? 6?

[aryan1]

What is the criteria for the count?

0, 1,2,3,0,04,5,0,0,0,6,7

What do you want the above to count as? 2? 5? 6?

Sorry, I admit that my question was not clear.

If I have the following binary stream in hex representation:

00 01 02 03 00 00 04 05 00 00 00 06 07

what I want is to obtain the size of the "largest" sequence of consecutive NULL bytes, which is 3 in above example.

[aryan1]

What is the criteria for the count?

0, 1,2,3,0,04,5,0,0,0,6,7

What do you want the above to count as? 2? 5? 6?

What do you think about the function below ?

int checkConNullBytes()
{
    const char *BEGIN = dataStream.str().c_str();
    const char *END = dataStream.str().c_str() + dataStream.str().length();

    uint32_t totalNumberOfNullCharactersInStream = 0;

    map<uint32_t, int> myMap;

    for(char *i = const_cast<char*>(BEGIN); i != const_cast<char*>(END); i++)
    {
        totalNumberOfNullCharactersInStream = strspn(i, "\0");
        myMap[totalNumberOfNullCharactersInStream] = 0;//assume that there is no two keys in map which are the same
    }

    //return last entry in myMap since myMap 's entries will be sorted in ascending order based on key
}

This is probably not the most effective way of doing the job.

[JohnW@Wessex]

That looks a bit over complicated. How about...

#include <string>
#include <algorithm>

int checkConNullBytes(const std::string &dataStream)
{
    int maxCount = 0;
    int count = 0;

    std::string::const_iterator begin = dataStream.begin();
    std::string::const_iterator end = dataStream.end();

    while (begin != end)
    {
        if (*begin == 0)
        {
            ++count;
            maxCount = std::max(maxCount, count);
        }
        else
        {
            count = 0;
        }
    
        ++begin;
    }

    return maxCount;
}

int main()
{
    char data[] = {0, 1, 2, 3, 0, 0, 4 ,5 ,0, 0, 0, 6, 7};

    std::string dataStream(data, data + 13);

    int largest = checkConNullBytes(dataStream);
}

[superbonzo]

... and with C++0x

#include <algorithm>

int main()
{
    char data[] = {0, 1, 2, 3, 0, 0, 4 ,5 ,0, 0, 0, 6, 7};

    int largest = std::accumulate( data, data + 13, []( int count, char value ){ return value ? 0 : ++count; }, 0 );
}

[monarch_dodra]

... and with C++0x

#include <algorithm>

int main()
{
    char data[] = {0, 1, 2, 3, 0, 0, 4 ,5 ,0, 0, 0, 6, 7};

    int largest = std::accumulate( data, data + 13, []( int count, char value ){ return value ? 0 : ++count; }, 0 );
}

Well you don't actually need c++0x to do that. The lambda function is just sugar coating. Nicer than writing a one shot functor though, I'll grant you that.

The big flaw though is that your function doesn't actually count the longest consecutive null chars, but just counts the null chars. And if we wanted to do that, I'm sure std::count could do a better job.

Also, but I'm not completely sure, the above could be undefined, as accumulate expects the predicate to "return the result of an accumulation operation", and since in this case lambda(count, value) != lambda(value, count), depending on the implementation, the result could be outrageously different. On my system, I had to swap count and value for it to work correctly.

I doubt an algorithm could do this, as it would require the predicate to have a state (remember the longest chain, for example), and in Scott Meyer's words "Make predicates pure functions". Anything else is undefined with std::algorithm, I believe.

[JohnW@Wessex]

... and with C++0x

Are you sure?

Isn't that equivalent to this?

#include <string>
#include <numeric>

int Function(int count, char value)
{
    return value ? 0 : ++count;
}

int main()
{
    char data[] = {0, 1, 2, 3, 0, 0, 4 ,5 ,0, 0, 0, 6, 7};

    std::string dataStream(data, data + 13);

    int largest = std::accumulate(dataStream.begin(), dataStream.end(), int(0), Function);
}

If so, it doesn't work!

[JohnW@Wessex]

I doubt an algorithm could do this, as it would require the predicate to have a state (remember the longest chain, for example), and in Scott Meyer's words "Make predicates pure functions". Anything else is undefined with std::algorithm, I believe.

I find that to be such an annoying restriction, as often I find something that could be achieved in a couple of lines ends up turning in to a 'home-made' algorithm or loop just so I can be 'pure' and not pass a stateful predicate to an STL algorithm. And when I look at the code for the said STL algorithm, it's written in the same way as my home-made one anyway!

For example:
I often write image processing algorithms that require the last few pixels to be remembered. std::find_if with a stateful predicate would be perfect for this, but it's 'not allowed' (despite the supplied find_if being perfectly compatible). So I write my own Find_If, just in case the STL library writer decides to do something different, one day, maybe.

Is it a case of the STL designers keeping their options just a little too open and making life difficult for the end users?

[superbonzo]

as accumulate expects the predicate to "return the result of an accumulation operation", and since in this case lambda(count, value) != lambda(value, count), depending on the implementation, the result could be outrageously different. On my system, I had to swap count and value for it to work correctly.

uhm, the standard says "Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = acc + *i or acc = binary_op(acc, *i) for every iterator i in the range [first, last) in order."

so its behavior is prefectly defined. But ...

Isn't that equivalent to this?...If so, it doesn't work!

uhm... yes, that functor should have a state to store the maximal count:

int main()
{
	char data[] = {0, 1, 2, 3, 0, 0, 4 ,5 ,0, 0, 0, 6, 7};

	int largest = 0;
	
	std::accumulate( data, data + 13, int(0),
			[largest&]( int count, char value ) -> int { count = value ? 0 : ++count; largest = std::max(largest,count); return count; }
		);
}

[aryan1]

That looks a bit over complicated. How about...

#include <string>
#include <algorithm>

int checkConNullBytes(const std::string &dataStream)
{
    int maxCount = 0;
    int count = 0;

    std::string::const_iterator begin = dataStream.begin();
    std::string::const_iterator end = dataStream.end();

    while (begin != end)
    {
        if (*begin == 0)
        {
            ++count;
            maxCount = std::max(maxCount, count);
        }
        else
        {
            count = 0;
        }
    
        ++begin;
    }

    return maxCount;
}

int main()
{
    char data[] = {0, 1, 2, 3, 0, 0, 4 ,5 ,0, 0, 0, 6, 7};

    std::string dataStream(data, data + 13);

    int largest = checkConNullBytes(dataStream);
}

Thanks.

This is much better.

[monarch_dodra]

uhm, the standard says "Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = acc + *i or acc = binary_op(acc, *i) for every iterator i in the range [first, last) in order."

Yeah, apparently I was wrong. I missread my code

uhm... yes, that functor should have a state to store the maximal count:

int main()
{
    char data[] = {0, 1, 2, 3, 0, 0, 4 ,5 ,0, 0, 0, 6, 7};

    int largest = 0;
    
    std::accumulate( data, data + 13, int(0),
            [largest&]( int count, char value ) -> int { count = value ? 0 : ++count; largest = std::max(largest,count); return count; }
        );
}

I can't give examples about it, but I remember Scott Meyers being very explicit about not doing this. Saying that functors should be pure functions.

I don't know where and when this applies, so I'm playing it safe, but yeah, just a warning. I hope you know what you are doing.

[JohnW@Wessex]

I don't know where and when this applies, so I'm playing it safe, but yeah, just a warning. I hope you know what you are doing.

The problem I see is that quite a lot of C++ coders aren't sure either, and when told, can't see the logic of why on earth it was done that way at all.

[monarch_dodra]

The problem I see is that quite a lot of C++ coders aren't sure either, and when told, can't see the logic of why on earth it was done that way at all.

I remember it made sense when I read it, which is why I remember it. But for me, right now, it is "maybe it will work, maybe it won't". That's undefined as far as I'm concerned. I'll try to re-read it if I find the time.

[superbonzo]

I can't give examples about it, but I remember Scott Meyers being very explicit about not doing this. Saying that functors should be pure functions.

I don't know where and when this applies, so I'm playing it safe, but yeah, just a warning. I hope you know what you are doing.

I suppose Meyers said that because there are no guarantees on how ( many times ) the functor is copyed and/or constructed nor when its operator() is invoked. Indeed, the standard also add "binary_op shall not cause side effects" at the and of that paragraph.

The problem I see is that quite a lot of C++ coders aren't sure either, and when told, can't see the logic of why on earth it was done that way at all.

Agreed. BTW, when/how on earth lambda functors which have no state but induce sideeffects (like mine above) should be used with STL ?!?