0

Consider the following code

string s;
cin >> s;
vector<bool> deleted(int(s.size()));
int t;
cin >> t;
while (t--) {
    char x;
    cin >> x;
    deleted[x - 'a'] = true;
}
for (int i = 0; i < s.size(); i++) {
    if (deleted[s[i] - 'a']) continue;
    cout << s[i];
}
cout << "\n";

The above code takes a string consisting of lowercase English letters and t lowercase English letters to remove from s.

Input like the following should cause accessing out of bounds, but it seems like it's valid, since it prints the correct result "hod"

howdy
2
w
y

w and y will access indices 22 and 24 which is obviously greater than vector size.

Mohamed Magdy
  • 345
  • 3
  • 15
  • 9
    "should cause accessing out of bounds" what did you expect to happen? Undefined behavior is undefined – 463035818_is_not_an_ai Jun 29 '22 at 14:09
  • 2
    The `[]` indexing operator have no bounds-checking. If you want bounds checking then you should use the `at` function (which incur a performance penalty because of the bounds checking). – Some programmer dude Jun 29 '22 at 14:10
  • note that there is a flaw in your logic. suppose you are asked to calculate 3+3, you take a die and roll a 6, is this sufficient to conclude that rolling dice is a good way to add numbers? – 463035818_is_not_an_ai Jun 29 '22 at 14:12
  • @463035818_is_not_a_number I changed the type to int, it behaves differently it prints incorrect results, seems like something special about the vector of bool. – Mohamed Magdy Jun 29 '22 at 14:13
  • Wow, that behavior sounds really undefined. – paddy Jun 29 '22 at 14:14
  • 5
    it is out of bounds in both cases. C++ is not a nanny language. It does not even attempt to produce compiler errors or expressive runtime error for all things that can you can do wrong. Use `at` if you want bounds checking – 463035818_is_not_an_ai Jun 29 '22 at 14:15
  • 1
    @MohamedMagdy *Input like the following should cause accessing out of bounds* -- That's what happened -- so what is the issue? – PaulMcKenzie Jun 29 '22 at 14:16
  • Note that `x - 'a'` will fail for anything not a lower-case letter, or if the encoding is different from ASCII (that pattern is only portable and standardized for digits). – Some programmer dude Jun 29 '22 at 14:16
  • 1
    @MohamedMagdy Indeed `std::vector` is special (but not in a good way, imo). An out-of-bounds-access will still cause undefined behaviour, regardless of the type of vector. Undefined behaviour means, anything can happen. – Lukas-T Jun 29 '22 at 14:16
  • These duplicates doesn't answer my question. – Mohamed Magdy Jun 29 '22 at 14:28
  • There's no need to save information about the characters to delete. After `std::can >> x;` just remove all occurrences of `x` from the string. – Pete Becker Jun 29 '22 at 14:28
  • 5
    @MohamedMagdy *but it seems like it's valid, since it prints the correct result "hod"* -- You buy 10 ropes that are rated to hold only 500 pounds. You then tie 600 pounds to each of those ropes -- 6 break immediately, 4 don't break. You get 10 more ropes, you run the same test -- now 9 ropes break and 1 doesn't break. That's what you're doing here -- you broke the rules of accessing an out-of-bounds item -- there is no guarantee what will happen when you do that. – PaulMcKenzie Jun 29 '22 at 14:28
  • Re: "letters to remove from `s`" -- but the code doesn't remove anything from `s`. It displays characters from `s` that are not in the deleted list, but it leaves `s` unchanged. – Pete Becker Jun 29 '22 at 14:29
  • @PeteBecker But that's O(n) where `n` is the size of the string. I'm asked to print the nonremoved characters. – Mohamed Magdy Jun 29 '22 at 14:33
  • The loop `for (int i = 0; i < s.size(); i++)` already makes the algorithm O(n). That you don't print all the characters in the string is irrelevant for the complexity. – Some programmer dude Jun 29 '22 at 14:34
  • 2
    @MohamedMagdy *These duplicates doesn't answer my question.* -- I'll be honest with you -- if you want to spend time chasing down why undefined behavior does this or that, then you will be mostly on your own. Change compilers, compiler options, etc. and you may get a different behavior -- so are you willing to spend time on figuring out why a certain optimization setting changes undefined behavior? You will quickly realize it will be like a dog chasing its own tail, and not worth the effort. – PaulMcKenzie Jun 29 '22 at 14:35
  • @Someprogrammerdude -- on the other hand, removing m characters one at a time (as I recommended) from a string that holds n characters is going to be O(m*n). I was really making a somewhat pedantic point about clearly stating the problem to be solved. – Pete Becker Jun 29 '22 at 14:38
  • @PaulMcKenzie I know all that, accessing out of bounds gives undefined behavior, but, It seems like the vector of bool capacity is greater than the vector of int capacity. – Mohamed Magdy Jun 29 '22 at 14:44
  • You understand that both are undefined behavior so it’s not useful to try and reason about what “seems” to be happening. – Blastfurnace Jun 29 '22 at 14:52
  • If you really want to get to the bottom of this, just look at the source code for both and see how they're implemented. Beyond that, you're not gonna get a good answer – CoffeeTableEspresso Jun 29 '22 at 15:15
  • *"seems like something special about the vector of bool"* Yes, `vector` is special in that it stores the values as single bits. That way it is likely to have a storage of 32 or 64 bits minimum. This might affect how the undefined behaviour manifests itself. – BoP Jun 29 '22 at 15:25
  • **Undefined behavior**, if you are unlucky, means that the program may appear to work correctly. Or may crash, if you are lucky. Or may give the expected results today, but give unexpected results tomorrow at the big presentation with your boss. Or may email your browser history to your grandmother. There's really no reasoning about undefined behavior because any behavior is allowed. – Eljay Jun 29 '22 at 17:01

0 Answers0