为什么链表使用指针而不是在节点内部存储节点
Why do linked lists use pointers instead of storing nodes inside of nodes
我之前在 Java 中广泛使用过链表，但我对 C++ 还很陌生。我在项目中使用的这个节点class很好
class Node
{
public:
Node(int data);
int m_data;
Node *m_next;
};
但我有一个问题没有得到很好的回答。为什么需要使用
Node *m_next;
指向列表中的下一个节点而不是
Node m_next;
我明白用指针版比较好；我不打算争论事实，但我不知道为什么它更好。关于指针如何更好地分配内存，我得到了一个不太明确的答案，我想知道这里是否有人可以帮助我更好地理解这一点。
后者 (Node m_next) 必须 包含 节点。它不会指向它。然后就没有元素链接了。
你使用指针，否则你的代码：
class Node
{
//etc
Node m_next; //non-pointer
};
…不会编译，因为编译器无法计算Node的大小。这是因为它取决于自身——这意味着编译器无法决定它会消耗多少内存。
这不仅更好，而且是唯一可行的方法。
如果您在自身内部存储了一个 Node 对象，那么 sizeof(Node) 会是什么？它将是 sizeof(int) + sizeof(Node)，等于 sizeof(int) + (sizeof(int) + sizeof(Node))，等于 sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node)))，等等直到无穷大。
不可能存在这样的对象。 不可能.
在Java
Node m_node
存储指向另一个节点的指针。你别无选择。在 C++ 中
Node *m_node
意思是一样的。不同之处在于，在 C++ 中，您实际上可以存储对象而不是指向它的指针。这就是为什么你必须说你想要一个指针。在 C++ 中：
Node m_node
意味着将节点存储在此处（这显然不适用于列表 - 您最终会得到一个递归定义的结构）。
C++ 不是 Java。当你写
Node m_next;
在Java，也就是写
一样
Node* m_next;
在 C++ 中。在 Java 中，指针是隐式的，在 C++ 中是显式的。如果你写
Node m_next;
在 C++ 中，您将 Node 的实例放在您正在定义的对象中。它始终存在，不能省略，不能用 new 分配，也不能删除。这种效果在Java中是不可能实现的，它与Java用同样的语法所做的完全不同。
附带说明一下，如果 class 或结构的第一个成员是下一个指针（因此没有虚函数或 class 的任何其他功能，这意味着 next 不是' t class 或结构的第一个成员），那么你可以使用 "base" class 或仅带有下一个指针的结构，并使用通用代码进行基本的链表操作，如追加，之前插入，从前面检索，...。这是因为 C/C++ 保证 class 或结构的第一个成员的地址与 class 或结构的地址相同。基本节点 class 或结构将只有一个 next 指针供基本链表函数使用，然后根据需要使用类型转换在基本节点类型和 "derived" 节点类型之间进行转换。旁注 - 在 C++ 中，如果基节点 class 只有一个下一个指针，那么我假设派生的 classes 不能有虚函数。
Why is it better to use pointers in a linked list?
原因是当您创建一个 Node 对象时，编译器必须为该对象分配内存，并为此计算对象的大小。
编译器知道指向任何类型的指针的大小，因此可以计算对象的自引用指针大小。
如果使用 Node m_node，那么编译器不知道 Node 的大小，它将卡在 无限递归 计算 sizeof(Node)。永远记住：a class cannot contain a member of its own type。
概览
在 C++ 中有两种引用和分配对象的方法，而在 Java 中只有一种方法。
为了解释这一点，下面的图表展示了对象是如何存储在内存中的。
1.1 没有指针的 C++ 项目
class AddressClass
{
public:
int Code;
char[50] Street;
char[10] Number;
char[50] POBox;
char[50] City;
char[50] State;
char[50] Country;
};
class CustomerClass
{
public:
int Code;
char[50] FirstName;
char[50] LastName;
// "Address" IS NOT A pointer !!!
AddressClass Address;
};
int main(...)
{
CustomerClass MyCustomer();
MyCustomer.Code = 1;
strcpy(MyCustomer.FirstName, "John");
strcpy(MyCustomer.LastName, "Doe");
MyCustomer.Address.Code = 2;
strcpy(MyCustomer.Address.Street, "Blue River");
strcpy(MyCustomer.Address.Number, "2231 A");
return 0;
} // int main (...)
.......................................
..+---------------------------------+..
..| AddressClass |..
..+---------------------------------+..
..| [+] int: Code |..
..| [+] char[50]: Street |..
..| [+] char[10]: Number |..
..| [+] char[50]: POBox |..
..| [+] char[50]: City |..
..| [+] char[50]: State |..
..| [+] char[50]: Country |..
..+---------------------------------+..
.......................................
..+---------------------------------+..
..| CustomerClass |..
..+---------------------------------+..
..| [+] int: Code |..
..| [+] char[50]: FirstName |..
..| [+] char[50]: LastName |..
..+---------------------------------+..
..| [+] AddressClass: Address |..
..| +-----------------------------+ |..
..| | [+] int: Code | |..
..| | [+] char[50]: Street | |..
..| | [+] char[10]: Number | |..
..| | [+] char[50]: POBox | |..
..| | [+] char[50]: City | |..
..| | [+] char[50]: State | |..
..| | [+] char[50]: Country | |..
..| +-----------------------------+ |..
..+---------------------------------+..
.......................................
警告：此示例中使用的 C++ 语法类似于 Java 中的语法。但是，内存分配不同。
1.2 使用指针的 C++ 项
class AddressClass
{
public:
int Code;
char[50] Street;
char[10] Number;
char[50] POBox;
char[50] City;
char[50] State;
char[50] Country;
};
class CustomerClass
{
public:
int Code;
char[50] FirstName;
char[50] LastName;
// "Address" IS A pointer !!!
AddressClass* Address;
};
.......................................
..+-----------------------------+......
..| AddressClass +<--+..
..+-----------------------------+...|..
..| [+] int: Code |...|..
..| [+] char[50]: Street |...|..
..| [+] char[10]: Number |...|..
..| [+] char[50]: POBox |...|..
..| [+] char[50]: City |...|..
..| [+] char[50]: State |...|..
..| [+] char[50]: Country |...|..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..| CustomerClass |...|..
..+-----------------------------+...|..
..| [+] int: Code |...|..
..| [+] char[50]: FirstName |...|..
..| [+] char[50]: LastName |...|..
..| [+] AddressClass*: Address +---+..
..+-----------------------------+......
.......................................
int main(...)
{
CustomerClass* MyCustomer = new CustomerClass();
MyCustomer->Code = 1;
strcpy(MyCustomer->FirstName, "John");
strcpy(MyCustomer->LastName, "Doe");
AddressClass* MyCustomer->Address = new AddressClass();
MyCustomer->Address->Code = 2;
strcpy(MyCustomer->Address->Street, "Blue River");
strcpy(MyCustomer->Address->Number, "2231 A");
free MyCustomer->Address();
free MyCustomer();
return 0;
} // int main (...)
如果您检查两种方式之间的区别，您会发现，
在第一种技术中，地址项是在客户内部分配的，而第二种方法，您必须显式创建每个地址。
警告： Java 像第二种方法一样在内存中分配对象，但是，语法类似于第一种方法，这可能会让新手感到困惑 "C++".
实施
因此您的列表示例可能类似于以下示例。
class Node
{
public:
Node(int data);
int m_data;
Node *m_next;
};
.......................................
..+-----------------------------+......
..| Node |......
..+-----------------------------+......
..| [+] int: m_data |......
..| [+] Node*: m_next +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..| Node +<--+..
..+-----------------------------+......
..| [+] int: m_data |......
..| [+] Node*: m_next +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..| Node +<--+..
..+-----------------------------+......
..| [+] int: m_data |......
..| [+] Node*: m_next +---+..
..+-----------------------------+...|..
....................................v..
...................................[X].
.......................................
总结
由于链表的项目数量可变，因此会根据需要分配内存，并且会根据可用情况分配内存。
更新：
同样值得一提的是，@haccks 在他的 post 中评论道。
有时，引用或对象指针指示嵌套项 (a.k.a。"U.M.L. Composition")。
有时，引用或对象指针表示外部项 (a.k.a。"U.M.L. Aggregation")。
但是，相同 class 的嵌套项目无法使用 "no-pointer" 技术应用。
您描述的方法不仅与 C++ 兼容，而且与其 (mostly) subset language C 兼容。学习开发 C 风格的链表是向自己介绍低级编程技术（例如手动内存管理）的好方法，但通常 不是 最佳实践用于现代 C++ 开发。
下面，我实现了四种关于如何在 C++ 中管理项目列表的变体。
raw_pointer_demo 使用与您相同的方法——使用原始指针需要手动内存管理。这里使用C++只针对syntactic-sugar，使用的方式其他方面都兼容C语言- 在
shared_pointer_demo中，列表管理仍然是手动完成的，但内存管理是automatic（不使用原始指针）。这与您可能遇到的 Java. 非常相似
std_list_demo 使用标准库 list 容器。这表明如果您依赖现有的库而不是自己开发库，事情会变得容易得多。std_vector_demo 使用标准库 vector container. This manages the list storage in a single contiguous memory allocation. In other words, there aren't pointers to individual elements. For certain rather extreme cases, this may become significantly inefficient. For typical cases, however, this is the recommended best practice for list management in C++.
注意：在所有这些中，只有 raw_pointer_demo 实际上需要显式销毁列表以避免 "leaking" 内存。当容器超出范围时（在函数结束时），其他三种方法将 自动 销毁列表及其内容。重点是：C++ 在这方面非常 "Java-like" —— 但前提是您选择使用您可以支配的高级工具来开发您的程序。
/*BINFMTCXX: -Wall -Werror -std=c++11
*/
#include <iostream>
#include <algorithm>
#include <string>
#include <list>
#include <vector>
#include <memory>
using std::cerr;
/** Brief Create a list, show it, then destroy it */
void raw_pointer_demo()
{
cerr << "\n" << "raw_pointer_demo()..." << "\n";
struct Node
{
Node(int data, Node *next) : data(data), next(next) {}
int data;
Node *next;
};
Node * items = 0;
items = new Node(1,items);
items = new Node(7,items);
items = new Node(3,items);
items = new Node(9,items);
for (Node *i = items; i != 0; i = i->next)
cerr << (i==items?"":", ") << i->data;
cerr << "\n";
// Erase the entire list
while (items) {
Node *temp = items;
items = items->next;
delete temp;
}
}
raw_pointer_demo()...
9, 3, 7, 1
/** Brief Create a list, show it, then destroy it */
void shared_pointer_demo()
{
cerr << "\n" << "shared_pointer_demo()..." << "\n";
struct Node; // Forward declaration of 'Node' required for typedef
typedef std::shared_ptr<Node> Node_reference;
struct Node
{
Node(int data, std::shared_ptr<Node> next ) : data(data), next(next) {}
int data;
Node_reference next;
};
Node_reference items = 0;
items.reset( new Node(1,items) );
items.reset( new Node(7,items) );
items.reset( new Node(3,items) );
items.reset( new Node(9,items) );
for (Node_reference i = items; i != 0; i = i->next)
cerr << (i==items?"":", ") << i->data;
cerr<<"\n";
// Erase the entire list
while (items)
items = items->next;
}
shared_pointer_demo()...
9, 3, 7, 1
/** Brief Show the contents of a standard container */
template< typename C >
void show(std::string const & msg, C const & container)
{
cerr << msg;
bool first = true;
for ( int i : container )
cerr << (first?" ":", ") << i, first = false;
cerr<<"\n";
}
/** Brief Create a list, manipulate it, then destroy it */
void std_list_demo()
{
cerr << "\n" << "std_list_demo()..." << "\n";
// Initial list of integers
std::list<int> items = { 9, 3, 7, 1 };
show( "A: ", items );
// Insert '8' before '3'
items.insert(std::find( items.begin(), items.end(), 3), 8);
show("B: ", items);
// Sort the list
items.sort();
show( "C: ", items);
// Erase '7'
items.erase(std::find(items.begin(), items.end(), 7));
show("D: ", items);
// Erase the entire list
items.clear();
show("E: ", items);
}
std_list_demo()...
A: 9, 3, 7, 1
B: 9, 8, 3, 7, 1
C: 1, 3, 7, 8, 9
D: 1, 3, 8, 9
E:
/** brief Create a list, manipulate it, then destroy it */
void std_vector_demo()
{
cerr << "\n" << "std_vector_demo()..." << "\n";
// Initial list of integers
std::vector<int> items = { 9, 3, 7, 1 };
show( "A: ", items );
// Insert '8' before '3'
items.insert(std::find(items.begin(), items.end(), 3), 8);
show( "B: ", items );
// Sort the list
sort(items.begin(), items.end());
show("C: ", items);
// Erase '7'
items.erase( std::find( items.begin(), items.end(), 7 ) );
show("D: ", items);
// Erase the entire list
items.clear();
show("E: ", items);
}
std_vector_demo()...
A: 9, 3, 7, 1
B: 9, 8, 3, 7, 1
C: 1, 3, 7, 8, 9
D: 1, 3, 8, 9
E:
int main()
{
raw_pointer_demo();
shared_pointer_demo();
std_list_demo();
std_vector_demo();
}
因为在 C++
中
int main (..)
{
MyClass myObject;
// or
MyClass * myObjectPointer = new MyClass();
..
}
相当于Java
中的这个
public static void main (..)
{
MyClass myObjectReference = new MyClass();
}
其中他们都使用默认构造函数创建了一个 MyClass 的新对象。
Why do linked lists use pointers instead of storing nodes inside of
nodes?
当然有一个微不足道的答案。
如果他们没有通过指针 link 一个节点到下一个节点，他们就不会被 linked列出.
linked 列表的存在是因为我们希望能够将对象链接在一起。例如：我们已经从某个地方得到了一个对象。例如，我们现在想将该实际对象（而不是副本）放在队列的末尾。这是通过将 link 从已在队列中的最后一个元素添加到我们正在添加的条目来实现的。用机器术语来说，就是用下一个元素的地址填充一个词。
我之前在 Java 中广泛使用过链表，但我对 C++ 还很陌生。我在项目中使用的这个节点class很好
class Node
{
public:
Node(int data);
int m_data;
Node *m_next;
};
但我有一个问题没有得到很好的回答。为什么需要使用
Node *m_next;
指向列表中的下一个节点而不是
Node m_next;
我明白用指针版比较好；我不打算争论事实，但我不知道为什么它更好。关于指针如何更好地分配内存，我得到了一个不太明确的答案，我想知道这里是否有人可以帮助我更好地理解这一点。
后者 (Node m_next) 必须 包含 节点。它不会指向它。然后就没有元素链接了。
你使用指针，否则你的代码：
class Node
{
//etc
Node m_next; //non-pointer
};
…不会编译，因为编译器无法计算Node的大小。这是因为它取决于自身——这意味着编译器无法决定它会消耗多少内存。
这不仅更好，而且是唯一可行的方法。
如果您在自身内部存储了一个 Node 对象，那么 sizeof(Node) 会是什么？它将是 sizeof(int) + sizeof(Node)，等于 sizeof(int) + (sizeof(int) + sizeof(Node))，等于 sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node)))，等等直到无穷大。
不可能存在这样的对象。 不可能.
在Java
Node m_node
存储指向另一个节点的指针。你别无选择。在 C++ 中
Node *m_node
意思是一样的。不同之处在于，在 C++ 中，您实际上可以存储对象而不是指向它的指针。这就是为什么你必须说你想要一个指针。在 C++ 中：
Node m_node
意味着将节点存储在此处（这显然不适用于列表 - 您最终会得到一个递归定义的结构）。
C++ 不是 Java。当你写
Node m_next;
在Java，也就是写
一样Node* m_next;
在 C++ 中。在 Java 中，指针是隐式的，在 C++ 中是显式的。如果你写
Node m_next;
在 C++ 中，您将 Node 的实例放在您正在定义的对象中。它始终存在，不能省略，不能用 new 分配，也不能删除。这种效果在Java中是不可能实现的，它与Java用同样的语法所做的完全不同。
附带说明一下，如果 class 或结构的第一个成员是下一个指针（因此没有虚函数或 class 的任何其他功能，这意味着 next 不是' t class 或结构的第一个成员），那么你可以使用 "base" class 或仅带有下一个指针的结构，并使用通用代码进行基本的链表操作，如追加，之前插入，从前面检索，...。这是因为 C/C++ 保证 class 或结构的第一个成员的地址与 class 或结构的地址相同。基本节点 class 或结构将只有一个 next 指针供基本链表函数使用，然后根据需要使用类型转换在基本节点类型和 "derived" 节点类型之间进行转换。旁注 - 在 C++ 中，如果基节点 class 只有一个下一个指针，那么我假设派生的 classes 不能有虚函数。
Why is it better to use pointers in a linked list?
原因是当您创建一个 Node 对象时，编译器必须为该对象分配内存，并为此计算对象的大小。
编译器知道指向任何类型的指针的大小，因此可以计算对象的自引用指针大小。
如果使用 Node m_node，那么编译器不知道 Node 的大小，它将卡在 无限递归 计算 sizeof(Node)。永远记住：a class cannot contain a member of its own type。
概览
在 C++ 中有两种引用和分配对象的方法，而在 Java 中只有一种方法。
为了解释这一点，下面的图表展示了对象是如何存储在内存中的。
1.1 没有指针的 C++ 项目
class AddressClass
{
public:
int Code;
char[50] Street;
char[10] Number;
char[50] POBox;
char[50] City;
char[50] State;
char[50] Country;
};
class CustomerClass
{
public:
int Code;
char[50] FirstName;
char[50] LastName;
// "Address" IS NOT A pointer !!!
AddressClass Address;
};
int main(...)
{
CustomerClass MyCustomer();
MyCustomer.Code = 1;
strcpy(MyCustomer.FirstName, "John");
strcpy(MyCustomer.LastName, "Doe");
MyCustomer.Address.Code = 2;
strcpy(MyCustomer.Address.Street, "Blue River");
strcpy(MyCustomer.Address.Number, "2231 A");
return 0;
} // int main (...)
.......................................
..+---------------------------------+..
..| AddressClass |..
..+---------------------------------+..
..| [+] int: Code |..
..| [+] char[50]: Street |..
..| [+] char[10]: Number |..
..| [+] char[50]: POBox |..
..| [+] char[50]: City |..
..| [+] char[50]: State |..
..| [+] char[50]: Country |..
..+---------------------------------+..
.......................................
..+---------------------------------+..
..| CustomerClass |..
..+---------------------------------+..
..| [+] int: Code |..
..| [+] char[50]: FirstName |..
..| [+] char[50]: LastName |..
..+---------------------------------+..
..| [+] AddressClass: Address |..
..| +-----------------------------+ |..
..| | [+] int: Code | |..
..| | [+] char[50]: Street | |..
..| | [+] char[10]: Number | |..
..| | [+] char[50]: POBox | |..
..| | [+] char[50]: City | |..
..| | [+] char[50]: State | |..
..| | [+] char[50]: Country | |..
..| +-----------------------------+ |..
..+---------------------------------+..
.......................................
警告：此示例中使用的 C++ 语法类似于 Java 中的语法。但是，内存分配不同。
1.2 使用指针的 C++ 项
class AddressClass
{
public:
int Code;
char[50] Street;
char[10] Number;
char[50] POBox;
char[50] City;
char[50] State;
char[50] Country;
};
class CustomerClass
{
public:
int Code;
char[50] FirstName;
char[50] LastName;
// "Address" IS A pointer !!!
AddressClass* Address;
};
.......................................
..+-----------------------------+......
..| AddressClass +<--+..
..+-----------------------------+...|..
..| [+] int: Code |...|..
..| [+] char[50]: Street |...|..
..| [+] char[10]: Number |...|..
..| [+] char[50]: POBox |...|..
..| [+] char[50]: City |...|..
..| [+] char[50]: State |...|..
..| [+] char[50]: Country |...|..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..| CustomerClass |...|..
..+-----------------------------+...|..
..| [+] int: Code |...|..
..| [+] char[50]: FirstName |...|..
..| [+] char[50]: LastName |...|..
..| [+] AddressClass*: Address +---+..
..+-----------------------------+......
.......................................
int main(...)
{
CustomerClass* MyCustomer = new CustomerClass();
MyCustomer->Code = 1;
strcpy(MyCustomer->FirstName, "John");
strcpy(MyCustomer->LastName, "Doe");
AddressClass* MyCustomer->Address = new AddressClass();
MyCustomer->Address->Code = 2;
strcpy(MyCustomer->Address->Street, "Blue River");
strcpy(MyCustomer->Address->Number, "2231 A");
free MyCustomer->Address();
free MyCustomer();
return 0;
} // int main (...)
如果您检查两种方式之间的区别，您会发现， 在第一种技术中，地址项是在客户内部分配的，而第二种方法，您必须显式创建每个地址。
警告： Java 像第二种方法一样在内存中分配对象，但是，语法类似于第一种方法，这可能会让新手感到困惑 "C++".
实施
因此您的列表示例可能类似于以下示例。
class Node
{
public:
Node(int data);
int m_data;
Node *m_next;
};
.......................................
..+-----------------------------+......
..| Node |......
..+-----------------------------+......
..| [+] int: m_data |......
..| [+] Node*: m_next +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..| Node +<--+..
..+-----------------------------+......
..| [+] int: m_data |......
..| [+] Node*: m_next +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..| Node +<--+..
..+-----------------------------+......
..| [+] int: m_data |......
..| [+] Node*: m_next +---+..
..+-----------------------------+...|..
....................................v..
...................................[X].
.......................................
总结
由于链表的项目数量可变，因此会根据需要分配内存，并且会根据可用情况分配内存。
更新：
同样值得一提的是，@haccks 在他的 post 中评论道。
有时，引用或对象指针指示嵌套项 (a.k.a。"U.M.L. Composition")。
有时，引用或对象指针表示外部项 (a.k.a。"U.M.L. Aggregation")。
但是，相同 class 的嵌套项目无法使用 "no-pointer" 技术应用。
您描述的方法不仅与 C++ 兼容，而且与其 (mostly) subset language C 兼容。学习开发 C 风格的链表是向自己介绍低级编程技术（例如手动内存管理）的好方法，但通常 不是 最佳实践用于现代 C++ 开发。
下面，我实现了四种关于如何在 C++ 中管理项目列表的变体。
raw_pointer_demo使用与您相同的方法——使用原始指针需要手动内存管理。这里使用C++只针对syntactic-sugar，使用的方式其他方面都兼容C语言- 在
shared_pointer_demo中，列表管理仍然是手动完成的，但内存管理是automatic（不使用原始指针）。这与您可能遇到的 Java. 非常相似
std_list_demo使用标准库list容器。这表明如果您依赖现有的库而不是自己开发库，事情会变得容易得多。std_vector_demo使用标准库vectorcontainer. This manages the list storage in a single contiguous memory allocation. In other words, there aren't pointers to individual elements. For certain rather extreme cases, this may become significantly inefficient. For typical cases, however, this is the recommended best practice for list management in C++.
注意：在所有这些中，只有 raw_pointer_demo 实际上需要显式销毁列表以避免 "leaking" 内存。当容器超出范围时（在函数结束时），其他三种方法将 自动 销毁列表及其内容。重点是：C++ 在这方面非常 "Java-like" —— 但前提是您选择使用您可以支配的高级工具来开发您的程序。
/*BINFMTCXX: -Wall -Werror -std=c++11
*/
#include <iostream>
#include <algorithm>
#include <string>
#include <list>
#include <vector>
#include <memory>
using std::cerr;
/** Brief Create a list, show it, then destroy it */
void raw_pointer_demo()
{
cerr << "\n" << "raw_pointer_demo()..." << "\n";
struct Node
{
Node(int data, Node *next) : data(data), next(next) {}
int data;
Node *next;
};
Node * items = 0;
items = new Node(1,items);
items = new Node(7,items);
items = new Node(3,items);
items = new Node(9,items);
for (Node *i = items; i != 0; i = i->next)
cerr << (i==items?"":", ") << i->data;
cerr << "\n";
// Erase the entire list
while (items) {
Node *temp = items;
items = items->next;
delete temp;
}
}
raw_pointer_demo()...
9, 3, 7, 1
/** Brief Create a list, show it, then destroy it */
void shared_pointer_demo()
{
cerr << "\n" << "shared_pointer_demo()..." << "\n";
struct Node; // Forward declaration of 'Node' required for typedef
typedef std::shared_ptr<Node> Node_reference;
struct Node
{
Node(int data, std::shared_ptr<Node> next ) : data(data), next(next) {}
int data;
Node_reference next;
};
Node_reference items = 0;
items.reset( new Node(1,items) );
items.reset( new Node(7,items) );
items.reset( new Node(3,items) );
items.reset( new Node(9,items) );
for (Node_reference i = items; i != 0; i = i->next)
cerr << (i==items?"":", ") << i->data;
cerr<<"\n";
// Erase the entire list
while (items)
items = items->next;
}
shared_pointer_demo()...
9, 3, 7, 1
/** Brief Show the contents of a standard container */
template< typename C >
void show(std::string const & msg, C const & container)
{
cerr << msg;
bool first = true;
for ( int i : container )
cerr << (first?" ":", ") << i, first = false;
cerr<<"\n";
}
/** Brief Create a list, manipulate it, then destroy it */
void std_list_demo()
{
cerr << "\n" << "std_list_demo()..." << "\n";
// Initial list of integers
std::list<int> items = { 9, 3, 7, 1 };
show( "A: ", items );
// Insert '8' before '3'
items.insert(std::find( items.begin(), items.end(), 3), 8);
show("B: ", items);
// Sort the list
items.sort();
show( "C: ", items);
// Erase '7'
items.erase(std::find(items.begin(), items.end(), 7));
show("D: ", items);
// Erase the entire list
items.clear();
show("E: ", items);
}
std_list_demo()...
A: 9, 3, 7, 1
B: 9, 8, 3, 7, 1
C: 1, 3, 7, 8, 9
D: 1, 3, 8, 9
E:
/** brief Create a list, manipulate it, then destroy it */
void std_vector_demo()
{
cerr << "\n" << "std_vector_demo()..." << "\n";
// Initial list of integers
std::vector<int> items = { 9, 3, 7, 1 };
show( "A: ", items );
// Insert '8' before '3'
items.insert(std::find(items.begin(), items.end(), 3), 8);
show( "B: ", items );
// Sort the list
sort(items.begin(), items.end());
show("C: ", items);
// Erase '7'
items.erase( std::find( items.begin(), items.end(), 7 ) );
show("D: ", items);
// Erase the entire list
items.clear();
show("E: ", items);
}
std_vector_demo()...
A: 9, 3, 7, 1
B: 9, 8, 3, 7, 1
C: 1, 3, 7, 8, 9
D: 1, 3, 8, 9
E:
int main()
{
raw_pointer_demo();
shared_pointer_demo();
std_list_demo();
std_vector_demo();
}
因为在 C++
中int main (..)
{
MyClass myObject;
// or
MyClass * myObjectPointer = new MyClass();
..
}
相当于Java
中的这个public static void main (..)
{
MyClass myObjectReference = new MyClass();
}
其中他们都使用默认构造函数创建了一个 MyClass 的新对象。
Why do linked lists use pointers instead of storing nodes inside of nodes?
当然有一个微不足道的答案。
如果他们没有通过指针 link 一个节点到下一个节点，他们就不会被 linked列出.
linked 列表的存在是因为我们希望能够将对象链接在一起。例如：我们已经从某个地方得到了一个对象。例如，我们现在想将该实际对象（而不是副本）放在队列的末尾。这是通过将 link 从已在队列中的最后一个元素添加到我们正在添加的条目来实现的。用机器术语来说，就是用下一个元素的地址填充一个词。