C++ 容器的替代方法

• 下载源代码 - 23.7 KB

目录

• 引言
• 泛型编程和“引用语义”
• 泛化解引用
• Vector 及其异常
• 集合和迭代
• 缓冲区、向量和字符串
• 链式、串联和列表
• B树、节点、集合和映射
• 内存分配
• 单元测试
• 结论

引言

本文的构思源于对 C++ 标准库中用于创建开放数据结构的容器可用性的一些思考。事实上，STL 并没有提供太多帮助：它提供了结构良好的容器，但隐藏了内部结构，因此你无法对其进行扩展。实际上，任何需要实现自链接或自排序对象的人在 STL 中都找不到答案。

其他替代方法不考虑“值”的通用容器的概念，而是考虑使对象意识到容器的概念。当这种情况不适用时，就将值包装在容器感知的框中。

因此，我重新开始，没有使用 STL，而是写了自己的容器，试图摆脱 STL 的“值语义”概念。

泛型编程和“引用语义”

泛型编程的概念背后是这样的想法：对于类型 T 定义的任何功能都可以进行特化，以便“调整”为不符合给定默认值类型。这通常通过全局模板函数或通过作为策略的特性类（仅包含 typedefs 和静态函数的类）来完成，这些类相对于指定自定义行为的参数类型起作用。

这对于“值语义”来说是很好的，因为很容易想象一个返回值的函数，但当处理引用语义时，由于 C++ 的非托管性质，这会变得非常棘手。

实际上，我们永远无法确定谁拥有被引用的对象，谁创建了它，以及在传递给参数和返回值时谁应该销毁它。

“智能指针”，如 std::auto_ptr 或 boost::shared_ptr，可以解决这类问题。

但它们未能支持 C++ 的另一项功能：运算符重载。你将运算符定义为与类（因此具有值语义）一起操作，通过“指针”操作时会丢失它们。你总是需要显式地解引用它们，同时，在返回时仍然存在复制的问题。

为了更好地解释这一点，可以考虑一种“非常复杂”的数字，并定义两个数字之间的加法：除了返回时复制之外，别无他法。如果你想返回一个 auto_ptr<my_verycomplex>，最终会得到一个 operator+，它接收两个 my_verycomplex 并返回一个“指针”。

或者考虑只有操作指针的想法。

其他垃圾回收语言，如 C# 或较新的 D，总是动态分配对象，因此它们不需要区分访问和解引用（因此它们没有 -> 运算符），并且将引用视为运算符的“值”。

因此，我开始的想法是泛化解引用操作，并将指针的解引用特化为自动解引用。结果是一种有点奇怪的智能指针，它与类似的指针不同，可以自行转换——与它的相应值（而不是指针）相互转换，尽管由于 C++ 对使用“.”运算符的规定很严格，它们具有 -> 和 * 运算符。

泛化解引用

就像我们可以使用模板函数进行泛化比较一样

template<class A, class B> bool is_less(const A& a, const B& b)
{ return a < b; }

以便我们可以根据A和B不同地特化 is_less，解引用也可以使用特性进行特化，如下所示

template<class T>
struct dereference
{
    typedef T value_t; // the "dereferencing" type
    typedef T access_t; // the "dereferenced" result

    // default access to a pointer will result in the pointer itself
    static access_t* access(value_t* p) { return p; }
};

我们在这里基本上说，默认情况下，指向值的指针会访问值本身。

这时，我们可以声明一个智能句柄（一个可以自动转换为其值的指针），使用下面的类

template<class T>
class auto_H
{
    T* p; 
public:
    auto_H() :p() {}
    auto_H(const auto_H& h) :p(h.p) { const_cast<auto_H&>(h).p = 0; }
    auto_H(const T& t) :p(new T(t)) {}
    explicit auto_H(T* s) :p(s) {}
    ~auto_H() { delete p; }
    H& operator=(const H& h)
    { if(this != &h) { this->~H(); new(this)H(h); } return *this; } 
    /* access and dereference through generalized "dereference" */
    const T* get() const { return p; }
    T* get() { return p; }
    typedef T value_t;
    typedef typename dereference<T>::access_t access_t;
    const access_t* operator->() const 
    { if(!p) throw dbg::excp_nullptr(); return dereference<T>::access(p); }
    const access_t& operator*() const { return *operator->(); }
    access_t* operator->() 
    { if(!p) p = new T; return dereference<T>::access(p); }
    access_t& operator*() { return *operator->(); }
    operator const access_t&() const { return operator*(); }
    operator access_t&() { return operator*(); }
};

本质上，它累积了以下功能

• 复制和赋值会执行所有权转移（类似于 auto_ptr）。
• 访问和解引用（-> 和 *）通过解引用特性进行操作，并且与常规指针不同，它们会保留 const 性。
• 自动转换为相应的引用（而不是指针）并从相应的引用转换回来，因此，如果 T 提供了自己的运算符，我们可以轻松地编写混合T和 auto_H<T> 的表达式。由于最后一个事实，T可以使用 auto_H<T> 本身返回一个值，从而避免了返回时的复制。
• 在非 const 模式下访问时自动创建值。

