c++ 具有unique_ptr的单链表

bzzcjhmw 于 2022-11-27 发布在其他

关注(0)|答案(1)|浏览(246)

我正在尝试使用智能指针（std::unique_ptr）来创建一个单向链表。下面是一个带有原始指针的单向链表的例子。

struct Node {
  int data;
  Node *next = nullptr;
  Node(int data) : data{data}, next{nullptr} {}
  ~Node() { std::cout << "Destroy node with data: " << data << '\n'; }
};

void print_list(Node *head) {
  while (head != nullptr) {
    cout << head->data << " --> ";
    head = head->next;
  }
  cout << "nullptr" << std::endl;
}

void insert(Node *&head, int data) {
  Node *new_node = new Node{data};
  new_node->next = head;
  head = new_node;
}

int main(int argc, char *argv[]) {
  Node *head = nullptr;
  for (int i = 0; i < 5; ++i) {
    insert(head, i);
  }
  print_list(head);
  return 0;
}

输出为：

4 --> 3 --> 2 --> 1 --> 0 --> nullptr

显然上面的代码中存在内存泄漏（没有调用析构函数）。现在我想用智能指针来实现同样的事情：

struct Node {
  int data = 0;
  std::unique_ptr<Node> next;
  Node(int data) : data{data}, next{nullptr} {}
  ~Node() { std::cout << "Destroy node with data: " << data << '\n'; }
};

void print_list(std::unique_ptr<Node> head) {
  while (head != nullptr) {
    std::cout << head->data << " --> ";
    head = std::move(head->next);
  }
  std::cout << "nullptr" << std::endl;
}

void insert(std::unique_ptr<Node> &&head, int data) {
  std::unique_ptr<Node> new_node{std::make_unique<Node>(data)};
  new_node->next = std::move(head);
  head = std::move(new_node);
}

// g++ -std=c++17 -Wall 2_1.cpp && ./a.out
int main(int argc, char *argv[]) {
  std::unique_ptr<Node> head{nullptr};
  for (int i = 0; i < 5; ++i) {
    insert(std::move(head), i);
  }
  print_list(std::move(head));
  return 0;
}

输出为：

4 --> Destroy node with data: 4
3 --> Destroy node with data: 3
2 --> Destroy node with data: 2
1 --> Destroy node with data: 1
0 --> Destroy node with data: 0
nullptr

我们可以观察到new_node的生命周期在insert()返回时结束，我想知道是否可以使用智能指针实现单向链表，并保留上面的函数接口。

c++

来源：https://stackoverflow.com/questions/74541783/singly-linked-list-with-unique-ptr

1条答案

按热度按时间

xmakbtuz1#

首先，您的print_list实现存在问题（仅适用于unique_ptr的两个版本）。对于print_list，每次将head分配给不同的uniq_ptr时，实际上是在释放head中唯一的Node，这是不希望的。相反，在print_list中，您应该首先创建一个指向head的临时指针，然后只对临时指针进行迭代。
现在到了你的unique_ptr版本，你不需要把unique_ptr作为右值引用传递，你也可以把它作为左值引用传递。

void print_list(const std::unique_ptr<Node>& head);
void insert(std::unique_ptr<Node> &head, int data);

这允许您在不使用main中的std::move的情况下调用它们。
现在来看看定义。对于插入，你需要先用给定的值创建一个新的Node，然后把旧的head赋给新节点的next，并把新节点设为新的head：

void insert(std::unique_ptr<Node> &head, int data)
{
    // Use `auto` to avoid typing `....<Node>` twice
    auto new_node = std::make_unique<Node>(data);
    new_node->next = std::move(head);
    head = std::move(new_node);
}

或者，您也可以在Node的构造函数中再添加一个参数：

Node(int data, std::unique_ptr<Node>&& next = nullptr) 
: data{data}, next{std::move(next)}
{}

现在，您可以简单地创建new_node，如下所示：

void insert(std::unique_ptr<Node> &head, int data)
{
    // No need to assign `Node::next` separately
    auto new_node = std::make_unique<Node>(data, std::move(head));
    head = std::move(new_node);
}

或者直接将新节点分配给head：

void insert(std::unique_ptr<Node> &head, int data)
{
    head = std::make_unique<Node>(data, std::move(head));
}

对于print_list，我们应该首先创建一个指向head底层对象的临时指针，然后通过将临时指针赋给下一个对象的底层对象来迭代列表：

void print_list(const std::unique_ptr<Node>& head)
{
    // Create a pointing to the underlying object
    // You can use `.get()` to get the underlying pointer
    auto current = head.get();

    // No need to explicit compare pointer types to `nullptr`
    while (current) {
        std::cout << current->data << " --> ";
        // Make `current` point to the next underlying object
        current = current->next.get();
    }
    std::cout << "nullptr" << std::endl;
}

现在，您的main将如下所示：

int main(int, char *[]) {
    std::unique_ptr<Node> head;
    for (int i = 0; i < 5; ++i) {
        insert(head, i);
    }
    print_list(head);
    return 0;
}

Demo

赞(0）回复(0）举报 2022-11-27

我来回答

c++ 具有unique_ptr的单链表

1条答案

相关问题

热门标签

最新问答