map iterators interface

[brutus]

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

[Neil Cerutti]

On 2005-12-16, brutus <sk*******@tvalfager.se> 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

[brutus]

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