c++ - 在 C++ 中创建自定义可比树状数据结构

Question

我有一个类型 struct Type_Specifier我想代表一个不可变的树状结构，我可以比较。我有以下代码来说明我想要什么:

#include <vector>

struct Parameter_Specifier;
struct Type_Specifier
{
    explicit Type_Specifier(void* tag = nullptr, std::vector<Parameter_Specifier> parameters = {})
        : tag(tag), parameters(parameters) { }

    Type_Specifier(const Type_Specifier&) = default;
    Type_Specifier(Type_Specifier&&) = default;
    Type_Specifier& operator=(const Type_Specifier&) = default;
    Type_Specifier& operator=(Type_Specifier&&) = default;
    ~Type_Specifier() = default;

private:
    // Points to an arbitray memory location (whose lifetime is not managed by this type)
    void* tag;
    std::vector<Parameter_Specifier> parameters;

public:
    static bool operator ==(const Type_Specifier& left, const Type_Specifier& right)
    {
        if (left.tag != right.tag)
            return false;
        else if (left.parameters.size() != right.parameters.size())
            return false;
        else for (std::size_t i = 0; i < left.parameters.size(); i++)
        {
            if (!(left.parameters[i] == right.parameters[i]))
                return false;
        }

        return true;
    }

    static bool operator <(const Type_Specifier& left, const Type_Specifier& right)
    {
        if (left.tag < right.tag)
            return true;
        else if (left.parameters.size() < right.parameters.size())
            return true;
        else if (left.parameters.size() > right.parameters.size())
            return false;
        else for (std::size_t i = 0; i < left.parameters.size(); i++)
        {
            if (left.parameters[i] < right.parameters[i])
                return true;
            else if (right.parameters[i] < left.parameters[i])
                return false;
        }

        return false; // left == right
    }   
};

struct Parameter_Specifier
{
    explicit Parameter_Specifier(Type_Specifier type = Type_Specifier(), std::vector<char> value = {})
        : type(type), value(value) { }

    Parameter_Specifier(const Parameter_Specifier&) = default;
    Parameter_Specifier(Parameter_Specifier&&) = default;
    Parameter_Specifier& operator=(const Parameter_Specifier&) = default;
    Parameter_Specifier& operator=(Parameter_Specifier&&) = default;
    ~Parameter_Specifier() = default;

private:
    Type_Specifier type;
    // Arbitrary data (not a 'string' or sequence of 'characters')
    std::vector<char> value;

public:
    static bool operator ==(const Parameter_Specifier& left, const Parameter_Specifier& right)
    {
        if (!(left.type == right.type))
            return false;
        else if (left.value.size() != right.value.size())
            return false;
        else for (std::size_t i = 0; i < left.value.size(); i++)
        {
            if (left.value[i] != right.value[i])
                return false;
        }

        return true; // left == right
    }

    static bool operator <(const Parameter_Specifier& left, const Parameter_Specifier& right)
    {
        if (left.type < right.type)
            return true;
        else if (left.value.size() < right.value.size())
            return true;
        else if (left.value.size() > right.value.size())
            return false;
        else for (std::size_t i = 0; i < left.value.size(); i++)
        {
            if (left.value[i] < right.value[i])
                return true;
            else if (left.value[i] > right.value[i])
                return false;
        }

        return false; // left == right
    }
};

但是它当然不会编译，可能是由于 struct Parameter_Specifier不完整，运算符“<”和“==”未定义。

我的问题是:我如何修改以上类型以使其正常编译和工作？ (并且高效？)

注意事项:

• 此类型的目的是用于双向映射结构，以便能够在 struct Type_Specifier 之间进行映射。和 std::size_t (即它需要既是键类型又是值类型)
• 我将根据我对“==”和“>”的定义来定义其他比较运算符“!=”、“>”、“>=”和“<=”，为简洁起见，我在这里省略了它们
• 我很确定 a == b相当于!(a < b) && !(b < a)
• 比较的顺序并不真正相关，看起来它是一个严格的弱顺序关系
• 我想要 Type_Specifier键入以遵循 RAII 习语
• Paramater_Specifier类型仅用于 Type_Specifier 的 child 别处
• 我只想使用C++标准库

我正在考虑制作 Type_Specifier::parameters一个std::vector<Parameter_Specifier*>但是我将不得不在 Type_Specifier 中手动管理分配，这会导致明显的问题，如 Parameter_Specifier那里是不完整的。

Answer 1

关系运算符有问题。

1) operator==() ，您有两种选择:(a) 类/结构的方法，带有 一个 参数(左侧参数 *this 是隐式的)，不能是 static ，或 (b) 带有两个参数的外部函数(通常为 friend )。您混合了这两种选择并制作了方法 static .我强烈建议备选方案 (b):外部功能。所以(考虑到 operator==() 有一个 std::vector ) operator==()对于 Type_Specifier可能是

friend bool operator== (const Type_Specifier & left,
                        const Type_Specifier & right)
 {
   return           ( left.tag == right.tag )
          && ( left.parameters == right.parameters );
 }

对于 Parameter_Specifier可能是

friend bool operator== (const Parameter_Specifier & left,
                        const Parameter_Specifier & right)
 {
   return     ( left.type == right.type )
          && ( left.value == right.value );
 }

2) operator<() 同样的事情.此外，如果“left.tag < rigth.tag”是false ，我认为你应该验证这不是 true那left.tag > right.tag .我对 Type_Specifier 的建议(但行为不同；谨慎)是

friend bool operator< (const Type_Specifier & left,
                       const Type_Specifier & right)
 {
   return    ( left.tag < right.tag )
          || (    ( left.tag == right.tag )
               && ( left.parameters < right.parameters ) );
 }  

对于 Parameter_Specifier ，我的建议(具有不同的行为；谨慎)是

friend bool operator< (const Parameter_Specifier & left,
                       const Parameter_Specifier & right)
 {
   return    ( left.type < right.type )
          || (    (left.type == right.type )
               && (left.value < right.value ) );
 }

3) 有 operator==()和 operator<()其他关系运算符很简单。对于 Type_Specifier

friend bool operator!= (const Type_Specifier & left,
                        const Type_Specifier & right)
 { return ! (left == right); }

friend bool operator> (const Type_Specifier & left,
                       const Type_Specifier & right)
 { return (right < left); }

friend bool operator<= (const Type_Specifier & left,
                        const Type_Specifier & right)
 { return ! (right < left); }

friend bool operator>= (const Type_Specifier & left,
                        const Type_Specifier & right)
 { return ! (left < right); }

对于 Parameter_Specifier ...好吧...改变Type_Specifier与 Parameter_Specifier .

P.s.:抱歉我的英语不好。