Node<T>* head;
,当我插入一个节点时,其中一行代码为head = new Node<T>(data);
。现在我需要使用智能指针,但我不确定如何修改以使用智能指针。成员变量是否应更改为
shared_ptr<Node<T>> head;
,另一行代码会更改为head = shared_ptr<Node<T>>( new <Node<T>>(data) );
?Node<T>* head;
,当我插入一个节点时,其中一行代码为head = new Node<T>(data);
。shared_ptr<Node<T>> head;
,另一行代码会更改为head = shared_ptr<Node<T>>( new <Node<T>>(data) );
?关于链表,你不需要使用智能指针,因为这个说法没有意义。低级数据结构不需要使用智能指针,而高级程序逻辑才需要使用智能指针。
就低级数据结构而言,你可以使用C++标准库中的标准容器类,比如std::list
[*],它可以解决所有内存管理问题,而且不需要在内部使用任何智能指针。
如果你真的需要自己高度专业化/优化的自定义容器类,因为整个C++标准库都不适合你的要求,你需要一个替代std::list
、std::vector
、std::unordered_map
等经过优化、测试、文档化和安全的容器——我非常怀疑这种情况存在!——那么你无论如何都必须手动管理内存,因为这种专门的类的目的几乎肯定是需要像内存池、写时复制甚至垃圾回收等技术,所有这些都与典型的智能指针的简单删除逻辑相冲突。
用Herb Sutter的话来说:
永远不要使用拥有原始指针和删除(delete),除非在实现自己的低级数据结构时,这是少数情况(即使如此,也要将其封装在类边界内)。Herb Sutter's and Bjarne Stroustrup's C++ Core Guidelines中也表达了类似的观点:无法通过将所有拥有指针转换为unique_ptrs和shared_ptrs来解决这个问题(在规模上),部分原因是我们需要/使用拥有"原始指针"以及简单指针来实现我们的基本资源句柄。例如,常见的vector实现具有一个拥有指针和两个非拥有指针。使用原始指针编写C++链表类可以是有用的学术练习。使用智能指针编写C++链表类则是毫无意义的学术练习。在生产代码中使用这两个自制工具几乎总是错误的。std::vector
,因为由于缓存局部性,这通常是更好的选择。
T*
。是否需要delete
取决于容器的实现。我列举的一些高级技术可以在没有显式delete
的情况下工作。然而,考虑到std::list
,一个简单的链表不需要高级技术或任何自定义类。 - Christian Hacklunique_ptr
--你通常几乎不会失去任何性能,并获得很多安全性。 - davidhigh基本上有两种方法来设置智能指针增强列表:
Using std::unique_ptr
:
template<typename T>
struct Node
{
Node* _prev;
std::unique_ptr<Node> _next;
T data;
};
std::unique_ptr<Node<T> > root; //inside list
That would be my first choice. The unique-pointer _next
takes care there are no memory leaks, whereas _prev
is an observing pointer. However, copy constructor and such things -- in case you need them -- need to be defined and implemented by hand.
Using shared_ptr
:
template<typename T>
struct Node
{
std::weak_ptr<Node> _prev; //or as well Node*
std::shared_ptr<Node> _next;
T data;
};
std::shared_ptr<Node<T> > root; //inside list
This is alternative is copyable by design and adds further safety because of the weak_ptr, see below. It is less performant than the unique_ptr when it comes to structural changes of the list, such as insertions and removals, e.g. due to thread safety in shared_ptr's control block.
Yet, traversing the list, i.e. dereferencing the pointers, should be as performant as for the unique_ptr.
_prev
指针只是一个观察指针:它的任务不是保持前面的节点存活,而是提供一个链接来访问它们。为此,通常使用Node *
即可(--注意:观察指针表示您从不对指针执行与内存相关的操作,如new
、delete
)。std::weak_ptr
,这可以防止发生类似的事情。std::shared_ptr<Node<T> > n;
{
list<T> li;
//fill the list
n = li.root->next->next; //let's say that works for this example
}
n->_prev; //dangling pointer, the previous list does not exists anymore
weak_ptr
,您可以使用lock()
方法检查_prev
是否仍然有效。Node
析构函数中实现,但这将破坏unique-ptr的优势。因此,最好实现一个自定义的unique-ptr——假设它是一棵树形结构,并从下往上删除。(但这只是一些快速建议)。无论如何,这整个问题都不能成为使用原始指针而不是智能指针的理由...只是提一下。 - davidhigh#include <iostream>
#include <list>
#include <memory>
using namespace std;
int main()
{
// Unique ownership.
unique_ptr<int> int_ptr = make_unique<int>(5);
{
// list of uniquely owned integers.
list<unique_ptr<int>> list_unique_integers;
// Transfer of ownership from my parent stack frame to the
// unique_ptr list.
list_unique_integers.push_back(move(int_ptr));
} // list is destroyed and the integers it owns.
// Accessing the integer here is not a good idea.
// cout << *int_ptr << endl;
// You can make a new one though.
int_ptr.reset(new int(6));
// Shared ownership.
// Create a pointer we intend to share.
shared_ptr<int> a_shared_int = make_shared<int>(5);
{
// A list that shares ownership of integers with anyone that has
// copied the shared pointer.
list<shared_ptr<int>> list_shared_integers;
list_shared_integers.push_back(a_shared_int);
// Editing and reading obviously works.
const shared_ptr<int> a_ref_to_int = list_shared_integers.back();
(*a_ref_to_int)++;
cout << *a_ref_to_int << endl;
} // list_shared_integers goes out of scope, but the integer is not as a
// "reference" to it still exists.
// a_shared_int is still accessible.
(*a_shared_int)++;
cout << (*a_shared_int) << endl;
} // now the integer is deallocated because the shared_ptr goes
// out of scope.
delete node;
。template<class T>
struct LinkedList
{
Node<T> *head;
};
// The very start of a LinkedList with shared ownership. In all your access
// methods, etc... you will be returning copies of the appropriate pointer,
// therefore creating another reference to the underlying data.
template<class T>
struct LinkedList<std::shared_ptr<T>>
{
shared_ptr<Node<T>> head;
};
现在你开始实现自己的STL!正如在评论中提到的那样,您已经看到了这种方法可能存在问题。如果节点具有shared_ptr next,则会导致调用该共享节点的析构函数,该析构函数将调用下一个共享节点的析构函数,依此类推(由于递归而导致堆栈溢出是可能的)。因此,这就是为什么我不太喜欢这种方法。
struct Node{
int val;
unique_ptr<Node> next;
Node(int v, unique_ptr<Node> n) : val(v), next(std::move(n)) {}
};
unique_ptr<Node> reverseList(unique_ptr<Node> head) {
unique_ptr<Node> prev{nullptr};
unique_ptr<Node> current = std::move(head);
while (current) {
unique_ptr<Node> temp = std::move(current->next);
current->next = std::move(prev);
prev = std::move(current);
current = std::move(temp);
}
return prev;
}
void testReverseList() {
auto n1 = make_unique<Node>(1, nullptr);
auto n2 = make_unique<Node>(2, std::move(n1));
auto n3 = make_unique<Node>(3, std::move(n2));
auto n4 = make_unique<Node>(4, std::move(n3));
auto n5 = make_unique<Node>(5, std::move(n4));
Node* nodePtr = n5.get();
cout << "before: " << endl;
while(nodePtr) {
cout << nodePtr->val << endl;
nodePtr = nodePtr->next.get();
}
auto result = reverseList(std::move(n5));
cout << "after: " << endl;
nodePtr = result.get();
while(nodePtr) {
cout << nodePtr->val << endl;
nodePtr = nodePtr->next.get();
}
}
template<typename T> struct Node
{
T data;
shared_ptr<Node<T>> next;
};
shared_ptr<Node<int>> head(new Node<int>);
或者
auto head = make_shared<Node>(Node{ 1,nullptr });
make_shared
而不是调用new
,因为它提供了new
调用所不具备的异常安全性。 - UpAndAdam
shared_ptr
部分更改为unique_ptr
吗? - Mark