vector<bool>, bit_vector, or something else?

Discussion in 'C++' started by Scott Brady Drummonds, Jul 3, 2003.

  1. Hi, everyone,

    I have a program in which I need to store a series of Boolean values. A
    vector<bool> would be ideal. However, I'm concerned about this data
    structure because of Scott Meyers' Effective STL's Item 18: Avoid using
    vector<bool>.

    Plus, I'm loath to use bit_vector since SGI's STL implementation says it
    will soon be dropped on the floor
    (http://www.sgi.com/tech/stl/bit_vector.html).

    Additionally, the bitset won't work because I don't know the number of
    values I'll need at compile time. Lastly, Meyers' recommendation of using a
    dequeue<bool> scares me a little because it appears that it won't pack the
    sequence of bools into bits the way that a bitset does (and, frankly, the
    way I'd like my data structure to do since there may be a lot of flags in
    this container.)

    What is the best way to compactly store a sequence of on/off flags and allow
    for indexed addressing?

    Thanks,
    Scott



    --
    Remove ".nospam" from the user ID in my e-mail to reply via e-mail.
    Scott Brady Drummonds, Jul 3, 2003
    #1
    1. Advertising

  2. In article <be2ccu$vs6$>, Scott Brady Drummonds
    <> wrote:

    | Hi, everyone,
    |
    | I have a program in which I need to store a series of Boolean values. A
    | vector<bool> would be ideal. However, I'm concerned about this data
    | structure because of Scott Meyers' Effective STL's Item 18: Avoid using
    | vector<bool>.
    |
    | Plus, I'm loath to use bit_vector since SGI's STL implementation says it
    | will soon be dropped on the floor
    | (http://www.sgi.com/tech/stl/bit_vector.html).
    |
    | Additionally, the bitset won't work because I don't know the number of
    | values I'll need at compile time. Lastly, Meyers' recommendation of using a
    | dequeue<bool> scares me a little because it appears that it won't pack the
    | sequence of bools into bits the way that a bitset does (and, frankly, the
    | way I'd like my data structure to do since there may be a lot of flags in
    | this container.)
    |
    | What is the best way to compactly store a sequence of on/off flags and allow
    | for indexed addressing?

    With all due respect to Mr. Meyers, std::vector<bool>.

    Did the committee screw up when they created vector<bool> as opposed to
    bitvector? Yes. But the functionality afforded by vector<bool> is
    useful nonetheless. It just has a bad name, that's all.

    A future standard might deprecate vector<bool>, but at the same time
    introduce bitvector. There's no way (imho) that we will deprecate
    vector<bool> without reintroducing that same functionality under a
    different name. People need it.

    You might protect yourself a bit with:

    typedef std::vector<bool> MyVectorBool;

    And then use MyVectorBool religiously. Then should you be on a
    platform that offers bitvector, or should the standard change out from
    under you, your maintenance can be easily accomplished during or after
    a three martini lunch with a single change.

    Don't be afraid of vector<bool> for the functionality it offers. It is
    good stuff. Be wary of vector<bool> because it differs in subtle ways
    from vector<int>. And I think that is probably the point to take away
    from Scott's ESTL #18.

    --
    Howard Hinnant
    Metrowerks
    Howard Hinnant, Jul 4, 2003
    #2
    1. Advertising

  3. Scott Brady Drummonds

    Jerry Coffin Guest

    In article <be2ccu$vs6$>,
    says...
    > Hi, everyone,
    >
    > I have a program in which I need to store a series of Boolean values. A
    > vector<bool> would be ideal. However, I'm concerned about this data
    > structure because of Scott Meyers' Effective STL's Item 18: Avoid using
    > vector<bool>.


    The problems with vector<bool> almost all stem from the fact that it's
    required to be specialized to pack the bools.

    > Additionally, the bitset won't work because I don't know the number of
    > values I'll need at compile time. Lastly, Meyers' recommendation of using a
    > dequeue<bool> scares me a little because it appears that it won't pack the
    > sequence of bools into bits the way that a bitset does (and, frankly, the
    > way I'd like my data structure to do since there may be a lot of flags in
    > this container.)
    >
    > What is the best way to compactly store a sequence of on/off flags and allow
    > for indexed addressing?


    ....and another container that packs the bits won't likely be any better
    than vector<bool> anyway.

    It comes down to a simple choice: you can leave the bools unpacked, and
    get normal semantics for the container. You can pack the bools, and get
    compact storage. At least the way C++ is defined right now, I don't
    know of a way to pack the bools one per bit, and still get normal
    semantics for the container, so if packed bools is what you want, then
    vector<bool> is at least as good as most of the alternatives.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
    Jerry Coffin, Jul 4, 2003
    #3
  4. Scott Brady Drummonds

    Evan Guest

    Pete Becker <> wrote in message news:<>...
    > Scott Brady Drummonds wrote:
    > >
    > > I have a program in which I need to store a series of Boolean values. A
    > > vector<bool> would be ideal. However, I'm concerned about this data
    > > structure because of Scott Meyers' Effective STL's Item 18: Avoid using
    > > vector<bool>.

    >
    > If vector<bool> does what you need, use it.
    >
    > > What is the best way to compactly store a sequence of on/off flags and allow
    > > for indexed addressing?
    > >

    >
    > vector<bool>.


    I agree. As long as you're aware of the differences with the <bool>
    specialization, you should be fine.
    Evan, Jul 4, 2003
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Dimitar Georgiev

    bit_vector and list_wl in VC++ 7.0

    Dimitar Georgiev, Sep 11, 2003, in forum: C++
    Replies:
    1
    Views:
    392
    Kevin Goodsell
    Sep 11, 2003
  2. Guest
    Replies:
    4
    Views:
    475
    Guest
    Oct 13, 2004
  3. Alex Vinokur

    vector<int> and vector<bool>

    Alex Vinokur, Jan 15, 2005, in forum: C++
    Replies:
    1
    Views:
    330
    Sharad Kala
    Jan 15, 2005
  4. Replies:
    8
    Views:
    1,913
    Csaba
    Feb 18, 2006
  5. Replies:
    4
    Views:
    212
    Tad McClellan
    Jun 1, 2007
Loading...

Share This Page