在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之间进行映射(也就是说，它需要是一个键类型和一个值类型)。
• 我将根据我对'>=‘>和'<=’的定义定义其他比较运算符'!=‘’，‘’based =‘’，'==‘’>，为了简洁起见，我在这里省略了它们
• 我确信a == b等同于!(a < b) && !(b < a)
• 比较的顺序并不是真的相关，因为它看起来是一个严格的弱序关系。
• 我想让Type_Specifier类型的人跟随RAII的成语
• Paramater_Specifier类型仅用于Type_Specifier的子级，而不用于其他任何地方。
• 我只想使用C++标准库

我正在考虑让Type_Specifier::parameters成为一个std::vector<Parameter_Specifier*>，但是接下来我必须手动管理Type_Specifier中的分配，这将导致明显的问题，因为Parameter_Specifier是不完整的。

Answer 1

关系运算符有问题。

对于operator==()，有两种选择：(a)一个类/结构的方法，它只有一个参数(左参数*this是隐式的)，不能是static，或者(b)具有两个参数的外部函数(通常是friend)。您混合了这两种方法，并使方法static。我强烈建议备选案文(b)：外部职能。因此(考虑到有一个operator==() for std::vector)，Type_Specifier的operator==()可能是

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。

对不起，我的英语很差。