列表拼接和遍历库的实现

• 下载 arraysplice.zip - 1.8 MB

引言

与 C++ 标准模板库的丰富性相比，C 标准库似乎相当稀疏。其中一个功能领域是动态向量，它提供了构建和操作列表的基本函数。由于没有现成的列表基本函数，C 程序员往往依赖数组和循环，这会导致在 Python 或 C++ 等其他编程语言中会使用更高级、更抽象、更以问题为中心的源代码。

背景

C++11 标准模板库和 C++11 标准的变更给 C++ 注入了函数式编程的风格。在学习了 Bjarne Stroustrup 的最新版《C++ 编程语言》以及阅读了 Allen Holub 的《Holub on Patterns》一书后，我意识到我在编程时过多地关注了解决方案领域，即如何在源代码中实现解决方案，而对问题领域的关注不足。我作为旧 C 源代码的维护程序员的主要工作是侧重于解决方案领域，通过 Holub 所说的“原始循环”来实现功能，并编写那些需要信息而不是通过委派操作给模块、对象或函数来寻求帮助的函数。

为了重塑我的关注点，我决定以列表作为抽象数据类型来实验实现一个用 C 编写的通用列表功能，并供 C 程序员使用。这个库的目标是提供 C++11 标准模板库以及 PHP 或 Python 等脚本语言中可用的部分列表功能。

我脑中的问题是如何提供一个可以与各种不同数据类型一起使用的列表功能。 C 编程语言在面向对象编程方面提供的设施很少，而 C 预处理器虽然在其时代非常出色，但没有 C++ 模板在泛型编程方面的特性和功能。C 的局限性意味着提供列表功能将相当依赖 C 程序员，并且需要使用 void 指针和其他变通方法来替代 C++ 编译器使用模板所能提供的功能。

这项练习的目标是编写一组有用的列表函数，同时探索使用列表数据结构所提供的可能性。基本操作是能够向列表中添加或删除项目，以及对列表进行更改。我以 PHP 提供的 `splice()` 函数作为此包中实现的 `Splice()` 方法的模型，并参考 C++11 标准模板库来模型化将算法应用于列表元素。

为了使 `FindIf()`、`FindIfNext()`、`ForEachRemoveIf()` 等类型的函数更有用和灵活，我借鉴了 C 标准库的 `qsort()` 和 `bsearch()` 函数传递函数指针的方法，并添加了一个额外的指针操作数，该操作数可用于向用于处理列表的函数提供状态数据。额外的指针操作数通过在列表处理过程中提供状态数据以及提供结构体内的函数指针以对列表项进行进一步操作的可能性，打开了无数的可能性。

使用代码

基本概述

实际的列表功能库很小。为了减少命名空间冲突的可能性，有一个外部可见的结构体，其中包含指向实际列表操作函数的函数指针。唯一可用的类型是 `ItemArray`，有一个外部可见的实例 `ItemArrayFactory`。这个外部可见的实例在应用程序启动时就已初始化，为使用 `ItemArrayFactory.Create()` 方法创建的 `ItemArray` 实例提供了默认值。`ItemArrayFactory.Create()` 方法返回一个指向已初始化内存区域的指针，该区域将用于维护列表状态数据以及提供可用于操作列表的方法。这种使用带函数指针的结构体的方式类似于 C++ 中结构体的使用方式，其中结构体本质上是一个所有成员和方法都具有公共可见性的类。

C 编程语言没有构造函数或析构函数的规定，这意味着程序员使用未正确初始化的变量的机会很高，创建内存泄漏的机会也很高。由于结构体的所有成员都具有公共可见性，因此难以强制执行封装和隐藏数据成员。缺乏模板意味着要提供一种适用于多种数据类型的泛型编程方法需要变通方法，这会降低编译器使用静态分析来检测潜在源代码缺陷并生成适当警告的能力。

鉴于 C 编程语言的这些以及其他缺陷，对程序员的技能和纪律的要求更高。

这是来自 `arraysplice.cpp` 的测试工具中的一段代码示例。此示例使用 `ItemArrayFactory.Create()` 方法创建一个空列表，然后执行一些初步的一致性检查。这些源代码行展示了此库使用的风格。

