Why does returning vector<string> throw std::bad_alloc exception?

Question

the program below runs perfectly for most of inputs, like 123210122.

But when I give input as 12221112222221112221111111112221111, it throws std::bad_alloc exception.

I cannot change the class structure or function signature as it is specified in the question. So have a look at this code:

#include<iostream>
#include<vector>
#include<string>
using namespace std;
class BinaryCode
{
    public:
        vector<string> decode(string q)
        {
            string p;
            int i;
            vector<string> response;
            bool flagnone=false;
            p[0]='0';
            p[1]=((q[0]-'0')-0-(p[0]-'0'))+'0';
            if(p[1]!='0' && p[1]!='1')
                response.push_back("NONE");
            else
            {
                for(i=2;i<q.length();++i)
                {
                    p[i]=((q[i-1]-'0')-(p[i-2]-'0')-(p[i-1]-'0'))+'0';
                    if(p[i]!='0' && p[i]!='1')
                    {
                        response.push_back("NONE");
                        flagnone=true;
                    }
                }
                if(!flagnone)   
                {
                    response.push_back(p.data());
                }
            }
            flagnone=false;
            p[0]='1';
            p[1]=((q[0]-'0')-0-(p[0]-'0'))+'0';
            if(p[1]!='0' && p[1]!='1')
                response.push_back("NONE");
            else
            {
                for(i=2;i<q.length();++i)
                {
                    p[i]=((q[i-1]-'0')-(p[i-2]-'0')-(p[i-1]-'0'))+'0';
                    if(p[i]!='0' && p[i]!='1')
                    {
                        response.push_back("NONE");
                        flagnone=true;
                    }
                }
                if(!flagnone)   
                {
                    response.push_back(p.data());
                }
            }
            return response;
        }
}b;
int main()
{
    string s;
    cin>>s;
    vector<string>ans = b.decode(s);
    cout<<ans[0]<<" "<<ans[1];
    return 0;
}

May me that's the time to startup the debugger, step through your program an get a grip what's actually going on! — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Jun 9, 2014 at 13:37
@Csq And why push_back( p.data() ) on a std::vector<std::string> when the type of p is std::string? — James Kanze
– James Kanze, Commented Jun 9, 2014 at 13:39
The operator[] does not provide bounds checking so I presume that you have overwritten the allocated space? — Dennis
– Dennis, Commented Jun 9, 2014 at 13:42

Csq · Accepted Answer · 2014-06-09 14:37:06Z

2

To summarize, the two errors your program have:

1. indexing into an empty string

You index into an empty string, p. That can overwrite anything, causing other functions to bad_alloc for example.

You first have to allocate some memory for the string - e.g. this will create a string same length as q:

string p(q.size(), ' ');

or use push_back to create your string, like you did with the vector.

2. using non null-terminated char* in string constructor

push_back( p.data() )

p is a string, data returns a const char*, but it is not null terminated before C++11. To return null-terminated data use c_str()

However, because p is a string and you want to append the whole you can simply say this now:

push_back( p )

This is a better solution even if you are using C++11.

edited Jun 9, 2014 at 14:37

answered Jun 9, 2014 at 13:47

Csq

5,8856 gold badges28 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

user2734982 Over a year ago

allocating initial memory to p does the job... But I did not get why does this not create problem for other inputs?

Csq Over a year ago

@JayPanchal What problems were you expecting?

user2734982 Over a year ago

Such SIGTRAP fault when p had not been given initial memory and still p got updated for input to function. Like when input(testcase) is 123210122.

Csq Over a year ago

Your errors were causes by overwriting memory that does not belong to you. That can have different kind of consequences (That's why it's called undefined behaviour). As the code is now allocating the memory it will use, it should behave correctly.

James Kanze Over a year ago

For the record, std::string::data() will return a pointer to a '\0' terminated string in C++11 (but not necessarily with earlier versions).

molbdnilo · Accepted Answer · 2014-06-09 13:51:07Z

0

I'm not sure if these are all the problems, but they are the ones that jump out.

string p;

This creates an empty string. It has zero (0) elements.

p[0]='0';

Here you assign to the first element of the empty string p.
This is undefined.
That means that your entire program is invalid and anything can happen.

p[1]=((q[0]-'0')-0-(p[0]-'0'))+'0';

If p hadn't been empty, making it undefined, this would be equivalent to

p[1] = q[0];

Figuring out why is left as an exercise.

And

response.push_back(p.data());

can be replaced with

response.push_back(p);

There is also no point at all in creating the class BinaryCode and an instance of it, as it has no state.
C++ lets you have free functions, unencumbered by the struggle of classes.

answered Jun 9, 2014 at 13:51

molbdnilo

67.1k3 gold badges46 silver badges90 bronze badges

1 Comment

Csq Over a year ago

There is also no point at all in creating the class BinaryCode - that is the requirement of TopCoder.

Collectives™ on Stack Overflow

Why does returning vector<string> throw std::bad_alloc exception?

2 Answers 2

1. indexing into an empty string

2. using non null-terminated char* in string constructor

5 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1. indexing into an empty string

2. using non null-terminated char* in string constructor

5 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related