但一个重要方面是，通过特化 dereference，我们可以得到一个有趣的递归，如下所示

template<class T>
struct dereference<auto_H<T> >
{
    typedef auto_H<T> value_t;
    typedef typename dereference<T>::access_t access_t;
    static access_t* access(value_t* p) { return p->operator->(); }
};

在这里，我们说访问 auto_H 将导致其自身深度访问，从而使所有间接层都自动转换为其相应的深度值。

类 H<T,cow> 实现了一个类似于 auto_H 的句柄，但使用引用计数而不是所有权转移，并且当cow被定义为true时，通过克隆（通过复制构造函数）共享值来执行写时复制，如果以非 const 方式访问。

Vector 及其异常

与大多数容器不同，向量存在一个异常：它们的元素不能独立于彼此分配，并且在增长、插入和删除元素的情况下，整个结构必须重新定位，以保持其“连续元素的紧凑结构”这一基本性质，而这是需要通过整数索引进行高效访问的。

实际上，向量是由一个“管理器”动态分配的数组，该管理器定义了如何增长和缩小该数组，该管理器作为参数或返回值传递，可以共享、复制等。该管理器本身就是一个句柄，因此向量必须表现得像“被句柄化”。

但向量也是可以枚举和迭代的集合。因此，需要有一个接口，允许类被此类操作一致地使用。

集合和迭代

STL 定义了一个抽象的“迭代器”概念（它不过是一个支持 ++ 和 -- 操作的通用指针），并在每种集合类型中私有实现。在这里，我们将保持这个概念的开放性，将迭代器定义为依赖于它们所迭代的集合中实现的功能的通用类型。

在此框架中，迭代器期望操作一个实现此接口模型的类

struct ti_enumerable
{
    struct index_type;
    struct iterated_type;

    iterated_type& at(index_type i);
    const iterated_type& at(index_type i) const;
    index_type first() const;
    index_type last() const;
    index_type prev(index_type ) const;
    index_type next(index_type ) const;
};

实际上，index_type 将被重写为“任何适合标记集合中某个位置的类型”：本质上是一个通用的“索引”。同时，iterated_type 将是迭代器解引用的预期类型。

你将不需要一个迭代器类来遍历集合，因为这些函数是可访问的。但迭代器可以通过类似于句柄的语法来简化遍历，而不是直接使用集合枚举函数。

“解引用”必须通过 at 函数在集合中实现，而迭代由 first、last、prev 和 next 支持。为了正确支持迭代边界，next(last()) 和 prev(first()) 必须返回一个可识别的索引值来标记迭代的结束。

对于 vector 基类 buffer，这变成了

typedef int index_type;
typedef typename dereference<T>::access_t iterated_type;
int first() const { return p->size? 0: npos; }
int last() const { return p->size? p->size-1: npos; }
int next(int n) { return (n<p->size-1)? n+1: npos; }
int prev(int n) { return (n>0)? n-1: npos; }
const iterated_type& at(int idx) const { 
return *dereference<T>::access(&p->get()[idx]); }
iterated_type& at(int idx) { unshare(); 
return *dereference<T>::access(&p->get()[idx]); }

其中 T 是缓冲区参数化的类型。请注意，我们使用了特化解引用来通过索引和迭代来访问存储的值，以便句柄的向量表现为持有值。

缓冲区、向量和字符串

buffer 类实现了一个引用计数的写时复制数组，其增长能力为容量的 50%，无需重新定位，使用就地构造和删除其元素。

这些操作由一个特性类（buffer_traits<T>）驱动，该类对于通用类型会迭代默认构造函数、复制构造函数和析构函数。

可以轻松地为字符类型特化它们，以避免这种开销，并调用传统的 C 函数（通常在直接汇编中实现）memcpy、memset 和 memmove。

类 vector 是一个“调优”得更好的缓冲区（它从中派生），由 vector_traits 驱动，它重写了 buffer_traits 并添加了一些特定功能来支持字典序排序。与 buffer 不同，vector 通过重写从 comparable 继承的 <== 运算符来支持比较运算符，并将委托给特性。

与许多其他框架不同，这里的 string 不是 vector，而是 buffer 的另一种风格，具有不同的特性（string_traits）和一些更具体的成员函数。

与向量的主要区别在于比较和转换能力。

	向量	字符串
比较	对 < 和 == 进行字典序比较元素，依赖于嵌入元素的比较操作，	使用 C“排序”函数进行字典序比较，使用当前区域设置并忽略大小写。
转换	从另一个向量转换，逐个元素，依赖于元素自身的转换（如果支持）。	仅通过 wcstombs 和反之亦然的 C 函数支持 char 和 whar_t 基于字符串之间的转换。
连接	未提供运算符。为此目的提供了 insert 函数。	insert 函数通过 + 和 += 运算符委托。