//  Create a new, empty list to contain copies of ArrayItem structs.  The initial max size is 6
ItemArray *jj = ItemArrayFactory.Create (sizeof(ArrayItem), 6);
if ( ! ItemArrayFactory.IsValidArray (&jj)) {
    std::cout << "test 2a, failed, IsValidArray() detected valid array as invalid." << std::endl;
}
if ( ! ItemArrayFactory.IsEmpty (&jj)) {
    std::cout << "test 2b, failed, IsEmpty() detected empty array as not empty." << std::endl;
}

这段源代码展示了几种风格特点。首先，`ItemArrayFactory.Create()` 方法用于创建一个空列表。指定了列表中存储项的大小。最简单的方法是使用 `sizeof()` 运算符，让编译器自行确定。第二个参数是初始最大计数。当添加项并且超过最大计数时，将使用 C 标准库函数 `realloc()` 重新分配列表，创建一个具有更大最大计数值的现有列表副本，从而为其他项腾出空间。

请注意，`ItemArrayFactory` 外部的 `IsValidArray()` 方法用于验证列表对象是否已实际创建。新创建的 `ItemArray` 对象 `jj` 也拥有相同的方法，因为 `jj` 是一个指向已初始化的 `ItemArray` 对象的指针，该对象包含与 `ItemArrayFactory` 相同的函数指针。当创建一个新的 `ItemArray` 对象时，它会包含 `ItemArrayFactory` 对象的一个副本，并初始化了部分数据成员以用于列表。但是，由于 `Create()` 方法可能会失败，我们使用 `ItemArrayFactory.IsValidArray()` 方法，因为该方法是否存在，无论 `jj` 是否已正确创建。

在测试工具的稍后部分，您可以看到一些源代码行，其中使用 `PushBack()` 方法将项添加到列表末尾，以及使用 `RemoveBack()` 方法从列表中移除项，类似于以下示例。

//  Add an item to the list
jj->PushBack (&jj, &oneItem);

//  ...

// Remove the item on the end of the list getting a copy of the item
jj->RemoveBack (&jj, &twoItem);

请注意，在这两种情况下，我们都使用 `ItemArray` 指针来调用我们想要使用的方法，并且该方法的第一个参数本身就是 `ItemArray` 指针。几乎列表库中的每个函数都使用第一个参数来标识实际的列表对象。如果这是 C++ 结构体，我们就无需提供标识实际对象的第一个参数。我们将不写 `jj->PushBack(jj, &oneItem);`，而是写 `jj->PushBack(&oneItem);`，C++ 编译器将确保 `this` 指针被正确设置为实际对象地址。然而，在 C 中，程序员必须提供对象，因为我们实际上是通过一个碰巧在 `ItemArray` 结构体对象中的函数指针变量来调用函数。

接口和数据与命令参数

拼接库中的一些方法是直接的，具有功能内聚性，即它们执行单个任务或函数而不产生副作用。一些方法是复杂的，其接口参数既充当数据（例如，当起始位置大于等于 0 时）又充当命令（例如，当起始位置为负数时，表示使用上次比较的结果）。

这种灵活性通常是缺陷的来源，因为它会在模块或函数之间产生不易察觉的耦合。总体而言，实现和使用副作用并非一个好的设计决策。比较索引副作用是一把双刃剑。对于 `FindIf()` 和 `FindIfNext()` 方法对，使用比较索引副作用是有意义的，并且实际上是可见接口的一部分。

然而，允许比较索引副作用可用于 `Splice()` 等其他方法，则开始进入危险区域。

内存管理注意事项

使用 C 编程语言开发此库的一个问题是，该库预计将在 C 程序中使用，其中一些库函数有时需要请求额外的内存，以便有足够的内存来容纳修改后的列表。只有两种可能的选择：始终返回对象指针，当可能执行内存 `realloc()` 的方法返回时；或者要求那些可能需要执行 `realloc()` 的方法提供一个变量的地址，如果执行了 `realloc()`，该变量将被更新为新地址。

第三种选择可能是改变内存管理。列表对象的创建方式是分配一个内存区域，该区域包含列表对象头（带有列表管理数据）和实际列表存储区域。列表对象头包含一个指向列表对象头之后的区域的指针，然后该区域用于包含实际列表数据。第三种选择是稍微不同地处理列表对象的表示，即列表对象不是由包含列表管理信息和实际列表数据的单个连续内存区域组成，而是由两个内存块组成：一个内存块中的列表对象头和第二个内存块中的列表数据。

