fail to insert new elements to set when I add customized comparator

Question

Here is my original code. I have two functions, add and print_out. "add" is used to update the times of a url by incrementing one every time when a user use that. And print_out just print all of urls that have bee used in order of times.

# include<iostream>
# include<unordered_map>
# include<set>
# include<string>
# include<utility>

using namespace std;

struct compare { // simple comparison function
   public:
      bool operator()(const pair<string, int>& x, const pair<string, int> &y) const
      { return x.second > y.second; } // returns x>y
};


class Sol{

    set< pair<string, int>, compare  > db;
// the unordered_map is used to store the iterator of a url in my set, db, so that I can pull the pair of this url later, and update it.
    unordered_map< string, set< pair<string, int> >:: iterator > table;


public:

    Sol(){};
    void add( string url); 
    void print_out();
};

void Sol :: add( string url){

    //  when a url is used, the times of it increments by it. If this url is used for the first time, then just insert new pair { url, 1 } into my set.

    if( table.find( url ) != table.end() ){

        int times = (*table[url]).second +1;
        db.erase( table[url] );
        db.insert( { url, times} );
        table[url] = db.find( { url, times} );
    }
    else{   
        pair<string, int> p = { url, 1};
        db.insert( p );

    }

    return;

}

void Sol :: print_out(){

// print out all of urls in order of times they have been used so far

    for( auto ite = db.begin() ; ite != db.end() ; ite++  )
        cout<< (*ite).first << "  " << (*ite).second<<"\n";

    return;
}

Because you are comparing pair::second, but pair::second is always one! — john, Feb 13 '18 at 08:01
the comparator is not only used to sort the elements, but also to decide what elements are equal. You actually only add elements that look equal to the set, hence there is only a single element — 463035818_is_not_an_ai, Feb 13 '18 at 08:02
If you want multiple elements that are positioned in the "same place" in an order, you can use `std::multi_set<...>` — Caleth, Feb 13 '18 at 10:09
Thanks, everybody. I thought pair {"A", 1} is different from pair { "B", 1 } because first elements in these two are different. — I Like CS But Don't Like Work, Feb 13 '18 at 15:24

score 4 · Answer 1 · answered Feb 13 '18 at 08:05

4

std::set uses its comparator (cmp) for two things:

Determine ordering of iteration: for two elements a and b, if cmp(a, b), then a comes before b in the order.
Determine item equivalent. If cmp(a, b) and cmp(b, a) are both false, the items are considered equivalent and only one of them can be present in the set.

Your comparator is > on the second element of the pair, and your function add always sets the second element to 1. Therefore, as far as the set is concerned, all the pairs are equivalent and only the first one will be stored.

answered Feb 13 '18 at 08:05

Angew is no longer proud of SO

167,307
17
350
455

I cannot suggest a solution because that depends on what you're trying to achieve, what your data represents, etc. If you share more, I can expand the answer. – Angew is no longer proud of SO Feb 13 '18 at 08:06
HI, Angew. Thanks for your answers! My goal is to design a simple system that could store the number of url our users have been using, and output the first five urls that has been used. So My idea is that I will use BST-like structure to store url and times it has been used. That's why I use pair {string, int}. And then elements in this BST is sorted by the second element of pair. So actually, my class will have two functions, one is add, the other function is to print out all of urls in order of times it has been used. every time when a url is used, the times in the BST will increment by one – I Like CS But Don't Like Work Feb 13 '18 at 15:34
@Hsiu-WeiYang You may want to look into `std::multiset`, which can store multiple elements with the same key (= number of uses in your case). However, note that (multi)set elements are *immutable:* you cannot change them once in the set. An increment would therefore need to be done as remove+add. Alternatively, you could look into [Boost.MultiIndex](http://www.boost.org/doc/libs/1_66_0/libs/multi_index/doc/index.html), but that is quite nontrivial to set up. [My answer](https://stackoverflow.com/a/39510606/1782465) about it could help. Or manually keep a sorted array. – Angew is no longer proud of SO Feb 14 '18 at 08:56
Thanks a lot, Angew! – I Like CS But Don't Like Work Feb 15 '18 at 07:31

fail to insert new elements to set when I add customized comparator

1 Answers1