检查 std::list 的结构

std::list 类看起来像清单 5-6。

template<typename T>
class listItem {
    listItem<T>* next;
    listItem<T>* prev;
    T value;
};
template<typename T>
class list {
    listItem<T>* root;
    int size;
};

清单 5-6：一个抽象的 std::list 对象

这里有两个类：listItem 和 list。为了避免在解释 std::list 如何工作时增加额外抽象，我会按类型为 DWORD 时的样子描述这个对象。下面是一款游戏如何声明 DWORD 类型的 std::list：

std::list<DWORD> _lst;

鉴于该声明，std::list 的结构如清单 5-7 中的代码。

    listItem* next;
    listItem* prev;
    DWORD value;
};
class list {
    listItem* root;
    int size;
};
// 指向列表
list* _lst = (list*)listAddress;

清单 5-7：一个 DWORD std::list 对象

list 类表示列表头，而 listItem 表示列表中存储的值。列表中的项目不是连续存储的，而是独立存储。每个项目包含一个指向它后面项目的指针（next）和一个指向它前面项目的指针（prev），这些指针用于定位列表中的项目。root 项目充当列表末尾的标记；最后一项的 next 指针指向 root，第一项的 prev 指针也指向 root。root 项目的 next 和 prev 指针还分别指向第一项和最后一项。图 5-5 展示了它的样子。

给定这个结构，你可以用以下代码遍历 std::list 对象：

// 向前遍历
listItem* it = _lst->root->next;
for (; it != _lst->root; it = it->next)
    printf("Value is %d\n", it->value);
// 向后遍历
for (; it != _lst->root; it = it->prev)
    printf("Value is %d\n", it->value);

第一个循环从第一项（root->next）开始，向前迭代（it =it->next），直到碰到末尾标记（root）。第二个循环从最后一项（root->prev）开始，向后迭代（it = it->prev），直到碰到末尾标记（root）。这种迭代依赖 next 和 prev，因为与数组中的对象不同，std::list 中的对象不是连续的。由于 std::list 中每个对象的内存不是连续的，没有快速计算大小的捷径。相反，类只定义了一个 size 成员。此外，为列表中的新对象保留空间的概念无关紧要，所以没有变量或计算来确定列表的容量。