Default constructed random access iteratators

Discussion in 'C++' started by Kristoffer Vinther, May 17, 2005.

  1. Hi,

    I need to store of parts of containers. The interface to the store could
    look something like this (the code in this post serves as illustrations,
    it is not meant to be 100% correct):

    template<class RanIt>
    class substreams
    {
    public:
    void add(RanIt begin, RanIt end);
    };

    and used like this:

    std::vector<int> vector(20);
    substreams<std::vector<int>::iterator> streams;
    //...
    streams.add(vector.begin(), vector.begin()+5);
    streams.add(vector.begin()+5, vector.begin()+10);
    streams.add(vector.begin()+15, vector.end());

    where I'm adding parts of a vector to the store (streams).

    Now, I know add() will be called at most k times, so I would like to
    implement it like this:

    template<class RanIt>
    class substreams
    {
    std::pair<RanIt,RanIt>* parts_begin;
    std::pair<RanIt,RanIt>* parts_end;
    std::pair<RanIt,RanIt>* parts_last;
    public:
    substreams(size_t k)
    : parts_begin(new std::pair<RanIt,RanIt>[k]),
    parts_end(parts_begin),
    parts_last(parts_begin+k) { }
    virtual ~substreams()
    {
    delete[] parts_begin;
    }

    void add(RanIt begin, RanIt end)
    {
    *parts_end++ = std::make_pair(begin, end);
    }
    };

    Suppose I want to count the total number of elements in the container
    parts added. I could do something like this:

    size_t size() const
    {
    size_t total = 0;
    for( std::pair<RanIt,RanIt>* it=parts_begin;
    it!=parts_last; ++it )
    total += (it->second-it->first);
    return total;
    }

    (strictly, I guess I should use typename
    std::iterator_traits<RanIt>::difference_type instead of size_t). Now you
    are thinking why not stop at it==parts_end? Let me just say the real
    problem is not computing the size(), but something less trivial than a
    for(...), so I would like to avoid involving parts_last. And that's the
    problem:

    Will the size() function as implemented above (using parts_last) always
    work, even if add() has not been called k times (for the vector example,
    size() should return 15 for all k>3)?
    IIRC, the standard specifically takes care of the case where RanIt is a
    pointer by requiring a default constructed pointer to be NULL, thereby
    guaranteeing new std::pair<RanIt,RanIt>[k] evaluates to an array of
    pairs of NULL pointers, in turn guaranteeing (it->second-it->first) is
    zero for the pairs between parts_end and parts_last (those not added).
    Correct me if I'm wrong.

    But what if RanIt is not a pointer? As far as I can see the standard
    only requires random access iterators to be default constructable but
    states nothing about the semantics of such an iterator, specifically
    nowhere that

    template<class RanIt>
    size_t diff()
    {
    RanIt b();
    RanIt e();
    return e-b;
    }

    should always return 0, or equivalently

    template<class RanIt>
    bool empty()
    {
    RanIt b();
    RanIt e();
    return e == b;
    }

    always returning true. Have I just missed something, or should I rethink
    my implementation?

    Thanks for your input,
    Kristoffer Vinther
     
    Kristoffer Vinther, May 17, 2005
    #1
    1. Advertising

  2. Kristoffer Vinther

    Ron Natalie Guest

    Kristoffer Vinther wrote:

    > But what if RanIt is not a pointer? As far as I can see the standard
    > only requires random access iterators to be default constructable but
    > states nothing about the semantics of such an iterator, specifically
    > nowhere that
    >
    > template<class RanIt>
    > size_t diff()
    > {
    > RanIt b();
    > RanIt e();
    > return e-b;
    > }
    >
    > should always return 0, or equivalently
    >
    > template<class RanIt>
    > bool empty()
    > {
    > RanIt b();
    > RanIt e();
    > return e == b;
    > }
    >
    > always returning true. Have I just missed something, or should I rethink
    > my implementation?
    >

    You haven't missed anything. While the standard requires default
    construction of an iterator to be legal, the use of that default
    constructed value is undefined behavior. It neither compares to
    0 or NULL nor deterministicly to any other object (including other
    default constructed iterators).
     
    Ron Natalie, May 18, 2005
    #2
    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. Kevin
    Replies:
    19
    Views:
    1,139
    Tris Orendorff
    Feb 13, 2006
  2. Paul
    Replies:
    8
    Views:
    440
    Rob Williscroft
    Dec 10, 2004
  3. Clemens Hintze
    Replies:
    0
    Views:
    292
    Clemens Hintze
    Nov 7, 2005
  4. aaragon
    Replies:
    12
    Views:
    1,307
    aaragon
    Nov 8, 2006
  5. globalrev
    Replies:
    4
    Views:
    774
    Gabriel Genellina
    Apr 20, 2008
Loading...

Share This Page