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:air<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]

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:air<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.

 

[Ivan Vecerina]

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:air<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:air<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

 

[Donovan Rebbechi]

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:air<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,

 

[msalters]

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:air<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