在std::set中使用自定义函数对象

Question

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int order[26];
struct lexcmp
{
    bool operator()(const string &s1,const string &s2)
    {
        int i=0;
        int j=min(s1.size(),s2.size());
        while(1)
        {
            if(order[s1[i]-'a']<order[s2[i]-'a'])
            return true;
            if(order[s1[i]-'a']>order[s2[i]-'a'])
            return false;
            if(i==j-1)
            return false;
            i++;
        }
    }
};
int main()
{
        string s;
        cin>>s;
        for(int i=0;i<s.size();i++)
        {
            order[s[i]-'a']=i;
        }
        set<string,lexcmp> store;
        int m;
        cin>>m;
        while(m--)
        {
            string q;
            cin>>q;
            store.insert(q);
        }
        for(auto i=store.begin();i!=store.end();i++)
        {
            cout<<*i<<endl;
        }
    }
    return 0;
}

---

• 制作自定义函数对象时的问题 问题是，我有一种新的元素顺序（而不仅仅是 a-z）。//保存在排序数组中
• 我只想基于新顺序对给定字符串进行排序。
• 例如：顺序是：bacdefghijklmnopqrstuvwxyz 因此，如果字符串是ss，aa，bb， 新的排序将为bb，aa，ss。
• 代码运行良好，但是当字符串像“pas”“p”这样进行比较时，它会给我带来问题。 p应该在pas之前出现，但是它却在之后出现。
• 我应该对函数对象做哪些修改？

- Crosk Cool

---

例如：排序为：bacdefghijklmnopqrstuvwxyz。因此，如果字符串是ss、aa、bb，新的排序将是aa、bb、ss。为什么不是bb, aa, ss，而是aa, bb, ss？因为在排序中，我们首先比较字符串的第一个字符，然后再根据需要进行进一步比较。在这种情况下，b的顺序确实在a之前，但是由于我们首先比较了第一个字符，所以按照字母顺序，aa会排在bb之前。 - ildjarn

如果您比较相同的字符串，则可能存在未定义行为。在循环中的i++之前添加if (i == j) return 0;。 - HolyBlackCat

也许你的 lexcmp 函数还需要处理两个字符串相等的情况。 - nos

@HolyBlackCat 我曾经尝试过这种比较方式 if(i==j-1)，但它并不能解决问题。 - Crosk Cool

Answer 1

Here's one approach:

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <algorithm>
#include <numeric>
#include <array>
#include <string>
#include <locale>

struct lexcmp {
    lexcmp() { std::iota(order_.begin(), order_.end(), std::int_fast8_t{}); }
    explicit lexcmp(std::string const& order) {
        assert(order.size() == order_.size());

        for (std::size_t i{}; i != order_.size(); ++i) {
            char const order_letter = order[i];
            assert(std::isalpha(order_letter, std::locale::classic()));
            assert(std::islower(order_letter, std::locale::classic()));
            order_[i] = order_letter - 'a';
        }

        auto unique_order_letters = [this]{
            auto order = order_;
            std::sort(order.begin(), order.end());
            return order.end() - std::unique(order.begin(), order.end()) == 0;
        };
        assert(unique_order_letters());
    }

    bool operator ()(std::string const& a, std::string const& b) const {
        auto const a_len = a.size(), b_len = b.size();
        std::size_t i{};
        for (auto const len = std::min(a_len, b_len); i != len; ++i) {
            if (auto const diff = order_[a[i] - 'a'] - order_[b[i] - 'a']) {
                return diff < 0;
            }
        }
        return i == a_len && i != b_len;
    }

private:
    std::array<std::int_fast8_t, 26> order_;
};

在线演示

- ildjarn