vector<int> 보다 vector<bool> 이 느리다?

문제를 풀다가 vector 로 요소 체크를 하면 통과하는데 vector 로 처리하니까 TLE가 발생했다.

이게 뭔 개소리야가 절로나와서 찾아보니 bool의 저장 방식 떄문이었다.

메모리 배치 및 엑세스 속도

• vector 의 경우
  내부적으로 int 타입의 배열과 비슷하게 배치된다.
• vector 의 경우
  메모리를 효율적으로 관리하기 위해 한 번에 여러개의 bool 값을 저장할 수 있는 bitfield로 구현된다. 즉, 하나의 정수에 여러 bool 값을 비트 단위로 저장하게 된다.
• 그래서 만약 저장된 bool 값을 조작하려면 해당 비트를 조작하기 위한 비트마스크 연산이 추가로 필요하게 되어 오버헤드가 발생하기 때문에 vector은 속도가 저하게된다.

결론은, bool 은 메모리 효율을 위해 시간 효율을 희생했다고 보면 된다. 이제부터 vector<bool>은 자제해야겠다 ;;