On 11/1/2013 7:24 PM, Travis Gockel wrote:

On Fri, Nov 1, 2013 at 1:18 PM, Jeff Flinn <Jeffrey.Flinn@gmail.com

<mailto:Jeffrey.Flinn@gmail.com>> wrote:

    On 11/1/2013 1:28 PM, MM wrote:

        On 1 November 2013 12:37, Jeff Flinn <Jeffrey.Flinn@gmail.com
        <mailto:Jeffrey.Flinn@gmail.com>

        <mailto:Jeffrey.Flinn@gmail.__com

        <mailto:Jeffrey.Flinn@gmail.com>>> wrote:
             On 10/31/2013 1:14 PM, MM wrote:
                 On 31 October 2013 16:10, Klaim - Joël Lamotte
                 <mjklaim@gmail.com <mailto:mjklaim@gmail.com>
        <mailto:mjklaim@gmail.com <mailto:mjklaim@gmail.com>>
                 <mailto:mjklaim@gmail.com <mailto:mjklaim@gmail.com>
        <mailto:mjklaim@gmail.com <mailto:mjklaim@gmail.com>>>> 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 ) ?
                 Also, what sort of iterator can iterate over just the valid
                 values? or
                 how to implement one?
                 The point here is that there's a small number of
        elements that are
                 invalid, their indices in the container are random,

             So why not keep the invalid items from getting into the
        container in
             the first place?

             Jeff

        because they are processed at a later stage, their indices in the
        container are relevant,


    I'd need a better description of just what defines and item to be
    valid/invalid. And just what this processed at a later stage means.

    If you've some functions:

       bool   valid(const MyPod& ) { return ...; }
       bool invalid(const MyPod& pod) { return !valid(pod); }

    , and a pre-existing container then you can get an adapted view

    using boost::range::adaptors::__filtered like:

    typedef std::vector<MyPod> MyPods;

    MyPods all(...);
    MyPods bad;

    boost::copy(all | filtered(invalid), std::back_inserter(bad));

    boost::foreach(all | filtered(valid), someFunction);

    It all depends on the context of where this is used. Another
    approach uses the boost icl (interval container library). One
    example is:

    http://www.boost.org/doc/libs/__1_55_0b1/libs/icl/doc/html/__boost_icl/projects.html#boost___icl.projects.large_bitset

    <http://www.boost.org/doc/libs/1_55_0b1/libs/icl/doc/html/boost_icl/projects.html#boost_icl.projects.large_bitset>

    I've used a similar approach to just store the "valid" bases in a
    dna sequences and keeping track of gaps with an interval container.
    The advantage is avoiding the filtering cost when the application is
    primarily interested in the valid items only.

I would recommend checking out Google sparsehash -- specifically,
sparse_hash_set<T>:
http://code.google.com/p/sparsehash/source/browse/trunk/src/sparsehash/sparse_hash_set

The biggest difference between that and something like an
std::vector<boost::optional<T>> is google::sparse_hash_set will re-order
values on you (the nature of hash tables). It also forces you to have a
"deleted key" which exists in the realm of possible T values. Based on
impression that I get from your original email, this fits with your idea
of an "invalid" T.

That said, it is a ridiculously low-overhead container (on the order of
~2 bits/entry vs 4 bytes/entry with a boost::optional).

That's 2x10^6 bits for the OP's case, where-as the ICL approach is 64bits per interval. In the OP's case that would be 64x100(max number of invalid items assuming all invalid separated by atleast 1 valid item) about 3 orders of magnitude less.

Jeff