non-sorted map?

[Aaron Walker]

I want a std::map<std::string, std::string> but I don't want it sorted by keys.
I've been able to simulate this with a vector of pairs and operator[].

class umap : public std::vector<std::pair<std::string, std::string > >
{
public:
std::string &operator[] (std::string s)
{
for (iterator i = begin() ; i != end() ; ++i)
if (i->first == s)
return i->second;

/* we got this far, so key must not exist */
push_back(std::make_pair(s, ""));
return back().second;
}
}

Not sure if this is the optimal way to go about it. Any suggestions?

[Karl Heinz Buchegger]

Aaron Walker wrote:

I want a std::map<std::string, std::string> but I don't want it sorted by keys.
Why not?
I've been able to simulate this with a vector of pairs and operator[].

class umap : public std::vector<std::pair<std::string, std::string > >
{
public:
std::string &operator[] (std::string s)
{
for (iterator i = begin() ; i != end() ; ++i)
if (i->first == s)
return i->second;

/* we got this far, so key must not exist */
push_back(std::make_pair(s, ""));
return back().second;
}
}

Not sure if this is the optimal way to go about it.
The performance will be lousy
Any suggestions?

The biggest question is: Why don't you want a sorted map? What's
the problem with letting the map do the sorting? Sorting is the
maps way to improve performance. Most often this is the key point
in using a map: Performance. That one can retrieve the items in a
map in a sorted way is of little importance to most applications.

--
Karl Heinz Buchegger
kb******@gascad.at

[Ivan Vecerina]

"Aaron Walker" <ka*****@cfl.rr.com> wrote in message
news:ZZ*********************@tornado.tampabay.rr.c om...

I want a std::map<std::string, std::string> but I don't want it sorted by
keys. I assume you want to control the sorting order manually?
(the automatic sorting by std::map is essential to improve
look-up performance with the [] operator).
I've been able to simulate this with a vector of pairs and operator[].

class umap : public std::vector<std::pair<std::string, std::string > >
{
public:
std::string &operator[] (std::string s)
{
for (iterator i = begin() ; i != end() ; ++i)
if (i->first == s)
return i->second;

/* we got this far, so key must not exist */
push_back(std::make_pair(s, ""));
return back().second;
}
}

Not sure if this is the optimal way to go about it. Any suggestions?

Don't create a new class unless you effectively enforce new invariants.
By publicly deriving from std::vector, you expose your class
to misuse (i.e. non-virtual destructor, and any code could mess-up
with the contents of the vector), and do not gain any concrete
benefit over a simple non-member function.

You should either:

a) provide a non-member function that does what you need:
std::string&
valueForKey( std::vector< std::pair<std::string, std::string> >& v,
, std::string const& myKey )
{ /*same as above*/ return ...->second; }

b) use containment (the vector is a private data member
of umap) and implement the interface needed by users.

Regards,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

[Donovan Rebbechi]

On 2005-03-21, Aaron Walker <ka*****@cfl.rr.com> wrote:

I want a std::map<std::string, std::string> but I don't want it sorted by
keys.
As has been asked -- why not ? Your version is just a less efficient version
of existing classes. You gain slight speedup on insertion (which you could
also get with a hash map), and trade that for vastly inferior performance on
lookup and removal.
I've been able to simulate this with a vector of pairs and operator[].

class umap : public std::vector<std::pair<std::string, std::string > >
A classic abuse of inheritance. Don't do this. Unless your class really IS-A
vector, don't use public inheritance. Use private inheritance or containment.
The vector class really doesn't have that many member functions, so it's
not unreasonable to re-implement them all, and when your class is not modelling
IS-A, it's a good idea to go through the busy work of checking each and every
member function that you plan to expose, instead of indiscriminately exposing
them all.
{
public:
std::string &operator[] (std::string s)
The signature of this function is wrong (should be const std::string&)
You also don't have a const version of
operator[], so you can't use operator[] on a const umap.

You actually need:

std::string& operator[](const std::string&);
const std::string& operator[](const std::string&) const;
return back().second;
}
}

Not sure if this is the optimal way to go about it. Any suggestions?

Use either a hash table (see if your STL implementation includes one, don't
try to write your own) or a map with a custom sorting method, depending on
what you're trying to achieve.

Cheers,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/

[msalters]

Donovan Rebbechi wrote:

On 2005-03-21, Aaron Walker <ka*****@cfl.rr.com> wrote:

I want a std::map<std::string, std::string> but I don't want it sorted by keys.
As has been asked -- why not ? Your version is just a less efficient

version of existing classes. You gain slight speedup on insertion (which you could also get with a hash map), and trade that for vastly inferior performance on lookup and removal.

The obvious answer to me would be, to keep the insertion order. Adding
a
new key should append that key/value pair, not insert in the middle.

Such a class could make sense in some contexts. It's not very difficult
to write. Sketch (not compiled)

template< typename K, typename V >
class associative_array {
typedef std::vector<std::pair<K,V> > vec;
vec data;
std::map< boost::ref<K>, vec::iterator > assoc;
public:
V& operator[]( K const& key]) { return assoc[key]->second; }
...

Of course, if K is small you can replace boost::ref<K> with K, the
OP wanted strings and storing them twice may be expensive. Another
solution could be to drop the map, and implement a Red-Black tree
yourself. You'd then store a node<K,V> containing two node<K,V>*s
but that is only needed if profiling shows the map is a bottleneck.

HTH,
Michiel Salters