如何在 c++ 链表中使用模板?

Question

我不完全理解模板的概念，并试图获得有关如何在下面的链表上实现模板的帮助。我正在尝试让我的代码能够支持以下类型List< List<std::string> >List<std::string>List<int>：我想知道除了尝试解释正在发生的事情之外，是否有人可以给我一个例子，说明如何将这些项目转换为模板？我是 c++ 的新手，所以我能得到的任何帮助将不胜感激。

#include <string>
#include <iostream>
#include <cstddef>

using Item = std::string;
// TURN DList into a template!
class DList {
private:
class DListNode {
public:
Item item;
DListNode * next;
DListNode * prev;
DListNode(Item i, DListNode *n=nullptr, DListNode *p=nullptr) {
item = i;      
next = n;
prev = p;
}
};
DListNode * head;
DListNode * tail;
public:
class iterator {
DListNode *node;
public:
iterator(DListNode *n = nullptr) {
node = n;
}
Item& getItem() { return node->item; }
void next() { node = node->next; }
void prev() { node = node->prev; }
bool end() { return node==nullptr; }
friend class DList;
};

public:
DList() {
// list is empty
head = nullptr;
tail = nullptr;
}
bool empty() {
return head==nullptr;
}
void append(Item a) {
DListNode *node = new DListNode(a,nullptr,tail);
if ( head == nullptr ) {
// empty list
head = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
}
void insertAfter(iterator it, Item item)
{
if(head == nullptr || it.node == nullptr) { // NULL iterator means insert at head
DListNode *node = new DListNode(item,head); // next=head, prev=NULL
if ( head == nullptr) // same as zyBook
head = tail = node;
else { // if inserting before head, it.node==NULL
head->prev = node;
head = node;
}
} else if (it.node == tail) {
DListNode *node = new DListNode(item,nullptr,tail); // next=NULL, prev=old tail
tail->next = node;
tail = node;
} else {
DListNode *node = new DListNode(item,it.node->next,it.node);
it.node->next = node;
node->next->prev = node;
}
}
void erase (iterator it) {
DListNode *succ = it.node->next; // successor node
DListNode *pred = it.node->prev; // predecessor node
if (succ != NULL)
succ->prev = pred;
if (pred != NULL)
pred->next = succ;
if (it.node == head)
head = succ; // head is following node
if (it.node == tail)
tail = pred; // tail is previous node
delete it.node; // delete the node; not shown in zyBook, but necessary in C/C++
// iterator is now invalid, caller should not use it again
}
iterator begin() {
return iterator(head);
}
iterator reverse_begin() {
return iterator(tail);
}
};
template <typename Item>
std::ostream& operator << (std::ostream& out, DList<Item> &l)
{
out << "{";
auto it = l.begin();
out << it.getItem();
it.next();
for(; !it.end(); it.next())
{
out << ", " << it.getItem();
}
out << "}" << std::endl;
return out;
}

int main()
{
{
DList<std::string> l;
l.append("eggs");
l.append("milk");
l.append("bread");
std::cout << l;
}
{
DList<int> l;
l.append(1);
l.append(2);
l.append(3);
std::cout << l;
}
return 0;
}

Answer 1

实际上，您几乎拥有所需的一切，但您仍在使用具有具体类型的 regualar 类。

using Item = std::string;
class DList { ... };

所以首先我们去掉具体类型：

// using Item = std::string;
class DList { ... }; // sure Item is now undefined...

然后我们告诉类是一个模板

template <typename Item>
class DList { ... };

现在Item被重新引入，但它现在不是具体类型，而是通用类型。就是这样，你有一个模板列表(假设列表正确实现，我没有检查(。

现在，每当您实例化列表时：

DList<int>;
DList<std::string>;
// ...

你创建了一个全新的、独立的数据类型(这尤其意味着，你不能将DList<int>分配给指向DList<double>的指针，就像你不能将 int 分配给指针到双精度一样(。

当您实例化模板时，每次出现的模板参数都将替换为您实例化模板的类型，例如，在DList<int>中，每次出现Item都将替换为int。

好吧，所有这些都只是一个非常简短的介绍，还有很多事情要做，但这更像是在书中处理，而不是在堆栈溢出的答案中处理......

不过，对节点构造函数的一些说明：

DListNode(Item i /* , ... */) { item = i; }

首先，您应该习惯于使用构造函数的初始化器列表(不要与std::initializer_list混淆(：

DListNode(Item i /* , ... */) : item(i) { }

您可以避免默认的启动 + 赋值，而是按值直接初始化。此外，某些类型(非默认可构造类型、const 成员和引用(只能以这种方式初始化。

然后，您将生成不必要的副本：

DListNode(Item i /* , ... */) : item(i) { }
//             ^ temporary copy   ^ final copy, created from temporary

如果您通过引用接受该项目，则可以避免该副本：

DListNode(Item const& i /* , ... */) : item(i) { }
// now copies from reference, one copy less

您还可以提供移动语义：

DListNode(Item&& i /* , ... */) : item(std::move(i)) { }

这样，您不再需要的列表之外的对象就可以移动到其中(好吧，实际上是它们的内容(。在某些情况下，这可能比完整副本便宜得多......

关于构造函数的所有内容(除了初始化器列表(也适用于append和insertAfter函数。

初始化器列表和避免复制是一般建议，与模板无关......