起初，我尝试了第一种方法。在测试和扩展库的过程中，我发现知道何时进行可能发生 `realloc()` 的赋值会增加源代码的复杂性，并且需要比预期更多的对方法内部的了解。是否进行了 `realloc()` 似乎是一个应该保持私有的实现细节。因此，我修改了所有函数到接口，使它们接受指向对象的指针的地址，而不是对象本身的指针。

库提供什么以及如何使用标准 C 库

该库的重点是提供一组列表处理的基本函数。基本功能涵盖创建和删除列表对象，以及一组允许用户将列表拼接或将列表的一部分切片到另一个列表中的方法。由于 C 标准库提供了排序函数 `qsort()` 和二分搜索函数 `bsearch()`，因此添加了两个方法来提供排序列表和搜索列表项的方法，这些方法包装了 C 标准库中的这两个函数。

测试工具提供了可用的功能及其使用方法的概念。此库的使用方式与 C++ 标准模板库 `vector` 类的使用方式有些相似。由于列表数据区域由 `ItemArray` 结构体成员 `m_ItemList` 指向，并且该成员是公共可见的，因此列表可以被访问为 C 数组，使用 `ItemArray` 结构体成员 `m_ItemCount` 来知道正在使用多少个数组元素。

该包提供了构建列表的方法，一次构建一个项目，或通过将列表合并到另一个列表中，并执行各种操作来搜索列表中的项目以及修改列表或列表中的项目。

C 编程语言，常被称为高级汇编语言，提供了一种机制，即函数指针，它提供了极大的灵活性，但也提供了很多“自投罗网”的机会。本包在两种特定情况下使用函数指针：将算法或操作应用于列表中的项，以及为那些依赖比较来查找列表中项的方法提供比较函数。

由于这些函数由程序员提供，因此在迭代列表时都会为每个项调用一次，从而为以类似方式使用它们打开了可能性。虽然比较函数仅用于执行比较，但程序员也可以使用比较函数在处理比较项时修改它们。我不确定这是否是一个缺陷，还是一个特性。

关注点

各种方法的性能

完成第一个实现后，我很好奇大型列表的性能如何。由于方法使用了连续的内存区域，因此在除列表末尾以外的任何位置插入都需要移动插入点之前的数据，然后再插入新数据。

我创建了一个简单的列表，然后在一个循环中使用 `Splice()` 方法来使用这个简单的列表，以了解其性能影响。测试涉及一个循环，其源代码类似于以下内容，并带有 `Splice()` 方法的两个变种。我首先使用未优化版本的调试构建，然后重新编译了一个发布构建，看看是否有区别。

jj = ItemArrayFactory.Create (sizeof(ArrayItem), 100000);
j2 = ItemArrayFactory.Create (sizeof(ArrayItem), 6);

for (int ii = 0; ii < 33; ii++) {
    ArrayItem initval = {20, ii};
    j2->PushBack (&j2, &initval);
}

for (int ii = 0; ii < 100000; ii++) {
    jj->Splice (&jj, -1, 0, &j2, 0, -1);
}

尝试了两种变体：一种是反复将列表 `j2` 放入列表 `jj` 的开头（起始位置为 0），另一种是反复将列表 `j2` 放入列表 `jj` 的末尾（指定的起始位置为 -1，表示使用列表末尾）。

测试在配备 Intel Core 2 Duo 2.4GHz CPU 和 3.5 GB RAM 的 Dell 笔记本电脑上运行。运行了两个测试序列：一个调试构建和一个发布构建，均使用 Visual Studio 2005 编译。

在第一个调试构建的测试运行中，在 Windows XP 的任务管理器中观察进程时，第一个变种显示 CPU 时间为 0:12:32，VM 大小为 26,292，而第二个变种显示 CPU 时间为 0:01:42，VM 大小为 26,256。页错误数相似，约为 2080 万。在内部，`Splice()` 方法在 `Splice()` 不在列表末尾时需要执行 `memmove()` 来打开插入点，而此操作似乎成本很高。

