Why std::bad_alloc error in this

general
1

Problem link : Problem - B - Codeforces

here is a simple chunk of code where i input a string containing ‘.’ & ‘’ characters
and replacing some '’ by ‘x’ characters.
when i try for the following test case
1 // (t no. of testcases)
7 3 // ( length of string and a integer k )

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
 
int solve1 (string S , int i, int j, int n ){
    int pos = -1 ;
    if ( j >= n)
        j = n - 1 ;


    if (i >= n )
        return pos ;
    
    else {
        while ( j >= i){
            if ( S[j] == 'x'){
           pos = j ;
           break ; 
            }
            j-- ;
        }

    return pos ;

    }
    
}

int solve2 (string S , int i, int j, int n ){
    int pos = -1 ;
    if ( j >= n)
        j = n - 1 ;
    if (i >= n )
        return pos ;

    else {
        while ( j >= i){
        if ( S[j] == '*'){
           pos = j ;
           break ; 
            }
            j-- ;
        }

    return pos ;
    }
    
}
 
int main()
{
    int t ;
    cin >>t ;
    for (int j =0; j<t; j++){
        int n , k;
        cin>>n>>k ;
        string s;
        
        cin>>s;

        int count = 0;
        int i = 0;
        int f_x = 0 ;
        while ( i< n ){
            if ( s[i] == '*'){
                s[i] = 'x' ;
                f_x = i ;
                count ++ ;
                break ;
            }
            i++ ;
        }
        
        i = n - 1;
        while ( i >=0 ){
            if ( s[i] == '*'){
                s[i] = 'x' ;
                
                count ++ ;
                break ;
            }
            i-- ;
        }
        while ( f_x < n ){
            if (solve1(s, f_x + 1, f_x + k, n) == -1 ){
                int start = f_x + 1;
                f_x = solve2(s, start, f_x + k, n) ;
                s[f_x] = 'x' ;
                count ++ ;
            }

            else {
                int start = f_x + 1;
                
                f_x = solve1 (s, start, f_x + k, n) ;
            }
        }
        
        cout<<count<<endl;
    }
    return 0;
}

when i run this piece of code using the test case provided above, it gives me std::bad_alloc error

2

Please post the actual test input you are using (rather than a description of it), between pairs of triple backticks so that the forum software doesn’t mangle it.

Edit:

I’m going to assume the test input is:

1
7 3
.**.***

since that reproduces the issue. Have you tried debugging it?

[simon@simon-laptop][06:31:14]
[~/devel/hackerrank/otherpeoples]>cat testcase.txt 
1
7 3
.**.***
[simon@simon-laptop][06:31:15]
[~/devel/hackerrank/otherpeoples]>g++ -std=c++14 rudyiscrazy1-blah.cpp -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG -fsanitize=undefined -ftrapv
[simon@simon-laptop][06:31:18]
[~/devel/hackerrank/otherpeoples]>gdb ./a.out 
GNU gdb (Ubuntu 8.1.1-0ubuntu1) 8.1.1
Copyright (C) 2018 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ./a.out...done.
(gdb) r < testcase.txt 
Starting program: /home/simon/devel/hackerrank/otherpeoples/a.out < testcase.txt
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
/usr/include/c++/7/bits/basic_string.h:1057: std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::reference std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator[](std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>; std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::reference = char&; std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type = long unsigned int]: Assertion '__pos <= size()' failed.

Program received signal SIGABRT, Aborted.
__GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:51
51      ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.
(gdb) bt
#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:51
#1  0x00007ffff6760921 in __GI_abort () at abort.c:79
#2  0x0000555555557ff9 in std::__replacement_assert (__file=0x555555559708 "/usr/include/c++/7/bits/basic_string.h", __line=1057, 
    __function=0x5555555598c0 <std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::operator[](unsigned long)::__PRETTY_FUNCTION__> "std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::reference std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator[](std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type) [with _Ch"..., 
    __condition=0x55555555972f "__pos <= size()") at /usr/include/x86_64-linux-gnu/c++/7/bits/c++config.h:472
#3  0x0000555555558250 in std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::operator[] (this=0x7fffffffdb40, __pos=18446744073709551615)
    at /usr/include/c++/7/bits/basic_string.h:1057
#4  0x0000555555557c3c in main () at rudyiscrazy1-blah.cpp:89
(gdb) 

s[f_x] = 'x' ;

f_x is -1 with the testcase above when you execute this statement → undefined behaviour.

3

yes this is the test input i have been trying.
I m not good at debugging, still i tried it on VS Code but couldn’t find anything there !!

4

okay so at some point i m trying to access s[-1] which is invalid, am i right ?

5

in these lines where did you get to know that f_x is being passed as -1 ???

6

Yes :slight_smile:

#4  0x0000555555557c3c in main () at rudyiscrazy1-blah.cpp:89

Line 89 is s[f_x] = 'x';

#3  0x0000555555558250 in std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::operator[] (this=0x7fffffffdb40, __pos=18446744073709551615)
    at /usr/include/c++/7/bits/basic_string.h:1057

We’re calling std::string::operator[] with a pos of 18446744073709551615, which is -1 expressed as a uint64_t.

1 Like
7

so this is linux OS, an you share me any website/ you tube-video link to setup my desktop for this kind of debugging ???

8

Not really: if you already have Linux installed, installing gcc and gdb is usually done very easily via your package manager.