Re: [Boost-users] container with large number of elements and a small number of invalide elements

Subject: Re: [Boost-users] container with large number of elements and a small number of invalide elements
From: Klaim - Joël Lamotte (mjklaim_at_[hidden])
Date: 2013-11-01 07:54:23

On Thu, Oct 31, 2013 at 6:14 PM, MM <finjulhich_at_[hidden]> wrote:

> On 31 October 2013 16:10, Klaim - Joël Lamotte <mjklaim_at_[hidden]> wrote:
>
>> What would "valid"/"invalid" means here?
>> If it's "exist" or "don't exist", then maybe using boost::optional<MyPod>
>> would be enough.
>>
>
> That's right. How about sizeof(  boost::optional<MyPod> ) vs sizeof( MyPOD
> ) ?
>

You can check it easily. On this site using Boost 1.49 I get 4 additional
bytes on clang and gcc:
http://rextester.com/FMH8278

I'm a bit surprised because I thought it would be 1 byte max.

Anyway you will need a way to mark values as either valid or invalid.
There are several solutions, like using a std::vector<bool> (it's a bit
vector) or boost::dynamic_bitset to have one bit
per positions telling if it's valid or not. A simpler solution would have
your POD providing the info.

> Also, what sort of iterator can iterate over just the valid values? or how
> to implement one?
>

Well if the container, say std::vector, already provide an iterator, you
just have to wrap it by forwarding work
but just continue iterating if you just iterated into an invalid. Or
better, a range. I never used boost helpers to build
ranges so I can't say more on that but you have several possibilities.

> The point here is that there's a small number of elements that are
> invalid, their indices in the container are random,
>

I understand that, but I don't really see a specific problem.