选择使用“忽略大小写排序”进行字符串比较，是因为我发现在我编写的大多数程序中，这是匹配列表中的字符串或将用户输入与数据集匹配的最常用函数。

当然，还可以使用其他任何字符串函数：字符串是空终止的，并且可以自动转换为 const T*，其中 T 是 char 或 wchar_t（以及 TCHAR）。

缓冲区存储方式也使得字符串大小存储在第一个字符之前，从而使其与 BSTR 兼容，尽管不是通过 OLE 分配的。

链式、串联和列表

自链接项可能需要作为复杂结构中的元素，其中算法可以分布在元素的成员函数中（而不是分布在迭代中）。

对于这类内容，STL 几乎不支持。

这里，两个配对类（linked 和 chain）用作基础来实现复杂链式复杂链接元素。这两个类都以派生类作为模板参数，linked 和 chain 用于这些派生类。

由于模板实例是不同的类型，同一个派生类可以从多个不同参数化的基类派生。因此，可以独立地拥有多个链的元素和多个元素的链。

linked 元素被认为是它所插入的 chain 所拥有的，并且它知道链和相邻元素。因此，可以实现递归算法作为成员函数，调用自身应用于 next()-> 或 prev()->，使这些结构适合于责任链实现。

chain 拥有 linked 元素，并在 clear 时执行静态 free 函数中定义的动作（它调用 delete，但可以被重写）。static_cast 用于从其递归模板基类引用派生元素。链也实现为可枚举的，因此 stdx::iterator<your_chain> 可以协同工作，解引用到链式元素。

列表然后只不过是 list_node<T> 的链，而 list_node<T> 本身是包含 T 值的节点框。类 list<T> 是一个 chain<list<T>, list_node<T> >，其中 list_node<T> 是一个 linked<list_node<T>, list<T> >。类 list 重写了 at 函数和 iterated_type，以便迭代器可以通过其自身可能特化的 dereference<T>::access 和类型解引用到 T。

此外，项目的插入和删除是根据 T 定义的，而不是根据项目本身。因此，类 list 对其节点进行混合，即使基于可见结构，也因此等同于 std::list，但与 STL 不同的是，它不是唯一可能的列表类型。

B树、节点、集合和映射

与列表类似，btree 实现了一个 btree_node 的 AVL 树，或者更确切地说，这两个类都是实现 B 树节点 B 树的基础。

与列表节点一样，B 树节点知道它们的所有者和逻辑邻居（prev 和 next 函数遍历节点的排序序列），但与列表节点不同的是，其值本身就是列表节点，B 树节点必须指定一种方法，让 B 树获取排序键和映射值。

这是通过在 btree_node 中重写 key_t 和 mapped_t，以及 get_key 和 get_mapped 函数来实现的。默认实现仅返回对节点本身的 const 引用，这些节点被期望在重写时是可比较的（支持 < 和 ==）。

就像我们使用 buffer 创建 vector 和 string，以及使用 chain 创建 list 一样，一些“调优”的 btree 是从这个类对派生出来的。

类 set 是一个 btree<set<T>,seet_node<T> >，其中 set_node 是 btree_node<set_node<T>,set<T> >：它承载 T 值并将其用作自身的键和映射值。它对应于 std::set。

类似地，map<K,V> 是一个 btree<map<K,V>, map_node<K,V> >，而 map_node 是一个 btree_node<map_node<K,V>, map<K,V> >，将 K 声明为 key_t，将 V 声明为 value_t。它还引入了 operator[](const K&)，在 const 模式下返回 const V&（如果找不到键则抛出），在非 const 模式下返回 V&（如果找不到则创建）。

与所有其他类一样，访问和解引用是通过特化 dereference 特性实现的，从而允许句柄或支持类似行为的类型（具有特化 stdx::dereference 的类型）的自解引用。

内存分配

对 alloc.cpp 中的固定分配管理器进行了广泛的链式元素和链的使用。它不过是另一篇文章中介绍的内容，只是使用这些集合模块重写了。

通过重写全局的 new 和 delete 运算符，低于给定大小的内存不会被查询操作系统，而是由管理器进行子分配，管理器反过来总是向系统请求固定大小的块。这在大量使用动态对象（可能通过句柄）的应用程序中非常有用，其中许多对象可能很小且寿命相对较短。

单元测试

演示这些类功能的简单单元测试包含在 T0A 项目中，该项目以静态库的形式访问这些类。

这些单元测试在调试模式下编译，以便于通过逐步执行跟踪，并在发布模式下编译，以便作为容器的性能测试。为了构建，这可能需要至少 1GB 的内存，因为会分配和释放数百万个对象来检查容器的功能。

由于这是一个非 STL 项目，因此使用了 printf 函数向屏幕输出。

结论

两个简单的想法（使用智能“句柄”而不是“指针”，以及使用可访问的构建块来构建容器）使 C++ 的运行方式更像其他垃圾回收语言，甚至可以使 STL 不再是必需的。

单元测试代码是关于如何实现这一点的绝佳示例。