How to Represent a Set of Pointers with Customized

问题:

Basically, I want to save a set of pointers, which should be sorted by my customized compare function, but the uniqueness should still be determined by the pointer itself.

However:

#include <iostream>
#include <string>
#include <set>
#include <utility>
#include <functional>
using namespace std;

//         count, word
typedef pair<int, string> WordFreq;

struct WordFreqPointerCmp
{
    bool operator()(const WordFreq* lhs, const WordFreq* rhs) const
    {
        return lhs->first > rhs->first;
    }
};

int main()
{
    set<WordFreq*, WordFreqPointerCmp> s;
    s.insert(new WordFreq(1, "word1")); // Inserted
    s.insert(new WordFreq(1, "word2")); // This is not inserted
    s.insert(new WordFreq(3, "word3")); // Inserted

    cout << s.size() << endl;

    for (set<WordFreq*, WordFreqPointerCmp>::iterator it = s.begin();
         it != s.end(); ++it)
    {
        cout << (*it)->second << ": " << (*it)->first << endl;
    }

    return 0;
}
/* Output:
2
word3: 3
word1: 1
 */

As you can see that the ordering is correct, but the duplicate testing is wrong. What I am trying to do is:

• For ordering, I want to use WordFreqPointerCmp;

• For duplicate testing, I want to use the original meaning of raw Pointer comparsion, i.e., the address comparison, which means, even the following set should have two entries in the set;

  set<WordFreq*, WordFreqPointerCmp> s;
  s.insert(new WordFreq(1, "word1"));
  s.insert(new WordFreq(1, "word1"));
  

I also tried the following, but same result:

template<>
struct greater<WordFreq*>
{
    bool operator()(WordFreq* const& lhs, WordFreq* const& rhs) const
    {
        return lhs->first > rhs->first;
    }
};
set<WordFreq*, greater<WordFreq*> > s;

回答1:

while this post is ancient, I've just faced the same issue, so it may help somebody..

In your code you only handle one value, but what if values are the same? Then set treats it as the same element. The proper solution would be to extend your compare function to give set additional information how to test for duplicates. It can be something arbitrary like comparing strings, for example in your case:

struct WordFreqPointerCmp
{
    bool operator()(const WordFreq* lhs, const WordFreq* rhs) const
    {
        if (lhs->first == rhs->first)
            return lhs->second > rhs->second;
        else
            return lhs->first > rhs->first;
    }
};

回答2:

I am not sure what the problem is. Since you want the first component of your pair to be the key that determines uniqueness, inserting two "WordFreq" with key = 1 should lead to the second evict the first. Results match expectation here.

Update: I guess, I misunderstood something. Since you want duplicate keys, you are probably looking for multimap.

Update 2: To make this work you need to add a step before adding a new object: Iterate over all values of the same key, and kick those out that point to the object being added. Also, I forgot to mention there is multiset which is probably what you'd prefer.

I admit, here is where Java's HashSet with it's separate order and equality tests come in handy. Maybe you can find a C++ version of it.