AddressSanitizer: переполнение кучи-буфера по адресу

Question

Я пытаюсь написать функцию, чтобы определить допустимость входной строки.

Это задание из кода leetcode, 20-е задание. Так что это так.

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
*Open brackets must be closed by the same type of brackets.
*Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Мой код:

bool isValid(string s) {
        vector<char> str;
        map<char, char> mp;
        mp['{']='}';
        mp['(']=')';
        mp['[']=']';
        for(int i = 0; i < s.length(); i++){
            str.push_back(s[i]);
        }int c = 0;
        while(!str.empty()){
            c++;
            for(int i = 0; i < str.size(); i++){
                if(str[i+1]==mp[i]){
                    int x = i+1;
                    str.erase(str.begin()+x);
                    str.erase(str.begin()+i);
                    }
            }if(c>str.size()) break;
        }
        if(str.empty()) return true;
        else return false;
    }

Но каждый раз, когда я получаю эту ошибку:

=================================================================
==32==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000032 at pc 0x00000038767f bp 0x7ffffae90390 sp 0x7ffffae90388
READ of size 1 at 0x602000000032 thread T0
    #2 0x7fd5e106882f  (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
0x602000000032 is located 0 bytes to the right of 2-byte region [0x602000000030,0x602000000032)
allocated by thread T0 here:
    #4 0x7fd5e106882f  (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
Shadow bytes around the buggy address:
  0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c047fff8000: fa fa fd fa fa fa[02]fa fa fa fa fa fa fa fa fa
  0x0c047fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==32==ABORTING

Можете ли вы объяснить, что здесь не так, мое решение правильно или нет?

Answer 1

Сравнение с mp[i] не имеет никакого смысла.

Поскольку mp изначально не содержит 0,1,2,3, ... но три скобки, mp[i] будет нулевым, пока ваш индекс не окажется кодировкой одного из символов открывающей скобки (первый, скорее всего, 40, '(' в ASCII).

Что произойдет, если у вас не так много символов, если вы достигнете последнюю итерацию, когда i == size() - 1.
Тогда доступ к str[i+1] ведет к неопределенному поведению, и может произойти все что угодно.

Нет простого способа восстановить вашу программу, поскольку ваш подход изначально некорректен, поэтому я рекомендую вам удалить все это и начать все сначала. .
(Как минимум, вам нужен способ отслеживать все открывающие скобки, с которыми вы столкнулись до сих пор. Главный совет: прочитайте о std::stack)