How to get set<string> to store string in size order?

[zhuang2653]

I want to read a set of keywords and store them in size order, and if you type same keywords twice, i can only store only once, so naturally, I want to store string using set<string> it can remove duplicate for me, however, I have to override < to get string stored in size order.
for example:
if the input are:"he" "helo" "hello" "he" "helloworld"
then the set should contain
"helloworld"
"hello"
"helo"
"he"

but the code I write sames to have a problem processing two strings with same size.

like input "a" "b" "c" "a"

instead of a set of{"a", "b", "c"}, i get {"a", "b", "c", "a"}, very confusing.

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

using namespace std;

struct word{
    string keyword;
    word(string keyword){
        this->keyword = keyword;
    }
    bool operator<(const struct word& right) const{
        cout<<"current word:"<<this->keyword<<endl;
        cout<<"right word:"<<right.keyword<<endl;
        cout<<"Are they the same? 0:same"<<this->keyword.compare(right.keyword)<<endl;
        if(this->keyword.size() == right.keyword.size()){
            return this->keyword.compare(right.keyword);
        } else {
            return this->keyword.size() > right.keyword.size();
        }
    }
};

class Solution{
public:
    int add(string input){
        word str(input);
        keywords.insert(str);
        return keywords.size();
    }
    void show(void) {
        for(auto str:keywords) {
            cout<<str.keyword;
        }
        cout<<endl;
    }

private:
    set<word> keywords;
};
int main() {
    int num;
    cin>>num;
    Solution solu;
    for (int i = 0; i < num; i++) {
        int opType;
        cin>>opType;
        cin.get();
        string str;
        getline(cin, str);
        switch(opType) {
            case 1:
                cout<<solu.add(str)<<endl;
                solu.show();
                break;
            default:
                break;
        }
    }
}

[kigar64551]

std::set is ordered. So, doesn't the default string ordering do this already, sort of?

Anyhow, you could implement a custom comparator:

struct cmp {
    bool operator() (const std::string &a, const std::string &b) const
    {
        return a.length() < b.length();
    }
};

std::set<std::string, cmp> keywords;

But be aware: If you compare strings only by length, then all strings of the same length will be considered "equal" by the std::set, so then you can have only one string of a specific length in the set at a time.

Therefore, maybe you want to use:

bool operator() (const std::string &a, const std::string &b) const
{
        const size_t n = a.length(), m = b.length();
        return (n == m) ? (a < b) : (n > m);
}

[JLBorges]

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

int main()
{
   struct custom_cmp_str
   {
       bool operator() ( const std::string& a, const std::string& b ) const noexcept
       {
           if( a.size() == b.size() ) return a < b ; // in ascending order for different strings with same size
           else return a.size() > b.size() ; // in descending order of sizes otherwise
       }
   };

   std::set< std::string, custom_cmp_str > set { "helloworld", "hello", "helo",  "he", "abcde", "hello", "vwxyz" } ;
   for( const std::string& str : set ) std::cout << str << '\n' ;
}

http://coliru.stacked-crooked.com/a/be7c1d6eaf8a1557

[zhuang2653]

I see, thanks a lot, and can you elaborate what went wrong in my code, as I see you use operator() instead of operator<

[JLBorges]

> what went wrong in my code

word::operator< does not meet the requirement LessThanComparable
https://en.cppreference.com/w/cpp/named_req/LessThanComparable

Note that std::string::compare returns an integer value (negative, zero or positive).
When evaluated in a bool context, for two unequal words a and b, both a<b and b<a would yield true.

Rewrite as follows, and it should be ok:

       if(this->keyword.size() == right.keyword.size()){
            // return this->keyword.compare(right.keyword);
            return this->keyword < right.keyword ; // std::string is LessThanComparable
        } else {
            return this->keyword.size() > right.keyword.size();
        }

[seeplus]

You could also use std::multiset which allows multiple keys with the same value (size in this case).

[zhuang2653]

> what went wrong in my code

word::operator< does not meet the requirement LessThanComparable
https://en.cppreference.com/w/cpp/named_req/LessThanComparable

Note that std::string::compare returns an integer value (negative, zero or positive).
When evaluated in a bool context, for two unequal words a and b, both a<b and b<a would yield true.

thanks a lot, I get it now :).

[kigar64551]

You could also use std::multiset which allows multiple keys with the same value (size in this case).

If you compare strings only by length, then std::multiset would allow you to have multiple stings of the same length in the set, but it also would no longer remove exact "duplicate" strings.

So, I think that std::set with custom comparator (as suggested above) is the better choice here.

[ne555]

std::map< int, std::set<string> > dict;
dict[s.size()].insert(s);