Re: Picking a mapping type's value_type
Jeffrey Yasskin wrote:
I'm implementing a vector_map<Key,Value> backed by a
vector<pair<Key,Value>> which maintains its pairs in sorted order by
key and uses std::lower_bound for lookups, and I've run into a problem
with the Container requirement that vector_map::value_type and
vector_map::iterator::value_type be identical.
Why not use a std::map<Key, Value>? For one, inserting and removing
items would be faster with a map than with a vector; a std::map has an
additional advantage over a std::vector in that inserting or removing
elements from the container does not invalidate any of the map's other
iterators. Moreover, elements in a map are always kept in sorted order;
and std::map offers - not only lower_bound() - but upper_bound() and
equal_range() methods as well.
It looks like the only practical effects of value_type are the argument
to .insert() and the return type of operator*(). For
iterator::operator*(), I need to return something that lets people
change the value but not the key. The simplest choice is a proxy object
that contains a vector::iterator and has "const Key& key() const",
"Value& value()", and "const Value& value() const" methods (perhaps the
iterator type itself). For .insert(), I need to accept something that's
constructible from a Key and a Value and convertible to pair<Key,
Value>. pair<Key, Value> itself works fine, but isn't the same as the
result of operator*().
Programmers generally expect to be able to retrieve values in a map
directly - by specifying a key. It should not necessary to use an
iterator at all. A std::map, for example, offers both operator[] and
at() for accessing values based on their key:
my_map[ akey] = avalue;
The fact that it's this complicated to define what should be a simple
container leads me to suspect that I'm doing something wrong. How did
the committee intend people to define extra mapping containers? Is it
ok for vector_map::iterator::value_type to only be implicitly
convertible to vector_map::value_type rather than identical?
I imagine the committee expected that C++ programmers who needed a map
container would use the one provided in the Standard Library. That
seems to explain why std::map is there. So it's a pretty safe bet that
the committee did not expect anyone to reimplement their own map
container out of a std::vector instead.
Greg
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]