重载 C++ 集插入

Question

是否可以重载字符串集中的比较运算符，使其将编辑距离 <= 1 的两个元素定义为相同？

这是我失败的尝试：

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

using namespace std;

int min(int x, int y, int z) 
{
   return min(min(x, y), z);
}

int getEditDist(string& str1, string& str2, int m, int n)
{
    if (str1[m-1] == str2[n-1])
        return getEditDist(str1, str2, m-1, n-1);
    return 1 + min ( getEditDist(str1,  str2, m, n-1),
                     getEditDist(str1,  str2, m-1, n),
                     getEditDist(str1,  str2, m-1, n-1)
        );
}


class editDist
{
public:
    bool operator () (string& str1, string& str2)
        {
            return(getEditDist(str1, str2, str1.length(), str2.length()) <= 1);
        }
};


int main(int argc, char* argv[])
{

    string id1 = "AAA";
    string id2 = "BBB";
    string id3 = "BAB";
    set<string,editDist> my_set;
    //set<string> my_set;
    set<string,editDist>::const_iterator itr;
    //set<string>::const_iterator itr;
    my_set.insert(id1);
    my_set.insert(id2);
    my_set.insert(id3);
    for(itr = my_set.begin();itr != my_set.end();++itr) cout<<*itr<<endl;
    return(0);
}

我什至不确定它的编码是否正确，因为它无法编译。

Answer 1

编译失败有两个原因：

你递归调用你的 min 函数但是参数太少
getEditDist 和 operator() 的参数必须是常量

除此之外，您在 getEditDist 中的递归将永远不会完成。

即这将编译：

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

int min3(int x, int y, int z) 
{
   return std::min(std::min(x, y), z);
   // Or just use `std::min({x, y, z})` if you have C++11 available
}

int getEditDist(const std::string& str1, const std::string& str2, int m, int n)
{
    if (str1[m-1] == str2[n-1])
        return getEditDist(str1, str2, m-1, n-1);

    return 1 + min3(
        getEditDist(str1,  str2, m, n-1),
        getEditDist(str1,  str2, m-1, n),
        getEditDist(str1,  str2, m-1, n-1));
}

class editDist
{
public:
    bool operator () (const std::string& str1, const std::string& str2)
    {
        return(getEditDist(str1, str2, str1.length(), str2.length()) <= 1);
    }
};

int main(int argc, char* argv[])
{

    std::string id1 = "AAA";
    std::string id2 = "BBB";
    std::string id3 = "BAB";
    std::set<std::string, editDist> my_set;
    //set<string> my_set;
    std::set<std::string, editDist>::const_iterator itr;
    //set<string>::const_iterator itr;
    my_set.insert(id1);
    my_set.insert(id2);
    my_set.insert(id3);
    for(itr = my_set.begin(); itr != my_set.end(); ++itr)
        std::cout << *itr<< std::endl;

    return 0;
}

但是当你运行它时它会导致堆栈溢出。你将需要更改 getEditDist 使其停止。

Answer 2

TLDR：不，不可能做你想做的事。

详情：

你可以定义一个比较器 d(a,b) ≤ 1 ⇒ a ∼ b;
唯一有效的比较器，是∀(a,b)，a∼b，没什么用；
然而，not 可以定义一个比较器 d(a,b) ≤ 1 ⇔ a ∼ b 这正是您想要的.

比较器定义了字符串的排序和 classes 的等价性。如果您希望任何两个编辑距离 ≤ 1 的元素处于相同的等价 class，这意味着任何编辑距离 ≤ 2 的元素也处于相同的等价 class。我们可以继续对任何可能的编辑距离进行推理，因此所有字符串必须处于相同的 class 等价：

 struct always_equal_less {
   bool operator()(std::string const& x, std::string const& y) const {
     return false;
   }
 };

更正式的解释

std:set<Key,Compare,Allocator> must follow the Compare概念的Compare参数，即它必须定义严格的弱排序关系。它必须具有以下属性：

传递性，(a≺b∧b≺c)⇒a≺c;
非自反性，¬(a ≺ a);
不对称，(a ≺ b) ⇒ ¬(b ≺ a);
不可比传递性(a∼b)∧(b∼c)⇒(a∼c).

我用 a∼b 表示 ¬(a ≺ b) ∧ ¬(b ≺ a)。

假设我们有这样一个关系≺，它有额外的属性，对于编辑距离小于或等于1的任何两个元素都等于：d(a,b)≤1⇒a ∼ b.

我们可以证明唯一正确的关系是比较所有字符串是否相等：∀(a,b), a∼ b:

让我们取编辑距离为2的两个元素，d(a,b) = 2。我们可以找到第三个元素c，例如：d(a,c) = 1和d(c ,b) = 1。我们有 a∼c 和 c∼b。不可比性的传递性给出：a∼b。这意味着任何两个编辑距离为 2 的元素也被认为是相等的：∀(a,b), d(a,b) = 2, a ~ b.
你可以继续推理d(x,y)=3, d(x,y)=4。这表明任何给定的字符串对必须比较相等。

我们得到（没用的）关系∀(a,b), a ~ b.

因此无法定义 d(a,b) ≤ 1 ⇔ a ∼ b 的比较器。

重载 C++ 集插入

Overload C++ set insert

c++

overloading

operators

set

更正式的解释