From: Howard Hinnant (hinnant_at_[hidden])
Date: 2002-06-12 14:57:36
On Wednesday, June 12, 2002, at 02:37 PM, Alex Rosenberg wrote:
> on 6/12/02 9:18 AM, Jeremy Siek at jsiek_at_[hidden] wrote:
>> It sounds like you would like to see a class that has both iterators
>> arithmetic operators. I am open to adding iterators (Howard Hinnant
>> made this suggestions), however I have reservations. As I posted
>> previously, I think iterators over bits are a bad idea because they are
>> inherently slow.
> The standard model of iterating over each bit may be slow, but an
> model that returned the index of the next set bit could be fast. (c.f.
> PowerPC's cntlzw instruction and x86's BSR.)
> Such a model might fit better with typical uses of the arithmetic
> on bitsets.
I think the slowness of iterating over bits may not be as bad as all
that. Compared to iterating over binary trees, bit iteration is
probably faster. Compared to deque::iterator, probably faster too
(actually there are strong parallels between deque and bitvector). A
bit iterator that contained a word pointer and a word mask seems like a
good design to me. Dereference is just *word & mask. Incrementing is
just a rotate on the mask (often a single machine instruction) combined
with an increment to the word pointer when the mask reaches an end
condition (e.g. 1). PowerPC's cntlzw can come in handy when computing
the difference between two such iterators.
However if dyn_bitset is not meant to be a migration path from
vector<bool> I think the argument is moot.
I'm guessing that C++0X will entertain the idea of deprecating
vector<bool>. I'm also guessing that said movement will be more likely
to be successful if there is also a proposed bitvector for vector<bool>
clients to migrate to. dyn_bitset does not have to be that class though.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk