Orchid Win7 v1 <voi### [at] devnull> wrote:
> (One helpful commenter pointed out that std::vector<bool> is allowed to 
> behave differently, though.)

std::vector<bool> is special in that each element takes one bit.
You can't have a pointer pointing to a single bit. (std::vector<bool>
iterators are also special.)

> I did enjoy the guy who claimed that because you're guaranteed O(1) 
> access time, it must be a continuous array. O RLY? Because I'm pretty 
> sure I can come up with an O(1) implementation that isn't contiguous...

std::deque has O(1) random access and O(1) insertion and deletion from
the beginning and the end, and it doesn't use contiguous memory for the
entire data structure. (Iterators also remain valid even if you add
elements.)

On the other hand, the O(1) random access is slightly slower than with
std::vector.

-- 
                                                          - Warp

Post a reply to this message