为何访问超出vector<bool>容量的索引时，行为与vector<int>存在差异？

Great question! Let’s unpack this weird behavior—it comes down to two key things: vector<bool> being a quirky special case in the C++ standard library, and the chaos of undefined behavior (UB).

First: All out-of-bounds access is undefined behavior #

Let’s get this straight first: accessing any vector beyond its declared size is undefined behavior, no matter if it’s vector<bool> or vector<int>. That means the C++ standard doesn’t guarantee what will happen—your program could crash, print garbage, or (like here) accidentally do what you expect. The difference you’re seeing isn’t because vector<bool> is "safer"—it’s because its internal layout is totally different from regular vectors.

vector<bool> isn’t a "real" container #

Unlike vector<int> (where each element is a full 4-byte int stored in contiguous memory), vector<bool> is a bit-packed specialization. Instead of storing each bool as a separate byte, it crams multiple bools into a single byte (usually 8 bits per byte).

In your code, you created a vector<bool> with size 5 (since s.size() is 5). That means it only needs 1 byte total to store all 5 bits. Compare that to vector<int> of size 5, which would take 20 bytes (5 * 4 bytes).

Why your out-of-bounds writes didn’t crash #

When you tried to set deleted[22] = true (for 'w') and deleted[24] = true (for 'y'), here’s what happened under the hood for vector<bool>:

1. It calculated which byte to access: 22 / 8 = 2 (so the 3rd byte in the buffer, counting from 0)
2. It calculated which bit in that byte to flip: 22 % 8 = 6 (the 7th bit in the byte)

Since your program’s memory space includes that byte (it’s part of your process’s address space, not outside of it), writing to that bit didn’t trigger a segmentation fault. For vector<int>, accessing index 22 would jump 22 * 4 = 88 bytes past the start of the vector’s buffer—way outside the allocated memory, which almost always triggers a crash.

Why you got the "correct" output #

This is pure luck! When you loop through s and check deleted[s[i] - 'a']:

• For 'h' (index 7) and 'o' (index 14): you’re reading out-of-bounds bits, but those bits happened to be false (since you never modified them, and the memory was probably zero-initialized or unused)
• For 'w' (22) and 'y' (24): you’d set those bits to true, so the code skips them
• For 'd' (index 3): this is within the vector’s valid size, and it’s still false

All these coincidences lined up to give you the output you expected—but if you ran this on a different compiler, or with slightly different surrounding code, you could get garbage output or a crash.

The fix #

To avoid this UB entirely, just make your deleted vector the size of the entire lowercase alphabet (26 characters):

vector<bool> deleted(26, false);

This way, every lowercase letter maps to a valid index (0-25), no more out-of-bounds access.

内容的提问来源于stack exchange，提问作者Mohamed Magdy