您应该在C ++中将智能指针用于低级数据结构，例如链表吗？用例可以是访谈设置

Question

我已经实现了一个模板化的链表，该链表在内部使用唯一的指针。首先，我创建一个ListNode结构，该结构保存指向下一个节点和数据的指针。最后，它还有一个方便的功能将其转换为字符串（稍后打印）：

template < typename T>
struct ListNode;

template<typename T >
using ListNodePtr = std::unique_ptr<ListNode<T>>;

template < typename T>
struct ListNode
{
    ListNode(T data) : data(data) {}
    T data;
    ListNodePtr<T> next = nullptr;

    std::string str()
    {
        std::string output;
        ListNode<T>* curr = this;
        while (curr)
        {
            output += std::to_string(curr->data) + " ";
            curr = curr->next.get();
        }
        return output;
    }
};

链表本身存储指向节点的智能指针，该节点包含所有其他节点。已经实现了几种具有基本列表功能的方法，例如插入元素，在位置n的删除或反向列表。

template <typename T>
    class LinkedList

{
public:
    LinkedList() = delete;
    LinkedList(const std::vector<T>& data)
    {
        createListFromVector(data);
}

void createListFromVector(const std::vector<T>& data)
{
    if (data.empty())
    {
        return;
    }

    ListNodePtr<T> head = nullptr;
    ListNode<T>* curr = nullptr;
    for (const auto& item : data)
    {
        if (!head)
        {
            head = std::make_unique<ListNode<T>>(item);
            curr = head.get();
            continue;
        }

        curr->next = std::make_unique<ListNode<T>>(item);
        curr = curr->next.get();
    }

    m_list = std::move(head);
};

// insert node at head
void insertNode(T data)
{
    ListNodePtr<T> newNode = std::make_unique<ListNode<T>>(data);
    newNode->next = std::move(m_list);
    m_list = std::move(newNode);
}

// delete the nth node
void deleteNode(int pos)
{
    if (pos < 1) { return; }

    ListNode<T>* curr = m_list.get();
    while ((pos-1) && curr)
    {
        curr = curr->next.get();
        --pos;
    }

    if (curr)
    {
        ListNodePtr<T> next = std::move(curr->next->next);
        curr->next = std::move(next);
    }
}

// reverse the list iteratively
void reverse()
{
    ListNodePtr<T> prev = nullptr;
    ListNodePtr<T> curr = std::move(m_list);
    ListNodePtr<T> next = nullptr;

    while (curr)
    {
        next = std::move(curr->next);
        curr->next = std::move(prev);
        prev = std::move(curr);
        curr = std::move(next);
    }

    m_list = std::move(prev);
}

void print() { std::cout << str() << std::endl; };
std::string str() { return getHead()->str(); }
private:
    ListNode<T>* getHead() const { return m_list.get(); };
    std::unique_ptr<ListNode<T>> m_list = nullptr;
};

如您所见，我以这种方式实现了一些基本功能，但是，与例如在Python中的方式相比，这似乎太复杂了。如果不限于unique_ptr。

，事情将变得如此简单。

例如，假设我要创建一个方法：toOddThenEven会重新排列列表中的元素-首先是所有奇数位置，然后是所有偶数位置：1，7，2，14，5，32变为1、2 ，5，7，14，32。第一个索引被认为是1，因此是odd。

通常，通过制作赔率首部，偶数首部的副本，然后再创建两个指针以在列表中向前移动，可以轻松完成此操作。最后，您可以拥有赔率列表：1-> 2-> 5和偶数列表：7-> 14-> 32，可以通过设置next 最后一个奇数索引元素的指针指向偶数头，并返回几率的头。

Python示例：

def toOddThenEven(node):
if not node:
    return None

headO = node
headE = headO.next 
curr = headO
nxt = headE

while(nxt and nxt.next):
    # skip adjancent element for both curr and nxt
    curr.next = curr.next.next
    nxt.next = nxt.next.next

    # move forward
    nxt = curr.next.next
    curr = curr.next

# concatenate odds list and evens list
curr.next = headE
return headO

现在，可能有更好的方法来实现此目的，但是，尽管如此，您可能仍需要像上面所做的那样制作一些临时副本，以使其在不爆炸的情况下工作。

因此，C ++解决方案是使用shared_ptr而不是unique_ptr。但是，在这种情况下，我们将为每个指针使用2倍的内存，从而使LinkedList数据结构不是最优的-与仅使用带有new / delete的原始指针的简单实现相比和RAII，这样我们数据结构的用户就不会直接管理它的内存。

因此，在设计这样的数据结构的情况下-尤其是时间短时（例如在面试过程中，或向其他开发人员演示的目的），在这种情况下，似乎[是更好的选择。如果您不关心额外的性能影响，请选择shared_ptr。任何想法，将不胜感激。谢谢。

Answer 1

好，所以我实际上可以自己回答这个问题，我只是希望其他人可以分享他们对该主题的看法。

通常，最好在面试过程中保持简单。另外，低级数据结构通常是在不使用智能指针的情况下实现的，因为即使C ++标准库也没有使用它们，例如std :: list。

此外，面试来源/网站（例如Leetcode）也使用原始指针提供了给定的代码段。

此外，我还要提及的是，通常在进行开发时会使用智能指针。因为很少需要设计自己的低级数据结构。

[如果出现提示，我将继续给出一些智能指针的示例，并将它们进行对比，即：

unique_ptr

vs shared_ptr vs weak_ptr。最后，如果他们要我使用智能指针，那么起初我可能会选择

shared_ptr

，因为它会更简单。也许我还会用using子句定义一个较短的名称。