map iterators interface

Discussion in 'C++' started by brutus, Dec 16, 2005.

  1. brutus

    brutus Guest

    Hi,

    I'm trying to define a map-like interface to a container.

    My basic problem is that the container is associative,
    but values are not stored in pairs internally.
    (and as we know, the map value_type must be pair<const Key, T>)
    Instead there's a list (vector) of values, and a method
    to get key reference.

    But I'm ready to increase the values vector to store pairs.
    So... Internally, values are actually stored in a vector.
    But std::vector can only store pair with non-const types.
    Now I have
    std::vector<std::pair<Key, T> > m_values;
    and
    typedef std::pair<const Key, T> value_type;

    How do I define the reference type returned from (non-const) iterators?

    Trouble invites itself to the iterator dereference operator:

    class iterator {
    friend class MyContainer;
    iterator(const ValueList* values) : m_values(values), current(0) {}
    public:
    reference operator*() const { ...? }
    };

    Now, in boost concept checks for Forward Container (which is
    required for Pair Associative and most any container types),
    I get back-paddled in
    reference r = *it;
    I see two ways of getting past this:

    (i) typedef value_type reference;
    and returning a copy of the value - but this has wrong semantics:
    assigning to (*iter).second doesn't change the stored value.

    (ii) return *reinterpret_cast<value_type*>(&(*m_vector)[current]);
    Well, it works, sort of, but aint pretty... or portable?

    Any better approach?
    Should I define a custom value_type class with desired behaviour?
    And if so, doyouknow some similar example I could look at?
    (I've no desire to attempt to write a custom vector class that stores
    pairs with const members, but perhaps one exists somewhere?)

    (Of course I could make it look like anything, ie let iterator point to
    mapped_type and add a method key() to access the key, or whatever,
    but while it's an option, it's not the point...)

    Thanks,

    homsan
     
    brutus, Dec 16, 2005
    #1
    1. Advertising

  2. brutus

    Neil Cerutti Guest

    On 2005-12-16, brutus <> wrote:
    > Hi,
    >
    > I'm trying to define a map-like interface to a container.


    The C++ type system gets in the way here, as you've found out.

    > My basic problem is that the container is associative, but
    > values are not stored in pairs internally. (and as we know, the
    > map value_type must be pair<const Key, T>) Instead there's a
    > list (vector) of values, and a method to get key reference.
    >
    > But I'm ready to increase the values vector to store pairs.
    > So... Internally, values are actually stored in a vector. But
    > std::vector can only store pair with non-const types. Now I
    > have
    >
    > std::vector<std::pair<Key, T> > m_values;
    > and
    > typedef std::pair<const Key, T> value_type;
    >
    > How do I define the reference type returned from (non-const) iterators?
    >
    > I see two ways of getting past this:
    >
    > (i) typedef value_type reference;
    > and returning a copy of the value - but this has wrong semantics:
    > assigning to (*iter).second doesn't change the stored value.
    >
    > (ii) return *reinterpret_cast<value_type*>(&(*m_vector)[current]);
    > Well, it works, sort of, but aint pretty... or portable?


    It's not pretty, and it's implementation defined, but in practice
    it's portable.

    > Any better approach?


    Do a Google Groups search for "const_cast std::pair" for some
    interesting previous discussion of this topic.

    > Should I define a custom value_type class with desired
    > behaviour?


    std::map, facing the same problem when implementing its insert
    function, makes temporaries. You could do that too, though it
    seems considerably more horrible to do in the operator* of
    an iterator than in map::insert.

    > And if so, doyouknow some similar example I could look at?


    It's a big obstacle to a nice vector-based associative container,
    but I don't know of any commonly accepted solution.

    --
    Neil Cerutti
     
    Neil Cerutti, Dec 16, 2005
    #2
    1. Advertising

  3. brutus

    brutus Guest

    Neil Cerutti wrote:

    >>I'm trying to define a map-like interface to a container.

    >
    > The C++ type system gets in the way here, as you've found out.


    A little strange, as this must've been known and understood
    at the time of standardization - it seemed a side comment in
    one of my books hints that the std::pair template constructor
    was defined specifically, or partly, to handle map insertion.

    If we could just have (*iter).first() and (*iter).second()
    (or any of a host of other notations) there wouldn't be a problem at all...

    >>My basic problem is that the container is associative, but
    >>values are not stored in pairs internally.



    >>(ii) return *reinterpret_cast<value_type*>(&(*m_vector)[current]);
    >> Well, it works, sort of, but aint pretty... or portable?

    >
    >
    > It's not pretty, and it's implementation defined, but in practice
    > it's portable.


    - so good enough to use at home (if it works), not good enough to
    show around.

    >>Any better approach?


    (well, if I want to be safer but no less sorry, iterators can
    of course be immutable. Or change value_type. After all it's not
    exactly a map, just an associative damn container.)

    > Do a Google Groups search for "const_cast std::pair" for some
    > interesting previous discussion of this topic.


    Thanks, that got me some relevant hits!
    And apparently a well-known problem. Darn.

    I tried a few searches, but didn't find the right phrase
    (>50k hits, mostly source files and local copies of SGI docs)

    > It's a big obstacle to a nice vector-based associative container,
    > but I don't know of any commonly accepted solution.


    So for once I'm not _just_ missing some basic syntax rule,
    but have a real problem. Not sure if I like it better out here...

    Thanks for your comments!

    Bruno
     
    brutus, Dec 17, 2005
    #3
    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. Jim West
    Replies:
    14
    Views:
    6,236
    Alex Vinokur
    Dec 18, 2003
  2. Vlad
    Replies:
    0
    Views:
    361
  3. Christian Christmann

    problems with stl map iterators

    Christian Christmann, Apr 19, 2005, in forum: C++
    Replies:
    3
    Views:
    2,162
    Christian Christmann
    Apr 19, 2005
  4. Marcin Kaliciñski

    Iterators and reverse iterators

    Marcin Kaliciñski, May 8, 2005, in forum: C++
    Replies:
    1
    Views:
    489
    Kai-Uwe Bux
    May 8, 2005
  5. , India
    Replies:
    10
    Views:
    1,084
    James Kanze
    Aug 8, 2009
Loading...

Share This Page