从可变参数创建 Link 列表

Question

我想通过获取编译时给出的可变参数来创建一个 link 列表说明如下：

我有一个如下所示的节点：

template<typename T>
struct Node
{
    Node(const T& data, Node* next = nullptr ) : m_data(data),
                                                 m_next(next)
    {}
    
    T m_data;
    Node *m_next;
};

我有一个函数，它接受可变数量的参数（可变参数），如下所示，并且应该能够从所有参数和 return head*（起始指针）创建一个 link 列表创建的列表

template <class ... Ts>
constexpr Node* create(Ts && ... ts) {
    // should be able to create all nodes and return Head* for the given created list
    //return Head
}

主函数看起来像这样

int main()
{
    auto *k = create(1,2,3,4,5,6);
    auto *n = create();  // should handle no arguments case
    auto *l = create(9,10,11,22,4567,90);
    
    return 0;

}

Answer 1

不要把它弄得太复杂，只需使用 std::initializer_list。在这里使用可变参数会有点矫枉过正。

另外 Node 应该是列表的实现细节。所以创建一个模板 class List 这将是唯一使用 Node.

的模板

template<typename T>
struct Node
{
    T m_data;
    Node *m_next;
};

template<typename T>
class List
{
public:
    List(std::initializer_list<T> ini)
    {
        for (const T& x : ini) {
           push_back(x);
        }
    }

    void push_back(const T& x);
    ....

private:
   std::unique_ptr<Node> m_front;
   Node* m_back;
};

这种方法很糟糕，面试任务也很糟糕，但这里是：

template<typename T>
struct Node
{
    constexpr explicit Node(const T& x) : m_data{x}
    {}

    T m_data;
    std::unique_ptr<Node> m_next;
};

template<typename T>
using Node_t = Node<std::remove_reference_t<T>>;
template<typename T>
using NodePtr = std::unique_ptr<Node_t<T>>;

template<typename T>
constexpr NodePtr<T> create(T&& x)
{
    return std::make_unique<Node_t<T>>(std::forward<T>(x));
}

template <typename T1, typename ... Ts>
constexpr NodePtr<T1>
    create(T1&& x1, Ts && ...xi)
{
    auto r = create(std::forward<T1>(x1));
    r->m_next = create(std::forward<Ts>(xi)...);
    return r;
}

https://godbolt.org/z/bbo5Tc

Answer 2

这是完整的测试程序。 create 例程使用标准的尾递归和一些可变模板魔术。这使用 C++17 的 if constexpr，对于 C++14，您必须将 create 专门化为空参数列表 (return nullptr;).

Marek 的还包含关于 unique_ptr 和 std::initializer_list 的有效观点。

#include <iostream>

struct Node_t {
    Node_t(int v = 0, Node_t* n = nullptr): value(v), next(n) {}

    int value;
    Node_t* next;
};

constexpr Node_t* create() {
    return nullptr;
}

template <class Head, class... Tail>
constexpr Node_t* create(Head const& head, Tail const&... tail) {
    Node_t* result = new Node_t(head);
    if constexpr(sizeof...(tail) > 0) {
        result->next = create(tail...);
    }
    return result;
}

void printList(Node_t* n) {
     if (!n)
          return;
     std::cout << n->value;
     if (n->next) {
        std::cout << ", ";
        printList(n->next);
    }
}

int main() {
    Node_t* l = create(1,2,3);
    std::cout<< "List: "; printList(l);
    std::cout << std::endl;

    Node_t* l2 = create();
    std::cout<< "EmptyList: "; printList(l2);
}

从可变参数创建 Link 列表

Create Link List from variadic arguments

c++

variadic-templates

constexpr

c++17