reference l-value

[homsan toft]

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

[mlimber]

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

[homsan toft]

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;
}
}

[Neil Cerutti]

On 2005-12-21, homsan toft <no*****@specific.org> 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

[homsan toft]

Neil Cerutti wrote:

On 2005-12-21, homsan toft <no*****@specific.org> 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

[Neil Cerutti]

On 2005-12-22, homsan toft <no*****@specific.org> 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