在第二个测试中，发布构建仅在目标列表开头执行列表拼接，任务管理器中显示的数据与调试构建在列表开头插入时的数据相似。调试和发布构建之间相似的性能数据表明，大部分工作可能是页错误和数据移动。

一些有趣的语法

在使用此库时，我尝试了一些不寻常的语法，以及一两个实验。

第一个实验是让一些函数返回一个结构体而不是单个值。这允许一些函数同时返回列表上的项目指针和列表对象本身的指针。类似的结构体可用于在函数返回值的同时提供错误代码。在许多情况下，函数值用于返回有效数据或无效数据项以指示发生了错误。一个例子是 `malloc()` 函数，它返回一个有效指针或一个 NULL 指针以指示 `malloc` 尝试失败。

在测试工具中，我使用了以下源代码行，该行结合了在列表中查找元素，然后将其用作 `Splice()` 的插入点。我不推荐这种构造作为好的实践，但它编译并工作，这很有趣。

jj = jj->SpliceOnFind (&(jj->FindIf (&jj, 0, -1, ArrayItemRemoveGreaterThan, &cmpGreaterThan).pList), 0, &j2, 0, -1);

问题在于 `FindIf()` 方法返回的结构体是临时的，会消失，因此如果 `SpliceOnFind()` 需要执行内存 `realloc()`，新列表对象的地址也会被丢弃。有三种简单的解决方案。第一种也是最直接的方法是将此拆分为两行源代码，使用相同的列表对象指针。第二种方法是在 `FindIf()` 方法调用后使用逗号运算符引入一个顺序点，后跟列表对象指针的地址，例如 `(jj->FindIf(&jj, ...), &jj)` 或 `&(jj->FindIf(&jj, ...), jj)`。第三种方法是使用赋值运算符来获取 `SpliceOnFind()` 方法返回的列表对象指针，该方法是本例中使用的。

方法接口的复杂性

一个潜在的问题是方法接口的复杂性，以及一些方法存在副作用的事实。对于某些方法参数，使用特殊值将数据参数转换为命令参数。例如，在多个地方指定的结束位置可以接受值负一（-1）以指示使用列表的其余部分。这意味着函数调用不需要确定列表的结束位置，而是可以简单地指示使用列表的末尾，无论该值是什么。

`FindIf()` 和 `FindIfNext()` 方法会产生副作用，其中匹配项在列表中的位置存储在列表对象管理数据中。这有助于使用 `FindIf()` 后跟重复调用 `FindIfNext()` 来查找所有符合条件的匹配项。由于比较函数的指针以及比较状态对象的指针也存储在列表对象中，因此可以更容易地将 `FindIf()` 和 `FindIfNext()` 作为一对使用，例如在测试工具中的以下示例中。

ArrayItem cmp = {1, 0}, found = {0, 0};
iLoop = 0;
pFound = (ArrayItem *)(jj->FindIf (&jj, 0, -1, ArrayItemCmp, &cmp)).pItem;
while (pFound) {
    found.i += pFound->i;     // pFound->i should always be equal to 1 since that is what we are looking for
    found.j += pFound->j;
    iLoop++;                 // value of iLoop is the count of number of matching items
    if (pFound->i != 1) {
        std::cout << "test 13f, failed, PushBack() FindIf() FindIfNext() pFound check failed." << std::endl;
    }
    pFound = (ArrayItem *)(jj->FindIfNext (&jj, -1, -1, 0, 0)).pItem;
}

对于这样一个包，一个设计问题是如何在多大程度上依赖副作用来提供必要的行为。有些方法似乎很明显地与副作用配对，例如 `FindIf()` 和 `FindIfNext()` 方法。但是，`ForEachRemoveIf()` 函数是否应该使用相同的副作用作为开始搜索的地方？也许应该有一个指定操作的方法

副作用的问题在于它们会在方法之间引入耦合，这可能会使使用该包的人感到困扰。因此，方法接口中确实需要一些语法，以便方法的使用者知道它们何时依赖副作用，何时不依赖。还需要提供一种机制来检测副作用状态是否与正在调用的方法不兼容，然后采取合理的措施。结果是增加了方法的复杂性，同时也增加了使用这些方法的程序员的认知负担。

历史

在此处保持您所做的任何更改或改进的实时更新。