In a nutshell
#define _GLIBCXX_SANITIZE_VECTOR 1
Prerequisites
Many of you know about _GLIBCXX_DEBUG
/ _GLIBCXX_DEBUG_PEDANTIC
defines that force libstdc++ on GCC compilers to check out-of-bounds access to the array and react correspondingly. Linux (and some Mac OS users that use clang as a compiler) may also know about libasan library (that you can activate via providing -fsanitize=address
parameter to the build option. It checks not only for STL containers, but also every possible out-of-bounds memory access. While it may seem like it's going to work on std::vector
out-of-bounds access, that's not always the case. See the example below.
#include <vector>
int main() {
std::vector<int> arr = {1, 2, 3, 4};
int variable = arr[4];
}
This will trigger the libasan check, as the allocated capacity of the vector equals to the size of the vector. More on how std::vector
works you may read here.
In a nutshell: std::vector
allocated some capacity
that is >= than size
, and after each push_back
if capacity
becomes lower than size
it reallocates everything and doubles the capacity.
So what's the problem? Why doesn't it work in all of the cases?
You see, when size
< capacity
, the allocated memory length is actually the size of capacity
.
Imagine a situation: size
equals to 9, capacity
equals to 16. You access arr[9]
and that won't go out-of-bounds from the point of an OS. Libasan won't trigger. You can test this code to prove that:
#include <vector>
int main() {
std::vector<int> arr = {1, 2, 3, 4};
arr.reserve(10000);
int variable = arr[4];
}
What you have come for
If you pass #define _GLIBCXX_SANITIZE_VECTOR 1
before including any libraries, libasan
will trigger on container overflow in all of the cases. You can try the above example and see that it will work. So, the edited code will be:
#define _GLIBCXX_SANITIZE_VECTOR 1
#include <vector>
int main() {
std::vector<int> arr = {1, 2, 3, 4};
arr.reserve(10000);
int variable = arr[4];
}
Motivation
I haven't seen any mentions of this on codeforces yet, so may be that would be helpful to someone.
Auto comment: topic has been updated by aqeq (previous revision, new revision, compare).
OH MY FUCKING GOD THATS INCREDIBLE
How he solved the problem for a long time and finally found its solution
REALL!!!!!!!!!! LOVE IT!!
wow O.o
>.<