c++ - C++ 中带有编译时检查的链表

Question

我正在尝试实现一个链表，其中包含编译时检查进出功能。这些能力(或上限)应提供是否可以进行有效链接的信息。因此，一个元素的 out 大写字母与下一个元素的 in 大写字母相交。如果可以找到有效的交叉点，则建立链接。请参阅提供的代码以在运行时进行此类检查。

虽然这在运行时很容易完成，但我不知道元/模板编程在编译时处理它的方向。我已经开始阅读 std::variant<>、std::visit<>、模板实例化、模板特化。

基本上，我了解元/模板编程，但只了解 C++11 之前的水平。请让我问这个开放性问题，元/模板编程如何以及是否可行。

提前致谢。

#include <assert.h>
#include <list>

enum class NodeType {
    Type1,
    Type2,
    Type3
};

class Caps {
public:
    NodeType type;
    int      minValue;
    int      maxValue;
};

bool intersect(const std::list<Caps>& in, const std::list<Caps>& out)
{
    for (auto i : in) {
        for (auto o : out) {
            if (i.type == o.type) {
                auto minValue = std::max(i.minValue, o.minValue);
                auto maxValue = std::min(i.maxValue, o.maxValue);
                if (maxValue >= minValue) {
                    return true;
                }
            }
        }
    }

    return false;
}

class Node
{
public:
    virtual bool link(Node& next) {
        if (intersect(this->outCaps(), next.inCaps())) {
            m_next = &next;
            return true;
        }
        return false;
    }

    virtual std::list<Caps> inCaps() { return {}; }
    virtual std::list<Caps> outCaps() { return {}; }

protected:
    Node* m_next = nullptr;
};

class DerivedNode1 : public Node
{
public:
    std::list<Caps> outCaps() override {
        return { { NodeType::Type1, 1, 10 },
                 { NodeType::Type2, 5, 20 } };
    }
};

class DerivedNode2 : public Node
{
    std::list<Caps> inCaps() override { return { { NodeType::Type1, 8, 12 } }; }
};

class DerivedNode3 : public Node
{
    std::list<Caps> inCaps() override { return { { NodeType::Type2, 1, 4 } }; }
};

class DerivedNode4 : public Node
{
    std::list<Caps> inCaps() override { return { { NodeType::Type3, 1, 99 } }; }
};

int main()
{
    DerivedNode1 node1;
    DerivedNode2 node2;
    DerivedNode3 node3;
    DerivedNode4 node4;

    assert(node1.link(node2));  // This shall link due to matching types and ranges
    assert(!node1.link(node3)); // This shall fail due to non-matching range for a specific type
    assert(!node1.link(node4)); // This shall fail due to non-matching types
}

Answer 1

以下是您可能想要的。如果您不喜欢 Link 类，Node::link2 可以重命名为 Node::link，否则 it needs to have a different name .

您可以根据自己的喜好使用 Node::link2(a, b) 或 a.link(b) 语法。前者不需要将单参数 link 方法注入(inject)派生类，因此可能更可取。后者需要更多的工作才能使深度推导起作用

// Wouldn't work because `DerivedNodeY::link` and `DerivedNodeX::link` are ambiguous;
class DerivedNodeX : public DerivedNodeY, Link<DerivedNodeX>
{
public:
    static constexpr std::array<Caps,1> inCaps() { ... }
    // but this makes it work:
    using Link<DerivedNodeX>::link;
};

如果没有 Link 类，派生节点看起来就像:

class DerivedNode : public Node
{
public:
    static constexpr std::array<Caps,1> inCaps() {
        return {{ { NodeType::Type3, 1, 99 } }};
    }
};

代码是 C++17，它用 gcc 和 clang 编译，但它使 MSVC(最高 19.22)崩溃并出现内部错误:(。感谢编写了一个不错的编译器测试用例!

#include <array>
#include <type_traits>

enum class NodeType {
    Type1,
    Type2,
    Type3
};

struct Caps {
    NodeType type;
    int      minValue;
    int      maxValue;
};

class Node
{
public:
    static constexpr std::array<Caps,0> inCaps() { return {}; }
    static constexpr std::array<Caps,0> outCaps() { return {}; }

    template <class InCaps, class OutCaps>
    static constexpr bool intersect(const InCaps &in, const OutCaps &out);

    template <class N1, class N2>
    static std::enable_if_t<
        std::is_base_of_v<Node, N1> &&
        std::is_base_of_v<Node, N2> &&
        intersect(N1::outCaps(), N2::inCaps()), void>
    link2(N1 &prev, N2 &next) {
        prev.m_next = &next;
    }

protected:
    Node* m_next = nullptr;
};

template <typename ThisNode>
class Link
{
public:
    template <class N2> void link(N2 &next) {
        Node::link2(*static_cast<ThisNode*>(this), next);
    }
};

template <class InCaps, class OutCaps>
constexpr bool Node::intersect(const InCaps &in, const OutCaps &out)
{
    for (auto i : in) {
        for (auto o : out) {
            if (i.type == o.type) {
                auto minValue = std::max(i.minValue, o.minValue);
                auto maxValue = std::min(i.maxValue, o.maxValue);
                if (maxValue >= minValue) {
                    return true;
                }
            }
        }
    }
    return false;
}

class DerivedNode1 : public Node, public Link<DerivedNode1>
{
public:
    static constexpr std::array<Caps,2> outCaps() {
        return {{ { NodeType::Type1, 1, 10 },
                  { NodeType::Type2, 5, 20 } }};
    }
};

class DerivedNode2 : public Node, public Link<DerivedNode2>
{
public:
    static constexpr std::array<Caps,1> inCaps() {
        return {{ { NodeType::Type1, 8, 12 } }};
    }
};

class DerivedNode3 : public Node, public Link<DerivedNode3>
{
public:
    static constexpr std::array<Caps,1> inCaps() {
        return {{ { NodeType::Type2, 1, 4 } }};
    }
};

class DerivedNode4 : public Node, public Link<DerivedNode4>
{
public:
    static constexpr std::array<Caps,1> inCaps() {
        return {{ { NodeType::Type3, 1, 99 } }};
    }
};

int main()
{
    DerivedNode1 node1;
    DerivedNode2 node2;
    DerivedNode3 node3;
    DerivedNode4 node4;

    Node::link2(node1, node2); // compiles
    node1.link(node2);
#if 0
    Node::link2(node1, node3); // fails to compile
    node1.link(node3);
    Node::link2(node1, node4); // fails to compile
    node1.link(node3);
#endif
}