reference l-value

Discussion in 'C++' started by homsan toft, Dec 20, 2005.

  1. homsan toft

    homsan toft Guest

    Hi,

    I'm (still) trying to return a pair<const Key, T> from
    iterator dereference. So I defined a proxy class in the
    obvious way:

    template<class KeyT, class DataT>
    struct ref_proxy
    {
    typedef const KeyT first_type;
    typedef DataT second_type;
    //! Pair Associative value_type
    typedef std::pair<const KeyT, DataT> pair_type;

    ref_proxy(first_type& a, second_type& b) : first(a), second(b) {}

    //! Copy convertible to Pair Associative value_type
    operator pair_type() const { return pair_type(first, second); }

    first_type & first;
    second_type & second;
    };

    It is passed into iterator class via nonconst_traits<ref_proxy<Key,T> >,
    and typedef'd as value_type in there.
    Now try to use it, with mixed failure:

    mymap::MyMap<std::string, int> mappy;
    mappy["gack"] = 3;
    MyMap::iterator it = mappy.begin();

    (*it).second = 5; // compiler error: not an l-value

    // but this works, and does the right thing
    typedef mymap::detail::ref_proxy<std::string, int> proxy;
    proxy& ref = *it;
    ref.second = 5;


    What gives? I read about references and noted non-const refs
    get no type conversion. Is it a type lookup failure, or what
    am I missing?

    Thanks,

    homsan
    homsan toft, Dec 20, 2005
    #1
    1. Advertising

  2. homsan toft

    mlimber Guest

    homsan toft wrote:
    > Hi,
    >
    > I'm (still) trying to return a pair<const Key, T> from
    > iterator dereference. So I defined a proxy class in the
    > obvious way:
    >
    > template<class KeyT, class DataT>
    > struct ref_proxy
    > {
    > typedef const KeyT first_type;
    > typedef DataT second_type;
    > //! Pair Associative value_type
    > typedef std::pair<const KeyT, DataT> pair_type;
    >
    > ref_proxy(first_type& a, second_type& b) : first(a), second(b) {}
    >
    > //! Copy convertible to Pair Associative value_type
    > operator pair_type() const { return pair_type(first, second); }
    >
    > first_type & first;
    > second_type & second;
    > };
    >
    > It is passed into iterator class via nonconst_traits<ref_proxy<Key,T> >,
    > and typedef'd as value_type in there.
    > Now try to use it, with mixed failure:
    >
    > mymap::MyMap<std::string, int> mappy;
    > mappy["gack"] = 3;
    > MyMap::iterator it = mappy.begin();
    >
    > (*it).second = 5; // compiler error: not an l-value
    >
    > // but this works, and does the right thing
    > typedef mymap::detail::ref_proxy<std::string, int> proxy;
    > proxy& ref = *it;
    > ref.second = 5;
    >
    >
    > What gives? I read about references and noted non-const refs
    > get no type conversion. Is it a type lookup failure, or what
    > am I missing?
    >
    > Thanks,
    >
    > homsan


    Can you post a complete code sample that demonstrates the problem?

    Cheers! --M
    mlimber, Dec 20, 2005
    #2
    1. Advertising

  3. homsan toft

    homsan toft Guest

    mlimber wrote:
    >
    > Can you post a complete code sample that demonstrates the problem?


    Well, in fact I can. This is so shrunk. Still 200 lines...

    The thing I'm asking is of course at end of code.
    Before that: namespace detail
    const_traits, nonconst_traits -- iterator traits
    ref_proxy -- the problem child
    micromap_iter is real code, the point of it is operator*()
    - it wants to return a proper pair<const Key, T>, but key, T
    are stored separately so it returns a ref_proxy<const Key, T>
    which almost resolves to pair<const Key &, T&>

    The micromap<Key, T> class is a joke, but shows the basic behaviour:
    key, T's are stored separately, it has a mm_iter_base iterator
    that offers methods key(), val() and no dereference.

    The micromap::iterator typedef is real code - I ripped it off
    various implementations to get proper syntax and semantix.
    Bonus question: Is the whole iterator definition rightish?
    (given that operator--(), operator++(int) etc are not defined,
    so it's incomplete, but those details are not relevant
    in this example).

    The problem is shown in fiddle_my_map at end of post:
    iterator dereference returns a ref_proxy object, which
    (i) converts to pair<const Key, T>,
    (iia) can be assigned to a ref_proxy &
    (iib) the reference to a ref_proxy is mutable,
    ie ref.second = 5 compiles, and will change the map,
    BUT
    (iii) (*it).second gives compiler error "not an l-value". (MSVC 7.1)

    I want (*it).second to be assignable. What am I missing?

    -------- 8< -----------------------

    #include <utility>
    #include <iterator>

    int main(int argc, char* argv[])
    {
    void fiddle_my_map();
    fiddle_my_map();
    return 0;
    }

    namespace detail {

    template <class T> struct nonconst_traits;

    template <class T>
    struct const_traits {
    typedef T value_type;
    typedef const T& reference;
    typedef const T* pointer;
    typedef const_traits<T> ConstTraits;
    typedef nonconst_traits<T> NonConstTraits;
    };

    template <class T>
    struct nonconst_traits {
    typedef T value_type;
    typedef T& reference;
    typedef T* pointer;
    typedef const_traits<T> ConstTraits;
    typedef nonconst_traits<T> NonConstTraits;
    };

    // This attempts to fake std::pair<const Key, T> by reference to T
    template<class KeyT, class DataT>
    struct ref_proxy
    {
    typedef const KeyT first_type;
    typedef DataT second_type;
    //! Pair Associative value_type
    typedef std::pair<const KeyT, DataT> pair_type;

    ref_proxy(first_type& a, second_type& b) : first(a), second(b) {}

    //! Copy convertible to Pair Associative value_type
    operator pair_type() const { return pair_type(first, second); }

    first_type & first;
    second_type & second;
    };

    template<class BaseIterT, class TraitsT>
    struct micromap_iter
    {
    typedef typename TraitsT::ConstTraits ConstTraits;
    typedef typename TraitsT::NonConstTraits NonConstTraits;

    typedef BaseIterT base_iter;
    typedef micromap_iter<BaseIterT, TraitsT> this_type;

    typedef typename TraitsT::value_type value_type;
    typedef typename TraitsT::pointer pointer;
    typedef typename TraitsT::reference reference;

    typedef std::bidirectional_iterator_tag iterator_category;
    typedef ptrdiff_t difference_type;
    typedef std::size_t size_type;

    typedef micromap_iter<BaseIterT, ConstTraits> const_iterator;
    typedef micromap_iter<BaseIterT, NonConstTraits> iterator;
    friend const_iterator;
    friend iterator;

    micromap_iter() {}
    // copy constructor for iterator and constructor from iterator for const_iterator
    micromap_iter(const iterator& it) : m_iter(it.m_iter) {}

    micromap_iter(base_iter it) : m_iter(it) {}

    value_type operator*() const {
    return value_type(const_cast<base_iter&>(m_iter).key(), const_cast<base_iter&>(m_iter).val());
    }

    this_type& operator++() { m_iter.increment(); return *this; }

    this_type& operator--() { m_iter.decrement(); return *this; }

    bool operator== (const_iterator rhs) const { return m_iter.pos() == rhs.m_iter.pos(); }
    bool operator!= (const_iterator rhs) const { return m_iter.pos() != rhs.m_iter.pos(); }

    private:
    base_iter m_iter;
    };
    }

    template<class KeyT, class DataT>
    class micromap
    {
    public:
    typedef KeyT key_type;
    typedef DataT mapped_type;
    typedef std::pair<const KeyT, DataT> value_type;
    typedef value_type * pointer;
    typedef const value_type * const_pointer;
    typedef value_type & reference;
    typedef const value_type & const_reference;
    typedef std::size_t size_type;
    typedef detail::ref_proxy<KeyT, DataT> ref_proxy;

    struct mm_iter_base;

    micromap() : m_count(0) {}

    typedef detail::micromap_iter< mm_iter_base,
    detail::nonconst_traits<ref_proxy>
    > iterator;
    typedef detail::micromap_iter< mm_iter_base,
    detail::const_traits<ref_proxy>
    > const_iterator;

    iterator begin() { return mm_iter_base(keys, vals, 0); }
    const_iterator begin() const { return mm_iter_base(keys, vals, 0); }
    iterator end() { return mm_iter_base(keys, vals, m_count); }
    const_iterator end() const { return mm_iter_base(keys, vals, m_count); }

    // iterator implementation
    struct mm_iter_base
    {
    typedef mm_iter_base this_type;

    mm_iter_base(key_type* ks, mapped_type* ms, size_type index)
    : keys(ks), vals(ms), m_index(index)
    {}
    mm_iter_base() : keys(0), vals(0), m_index(-1) {}

    const key_type& key() const { return keys[m_index]; }
    mapped_type& val() { return vals[m_index]; }
    mapped_type val() const { return vals[m_index]; }

    void increment() { ++m_index; }
    void decrement() { --m_index; }
    size_t pos() const { return m_index; }
    private:
    size_type m_index;
    key_type* keys;
    mapped_type* vals;
    };

    // ok, rest of this class is bad joke, but I don't want to post 2000 lines
    mapped_type& operator[](const key_type& k)
    {
    // strong exception guarantee ;)
    if (m_count >= 3)
    throw std::bad_alloc("micromap full");
    size_type index = 0;
    while( index < m_count && k > keys[index] )
    index++;
    // sorted multiple...
    if (index < m_count) {
    std::copy(keys + index, keys + m_count, keys + index + 1);
    std::copy(vals + index, vals + m_count, vals + index + 1);
    vals[index] = mapped_type();
    }
    keys[index] = k;
    m_count++;
    return vals[index];
    }

    private:
    size_type m_count;
    key_type keys[3];
    mapped_type vals[3];
    };

    void fiddle_my_map()
    {
    typedef micromap<std::string, int> MyMap;
    MyMap mymap;
    mymap["gack"] = 3;
    MyMap::iterator it = mymap.begin();
    typedef detail::ref_proxy<std::string, int> proxy;
    proxy& ref = *it;
    ref.second = 5;
    // ref_proxy is convertible to pair<key,T>
    MyMap::value_type seeme = *it;
    // BUT assignment to dereferenced ref_proxy doesn't work
    (*it).second = 5; // compiler error "must be l-value". WHY!!?? (*sob*)

    mymap["and..."] = 3;
    // This prints and...=3 gack=5
    while (it != mymap.end()) {
    std::cout << (*it).first << "=" << (*it).second << " ";
    ++it;
    }
    }
    homsan toft, Dec 21, 2005
    #3
  4. homsan toft

    Neil Cerutti Guest

    On 2005-12-21, homsan toft <> wrote:
    > mlimber wrote:
    >>
    >> Can you post a complete code sample that demonstrates the problem?

    >
    > Well, in fact I can. This is so shrunk. Still 200 lines...
    >
    > The thing I'm asking is of course at end of code.
    > Before that: namespace detail
    > const_traits, nonconst_traits -- iterator traits
    > ref_proxy -- the problem child
    > micromap_iter is real code, the point of it is operator*()
    > - it wants to return a proper pair<const Key, T>, but key, T
    > are stored separately so it returns a ref_proxy<const Key, T>
    > which almost resolves to pair<const Key &, T&>
    >
    > The micromap<Key, T> class is a joke, but shows the basic behaviour:
    > key, T's are stored separately, it has a mm_iter_base iterator
    > that offers methods key(), val() and no dereference.
    >
    > The micromap::iterator typedef is real code - I ripped it off
    > various implementations to get proper syntax and semantix.
    > Bonus question: Is the whole iterator definition rightish?
    > (given that operator--(), operator++(int) etc are not defined,
    > so it's incomplete, but those details are not relevant
    > in this example).
    >
    > The problem is shown in fiddle_my_map at end of post:
    > iterator dereference returns a ref_proxy object, which
    > (i) converts to pair<const Key, T>,
    > (iia) can be assigned to a ref_proxy &
    > (iib) the reference to a ref_proxy is mutable,
    > ie ref.second = 5 compiles, and will change the map,
    > BUT
    > (iii) (*it).second gives compiler error "not an l-value". (MSVC 7.1)
    >
    > I want (*it).second to be assignable. What am I missing?


    There were several errors I had to correct, but I still can't get
    the code to compile as far as you say.

    > -------- 8< -----------------------
    >
    > #include <utility>
    > #include <iterator>


    Missing headers <iostream> and <exception>

    SNIP

    > // This attempts to fake std::pair<const Key, T> by reference to T
    > template<class KeyT, class DataT>
    > struct ref_proxy
    > {
    > typedef const KeyT first_type;
    > typedef DataT second_type;
    > //! Pair Associative value_type
    > typedef std::pair<const KeyT, DataT> pair_type;
    >
    > ref_proxy(first_type& a, second_type& b) : first(a), second(b) {}
    >
    > //! Copy convertible to Pair Associative value_type
    > operator pair_type() const { return pair_type(first, second); }


    How can that operation be applied to a const ref_proxy?

    > first_type & first;
    > second_type & second;
    > };
    >
    > template<class BaseIterT, class TraitsT>
    > struct micromap_iter
    > {
    > typedef typename TraitsT::ConstTraits ConstTraits;
    > typedef typename TraitsT::NonConstTraits NonConstTraits;
    >
    > typedef BaseIterT base_iter;
    > typedef micromap_iter<BaseIterT, TraitsT> this_type;
    >
    > typedef typename TraitsT::value_type value_type;
    > typedef typename TraitsT::pointer pointer;
    > typedef typename TraitsT::reference reference;
    >
    > typedef std::bidirectional_iterator_tag iterator_category;
    > typedef ptrdiff_t difference_type;
    > typedef std::size_t size_type;
    >
    > typedef micromap_iter<BaseIterT, ConstTraits> const_iterator;
    > typedef micromap_iter<BaseIterT, NonConstTraits> iterator;
    > friend const_iterator;
    > friend iterator;


    After correcting the syntax error in the friend declarations, g++
    3.3.1 refuses to accept those declarations, since the class
    becomes "implicitly friends with itself."

    > micromap_iter() {}
    > // copy constructor for iterator and constructor from iterator for const_iterator
    > micromap_iter(const iterator& it) : m_iter(it.m_iter) {}
    >
    > micromap_iter(base_iter it) : m_iter(it) {}
    >
    > value_type operator*() const {
    > return value_type(const_cast<base_iter&>(m_iter).key(), const_cast<base_iter&>(m_iter).val());
    > }


    How can that operation be applied to a const object?

    > this_type& operator++() { m_iter.increment(); return *this; }
    >
    > this_type& operator--() { m_iter.decrement(); return *this; }
    >
    > bool operator== (const_iterator rhs) const { return m_iter.pos() == rhs.m_iter.pos(); }
    > bool operator!= (const_iterator rhs) const { return m_iter.pos() != rhs.m_iter.pos(); }
    >
    > private:
    > base_iter m_iter;
    > };
    > }
    >
    > // ok, rest of this class is bad joke, but I don't want to post 2000 lines
    > mapped_type& operator[](const key_type& k)
    > {
    > // strong exception guarantee ;)
    > if (m_count >= 3)
    > throw std::bad_alloc("micromap full");


    SNIP

    std::bad_alloc hasn't got a constructor that takes an argument.

    > void fiddle_my_map()
    > {
    > typedef micromap<std::string, int> MyMap;
    > MyMap mymap;
    > mymap["gack"] = 3;
    > MyMap::iterator it = mymap.begin();
    > typedef detail::ref_proxy<std::string, int> proxy;
    > proxy& ref = *it;


    g++3.3.1 refuses to compile that line. Does the conversion work
    on your compiler?

    The proliferation of types is quite confusing.

    Perhaps it would be simpler to provide instead a key_iterator,
    value_iterator and const_value_iterator?

    Another solution might be to do as std::map does: handle the
    conversion from std::pair<KeyT, DataT> to std::pair<KeyT const,
    DataT> in your insert routine (using temporaries), storing nodes
    internally in a std::pair<KeyT const, DataT>. That's got to be
    easier than this attempt to contravene the type system using
    proxy objects.

    --
    Neil Cerutti
    Neil Cerutti, Dec 21, 2005
    #4
  5. homsan toft

    homsan toft Guest

    Neil Cerutti wrote:

    > On 2005-12-21, homsan toft <> wrote:
    >>
    >>iterator dereference returns a ref_proxy object, which
    >>(i) converts to pair<const Key, T>,
    >>(iia) can be assigned to a ref_proxy &
    >>(iib) the reference to a ref_proxy is mutable,
    >> ie ref.second = 5 compiles, and will change the map,
    >>BUT
    >>(iii) (*it).second gives compiler error "not an l-value". (MSVC 7.1)
    >>
    >>I want (*it).second to be assignable. What am I missing?

    >
    >
    > There were several errors I had to correct, but I still can't get
    > the code to compile as far as you say.


    Neil, thanks for your comments!
    I'm trying to acquire better habits... apologies for not trying harder.

    Running it through Comeau online helps a lot (why didn't think of that sooner??).

    Now on max warning level, MSVC does mention that the conversion to ref_proxy&
    is nonstandard, Ie, in fiddle_my_map():
    MyMap::iterator it = mymap.begin();
    typedef detail::ref_proxy<std::string, int> proxy;
    proxy& ref = *it; //<<<< so now I know this is incorrect conversion

    Comeau reports error: "initial value of reference to non-const must be an lvalue"

    Moreover, MSVC doesn't accept the conversion
    (*it).second = 5; // compiler error "must be l-value".
    - but Comeau gulps it.

    So MSVC near-silently converts the non-lvalue struct, but chokes on the l-value member(?)


    Your other comments duly noted.

    (except in proxy_ref struct:

    >> typedef std::pair<const KeyT, DataT> pair_type;
    >>
    >> operator pair_type() const { return pair_type(first, second); }

    >
    > How can that operation be applied to a const ref_proxy?


    It returns a copy std::pair<KeyT,DataT>. Is that non-const?

    line 9 of fiddle_my_map(),
    // ref_proxy is convertible to pair<key,T>
    MyMap::value_type seeme = *it;
    causes no complaint from Comeau.)


    > Perhaps it would be simpler to provide instead a key_iterator,
    > value_iterator and const_value_iterator?


    I'd like to do as nearly as possible a drop-in replacement for map...

    > Another solution might be to do as std::map does: handle the
    > conversion from std::pair<KeyT, DataT> to std::pair<KeyT const,
    > DataT> in your insert routine (using temporaries), storing nodes
    > internally in a std::pair<KeyT const, DataT>. That's got to be
    > easier than this attempt to contravene the type system using
    > proxy objects.


    I'm not deeply in love with the ref_proxy class, just trying to fake
    that pair<const K, T> interface.
    Did seem like it could be made to work, but guess I'll drop it.


    Thanks,

    homsan
    homsan toft, Dec 22, 2005
    #5
  6. homsan toft

    Neil Cerutti Guest

    On 2005-12-22, homsan toft <> wrote:
    > Neil Cerutti wrote:
    >>> operator pair_type() const { return pair_type(first, second); }

    >>
    >> How can that operation be applied to a const ref_proxy?

    >
    > It returns a copy std::pair<KeyT,DataT>. Is that non-const?
    >
    > line 9 of fiddle_my_map(),
    > // ref_proxy is convertible to pair<key,T>
    > MyMap::value_type seeme = *it;
    > causes no complaint from Comeau.)


    I did not notice that before. I assumed it was returning a
    ref_proxy, which contains modifiable references. If you return a
    copy of the data, then nothing you modify in that copy will have
    any effect on the data stored in your map.

    > I'm not deeply in love with the ref_proxy class, just trying to
    > fake that pair<const K, T> interface. Did seem like it could be
    > made to work, but guess I'll drop it.


    It most likely can be made to work; it just won't be easy. ;-)
    I've not been able to come up with anything that doesn't use a
    reinterpret_cast.

    --
    Neil Cerutti
    Neil Cerutti, Dec 22, 2005
    #6
    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. Darren
    Replies:
    0
    Views:
    494
    Darren
    Oct 11, 2004
  2. Dude
    Replies:
    0
    Views:
    353
  3. ce
    Replies:
    1
    Views:
    2,988
  4. sam pal
    Replies:
    3
    Views:
    543
    E. Robert Tisdale
    Jul 16, 2003
  5. Craig Nicol
    Replies:
    2
    Views:
    466
    Craig Nicol
    May 10, 2004
Loading...

Share This Page