我之前在Java中广泛使用链表，但是我对C++非常陌生。我正在使用这个在项目中给我的节点类，感觉还不错。
class Node
{
public:
Node(int data);
int m_data;
Node *m_next;
};
但是我有一个问题没有得到很好的回答。为什么需要使用？
Node *m_next;
指向链表中下一个节点的位置，而不是
Node m_next;
我知道使用指针版本会更好；我不会对事实进行争论，但我不知道为什么它更好。我得到了一个关于指针如何更好地进行内存分配的不太清楚的答案，我想知道是否有人能在这方面帮助我更好地理解。
这不仅仅是更好，它是唯一可能的方式。
如果你在一个Node对象中存储了自身，sizeof(Node)会是多少呢？它将等于sizeof(int) + sizeof(Node)，这将等于sizeof(int) + (sizeof(int) + sizeof(Node))，这将等于sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node)))，以此类推，直到无穷大。
这样的对象是不存在的。它是不可能的。
Node m_node
存储指向另一个节点的指针。您无法选择。在C++中。
Node *m_node
表示相同的意思。不同之处在于，在C++中您实际上可以存储对象，而不是指向它的指针。这就是为什么您必须说您想要一个指针。在C ++ 中：
->意思相同，不同之处在于在C++中你可以实际存储对象而不是对象的指针，这就是为什么你需要声明你要一个指针。在C++中：
Node m_node
在这里存储节点（对于列表显然行不通 - 你最终会得到一个递归定义的结构）。
Node自己的构造函数将被调用，这将实例化另一个新实例...您将获得无限伪递归。这不是完全严格和字面意义上的大小问题，而是性能问题。 - PanzercrisisNode m_node 更像是C++ 中的 Node &m_node，也就是引用而不是指针。 - ablighC++不是Java。当你写代码时，需要明确这一点。
Node m_next;
在Java中，这与编写以下代码相同
Node* m_next;
C++中有指针，Java中指针是隐式的，而C++中则是显式的。如果你写了
Node m_next;
在C++中，你可以将Node的实例放在你正在定义的对象内部。它总是在那里且不能省略，它不能使用new进行分配并且无法删除。这种效果在Java中是不可能实现的，并且与Java在相同语法下所做的完全不同。
你需要使用指针，否则你的代码：
class Node
{
//etc
Node m_next; //non-pointer
};
编译器无法计算Node的大小，因此不会编译，这是因为它依赖于自身，这意味着编译器无法确定它将消耗多少内存。
k == sizeof(Node) 成立且您的类型具有数据，则必须成立 sizeof(Node) = k + sizeof(Data) = sizeof(Node) + sizeof(Data)，然后 sizeof(Node) > sizeof(Node)。 - bitmaskaleph_0就可以满足条件。（只是过于严谨了一些 :-)) - k_gsizeof的返回值是无符号整型，因此超越甚至实际大小的希望也就破灭了。（更加严谨！ :p） - ThomasNode甚至没有被定义，因此您无法在内部真正使用它。允许隐式地前向声明指向尚未声明的类的指针是一种小技巧，语言允许这样的结构成为可能，而无需一直显式地转换指针。 - Sergey Orshanskiy后者（Node m_next）必须包含节点，而不是指向它。这样就不需要对元素进行链接。
raw_pointer_demo使用与您相同的方法 - 需要使用原始指针进行手动内存管理。在此，C++仅用于语法糖，否则使用的方法与C语言兼容。shared_pointer_demo中，列表管理仍然是手动完成的，但是内存管理是自动的（不使用原始指针）。这与您在Java中体验到的非常相似。std_list_demo使用标准库list容器。这显示了如果依赖于现有库而不是自己编写代码，事情会变得更加容易。std_vector_demo使用标准库vector容器。这将列表存储在单个连续的内存分配中。换句话说，没有指向各个元素的指针。对于某些相当极端的情况，这可能会变得非常低效。但是，对于典型情况，这是C++中列表管理的推荐最佳实践。raw_pointer_demo实际上需要显式销毁列表以避免“泄漏”内存。当容器超出范围时（在函数结束时），其他三种方法将自动销毁列表及其内容。重点是：如果选择使用可用的高级工具开发程序，则C++在这方面可以非常类似于Java。/*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();
}
Node_reference 声明涉及到 Java 和 C++ 之间最有趣的语言级别差异之一。在 Java 中，声明类型为 Node 的对象会隐式地使用对一个单独分配的对象的引用。而在 C++ 中，你可以选择引用（指针）或直接（堆栈）分配 -- 因此你必须显式地处理这个区别。在大多数情况下，你会使用直接分配，但不适用于列表元素。 - Brent Bradburn概述
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在他的帖子中所评论的那样。
有时，引用或对象指针表示嵌套项（也称为"U.M.L.组合"）。
有时，引用或对象指针表示外部项（也称为"U.M.L.聚合"）。
但是，同一类的嵌套项无法使用“无指针”技术。
Node m_node，编译器将不知道Node的大小，并将陷入无限递归计算sizeof(Node)的状态。请记住：类不能包含其自身类型的成员。因为这是使用C++编写的。
int main (..)
{
MyClass myObject;
// or
MyClass * myObjectPointer = new MyClass();
..
}
。
public static void main (..)
{
MyClass myObjectReference = new MyClass();
}
这两行代码都使用默认构造函数创建了一个MyClass类的新对象。
Node m_next并不是对节点的引用，而是存储整个Node本身的空间。 - Brian Cain