STL multimap value_type compare 1

[maluk]

Hi all!

The STL multimap accepts duplicate keys such that the following entry is valid for a multimap:


KEY VALUE

foo bar
jack jill


Now the problem is, multimap also accepts duplicate entries such that if I would add another foo, bar pair the multimap will accept it. So now my multimap might look like this:


KEY VALUE

foo bar
foo bar
jack jill



The question is, is there a short way to prevent insertion of VALUE duplicates?

The long way to do it is before a call to insert, I should iterate all those whose KEY is "foo" and if I find a VALUE that is the same, I will not insert it. This for me consumes too much CPU time if I have big data. So now I need a short way to do it.

Can anybody tell me or show me a short way of doing it?

Rome did not create a great empire by having meetings, they did it by
killing all those who opposed them.

- janvier -

 

[ArkM]

The shortest way to do it: use map (of key+data structures).
Apropos, find value in map/multimap is not so time-consuming op: it's a balanced tree structure (in most of STL implementations) so it has log(N) factor only.

 

[cpjust]

The multimap constructor takes a sort predicate as an optional argument. You might be able to prevent duplicates from being added by providing your own predicate. I've never tried it though.

 

[maluk]

Isn't that the predicate for the multimap is for sorting only?

Rome did not create a great empire by having meetings, they did it by
killing all those who opposed them.

- janvier -

 

[uolj]

Yes, for the multimap, since all duplicates are allowed, you wouldn't be able to prevent insertion by changing the sort. Of course, that's exactly the idea mentioned by ArkM for using a regular map. Define a sorting predicate for your key/value pair instead of just for your key. In fact, I would just make a struct that holds the key and the value and put those structs into a set.

#include <iostream>
#include <string>
#include <set>

struct data
{
    data(const std::string& k, const std::string& v) : key(k), value(v) { }
    std::string key;
    std::string value;
};

bool operator<(const data& lhs, const data& rhs)
{
    int cmp = lhs.key.compare(rhs.key);
    if (cmp == 0)
        return lhs.value < rhs.value;
    return (cmp < 0);
}

void insert_data(std::set<data>& data_set, const std::string& k,
                                           const std::string& v)
{
    std::cout << "Insert (" << k << "," << v << ") ";
    if (data_set.insert(data(k,v)).second)
        std::cout << "succeeded." << std::endl;
    else
        std::cout << "failed." << std::endl;
}

void output_data(const std::set<data>& data_set)
{
    std::cout << "\nSet contents:\n";
    for (std::set<data>::const_iterator iter = data_set.begin(),
         end = data_set.end(); iter != end; ++iter)
    {
        std::cout << "(" << iter->key << "," << iter->value << ")\n";
    }
}

int main()
{
    std::set<data> data_set;
    insert_data(data_set, "Foo", "Bar");
    insert_data(data_set, "Jack", "Jill");
    insert_data(data_set, "Foo", "Jill");
    insert_data(data_set, "Jack", "Bar");
    insert_data(data_set, "Foo", "Bar");
    insert_data(data_set, "Jack", "Jill");
    output_data(data_set);
}

Output:

Insert (Foo,Bar) succeeded.
Insert (Jack,Jill) succeeded.
Insert (Foo,Jill) succeeded.
Insert (Jack,Bar) succeeded.
Insert (Foo,Bar) failed.
Insert (Jack,Jill) failed.

Set contents:
(Foo,Bar)
(Foo,Jill)
(Jack,Bar)
(Jack,Jill)

Note that duplicates are allowed for values as long as the key is different. If you want all duplicates of values to be disallowed, you should keep a separate std::set of values, and store either a copy of or a pointer to those values in your map.

 

[maluk]

Thanks uolj! Can't I do the one you did for a multimap?

Rome did not create a great empire by having meetings, they did it by
killing all those who opposed them.

- janvier -

 

[uolj]

You can, but why would you want to? The effects will be different based on the different properties of maps vs. sets and multi- containers versus regular containers.

There are four options (technically there are 8, but I won't talk about the unordered_map containers that are based on hash tables since most library implementations don't have standard versions of them yet). The four standard options are set, multiset, map and multimap.

The difference between a set and a map is that a set holds only a single object. Basically, its key is its value, whereas a map holds a key and a separate value. In your case, because your "value" actually affects how entries are sorted in the container and whether they are duplicates, that "value" is really part of the key. That is why I used set rather than map, because the value string is really part of a more complex key structure that includes the combination of your key string and your value string.

Either way the data will be saved in the container, but by combining them into a struct (or an std:air would work as well) and putting them into a set you are able to use the value to help identify duplicates. If you were to use that struct in a map instead of a set, what would you put as the value?

Now, the second half of the question is whether you want to use set or multiset (or map vs. multimap). In that case, the question is whether you want to allow duplicate keys or not. In my example, I do not want to allow duplicates, because the combined key-value pair that is held by the set already allows the same key string to appear automatically as long as the values are different. It relies on the fact that a set doesn't allow duplicate entries to avoid having two data objects with the same key string and the same value string, and that was the original goal - allow duplicate key strings but don't allow duplicate key strings that share a value string.

So, you could use your own struct and add your own sorting method with a multimap, but doing so won't allow you to achieve the desired behavior because multimap works differently from set in those two important ways.