Usage of deque<bool> in 6.16

#1

Problem 6.16 is the Sudoku checker problem. In the text it says ‘It’s convenient to use bit arrays to test for constraint violations’ then in code proceeds to use deque<bool>. As far as I know deque<bool> isn’t a bit array. vector<bool> and bitset are since they use a packed representation where a bit is used to represent a boolean value. So I think the code should either use vector<bool> or bitset. The shortcoming of vector<bool>, where &v[0] won’t work as expected when the template type is non-bool, isn’t applicable for this problem.

0 Likes
#2

Hi @sashang,

Thanks for your question, and this is a very deep question with keen observation. The bit array we referring here is like a high-level concept of bit array, where each element is used as 0 or 1. There is a nuance here in C++ as you pointed out, the reason we use deque is simply because it is the best practice, and the purpose of this deque is exactly like a bit array (using 0 or 1 in each element). We are not focusing on it must like a bit array in very low-level detail implementation.

0 Likes