基于不同类型而模板化的链表实现

Question

我已经实现了一个Node类，其代码如下：

template<unsigned int Size>
class Node
{
    private:
        Eigen::Matrix<float, Size, Size> m_matrix;

        Node<?> *m_previousNode;
        Node<?> *m_nextNode;
};

这个类有一个成员变量，其维度由模板参数设置。重要的是，它存储指向前一个和后一个节点的指针（这些指针的大小可以与自己的大小不同）。

现在，我有一定数量尺寸不同的这个类的节点，想将它们存储在一个Network类中。一开始它可能是三维的：

template<unsigned int S0, unsigned int S1, unsigned int S2>
class Network
{
    private:
        Node<S0> *m_firstNode;
        Node<S1> *m_secondNode;
        Node<S2> *m_thirdNode;
};

我希望以这种方式实例化它：

Network<10, 20, 5> network;

正如您所见，节点的数量和大小都是固定的；它们不能在之后进行修改。

我的问题是，我该如何存储指向前一个节点和后一个节点的指针（即上面代码中的 Node<?> *）。

我最初考虑将模板参数列表扩展为以下形式：

template<unsigned int PreviousSize, unsigned int Size, unsigned int NextSize>
class Node
private:
    Eigen::Matrix<float, Size, Size> m_matrix;

    Node<?, PreviousSize, Size> *m_previousNode;
    Node<Size, NextSize, ?> *m_nextNode;

但显然，我需要知道上一个节点的前驱节点的大小，这会导致同样的问题——我仍然无法填入 ?。

有什么解决方法吗？

- wuschelhase

---

我在这里冒险表示，您可能不想做您认为自己想做的事情。模板是编译时构造，不易于运行时检查。即使您可以构建某些带有标记联合类型的小装置或存储void指针，您仍然必须在运行时处理结果，这是不切实际的。 - Kerrek SB

这个 Size 参数控制的是哪种数据结构的大小？您是说大小因节点而异，在列表中并不是所有节点都是常量大小吗？ - John Kugelman

也许“链表”这个术语有些误导。我想建立一个具有固定节点数的列表，每个节点都有相同的大小（每个节点都可以有另一个大小值的常量）。节点的数量和它们的大小在编译时已知。 - wuschelhase

@wuschelhase：这听起来确实完全不同。您能否编辑您的问题并细化您的目标，然后我们都可以参与讨论。如果在编译时已知所有内容，那么使用编译时构造肯定是可行的。可能需要使用可变参数模板或使用cons列表来避免迷失方向。 - Matthieu M.

@MatthieuM.：好的，希望有人能在我更新问题后指点我正确的方向。到目前为止谢谢！ - wuschelhase

Answer 1

我可以看到几个涉及链表的解决方案，但它们都很丑陋；）

然而，考虑到列表的所有节点都属于一个共同实体“网络”，我认为这是我们的魔法卡。如果我们放弃列表的想法，而是针对网络中的“定位”节点，那么问题就变得容易得多！

template <typename Network, unsigned Index, unsigned Size>
class Node {
public:

private:
    Network* m_network;
    Eigen::Matrix<float, Size, Size> m_matrix;
}; // class Node

而且网络：

template <unsigned Size0, unsigned Size1, unsigned Size2>
class Network {
public:
    template <unsigned Index>
    auto access() -> decltype(m_nodes.get<Index>()) {
        return m_nodes.get<Index>();
    }

    template <unsigned Index>
    auto get() const -> decltype(m_nodes.get<Index>()) {
        return m_nodes.get<Index>();
    }

private:
    std::tuple< Node<Network, 0u, Size0>,
                Node<Network, 1u, Size1>,
                Node<Network, 2u, Size2>> m_nodes;
};

最后，迭代？

template <typename Network, unsigned Index, unsigned Size>
auto Node<Network, Index, Size>::prev() -> decltype(m_network->access<Index-1>()) {
    return m_network->access<Index-1>();
}

template <typename Network, unsigned Index, unsigned Size>
auto Node<Network, Index, Size>::next() -> decltype(m_network->access<Index+1>()) {
    return m_network->access<Index+1>();
}

嗯，除了我们在这里遇到了一个小鸡生蛋的问题...不过我们可以通过将Node的定义嵌套在Network类中来欺骗自己。我可能会这样做，但是，为什么不接受迭代应该始终从网络类开始呢？

最后，这就是我的建议：

template <unsigned Size>
class Node {
public:
    // ...
private:
    Eigen::Matrix<float, Size, Size> m_matrix;
};

template <unsigned Size>
std::ostream& operator<<(std::ostream& out, Node<Size> const&) {
    return out << "Node<" << Size << ">";
}

template <unsigned S, unsigned... Sizes>
class Network {
private:
    // Hack for gcc, using m_nodes in decltype requires that it's already been declared
    typedef std::tuple< Node<S>, Node<Sizes>... > Nodes;
    Nodes m_nodes;

public:

    static constexpr unsigned Size() { return sizeof...(Sizes) + 1; }

    template <unsigned Index>
    auto access() -> decltype(std::get<Index>(this->m_nodes)) {
        return std::get<Index>(this->m_nodes);
    }

    template <unsigned Index>
    auto get() const -> decltype(std::get<Index>(this->m_nodes)) {
        return std::get<Index>(this->m_nodes);
    }

}; // class Network

当然，一个Node不再知道它的位置，但你可以把它装进迭代器中：

template <typename Network, unsigned Index>
class NetworkIterator {
private:
    // Hack for gcc, using m_network in decltype requires that it's already been declared
    Network& m_network;

public:
    static_assert(Index < Network::Size(), "Index cannot exceed network size by more than one");

    NetworkIterator(Network& n): m_network(n) {}

    auto element() -> decltype(this->m_network.template access<Index>()) {
        return m_network.template access<Index>();
    }

    template <unsigned U = Index - 1>
    NetworkIterator<Network, U> prev() {
       return NetworkIterator<Network, U>(m_network);
    }

    template <unsigned U = Index + 1>
    NetworkIterator<Network, U> next() {
       return NetworkIterator<Network, U>(m_network);
    }
}; // class NetworkIterator

没错，它管用。

- Matthieu M.