ptr_vector - 指针容器

Roland Pibinger

4.74/5 (47投票s)

2004年6月9日

10分钟阅读

240819

1061

便捷的符合STL规范的指针容器。

下载源代码 + 测试 + 演示项目 - 137 Kb

引言

STL容器、迭代器和算法是为值设计的，而不是为对象设计的。当你尝试在标准容器（例如std::vector）中存储指针时，值语义就会显现出来。你会立刻感受到标准vector的值接口和存储的指针之间的“阻抗不匹配”。需要多一个*（解引用）才能访问被指向的对象。这尤其在处理算法时会很麻烦。

ptr_vector<T>是对标准vector<T*>的封装，它为迭代器和成员函数减少了一个间接层级。本质上，ptr_vector让你像处理值的vector一样处理指针的vector。在很多情况下，这正是你想要的。

如果你不熟悉STL，请参考CodeProject上的教程和初学者文章。

ptr_vector也可在Sourceforge上获取。

请参阅历史记录以了解代码和文章的最新更改。

背景

核心功能

ptr_vector实现为一个标准C++（STL）vector的封装器。
迭代器迭代的是被指向的对象，而不是指针。
迭代器是稳定的：当ptr_vector容器扩展时，ptr_vector迭代器保持有效（标准vector迭代器会失效）。
一些（即“右侧”）ptr_vector成员函数（operator[]、at()、front()、back()等）引用的是被指向的对象，而不是指针^[1]。
不依赖第三方库 - 仅
```
#include "ptr_vector.h"
```
ptr_vector<T>具有与标准vector<T*>相同的异常保证；成员函数提供无抛出或强异常保证。
ptr_vector对被指向的对象是非侵入性的（例如，它们不需要派生自共同的基类）。
前提条件：ptr_vector的指针不能是0或NULL。

[1] 更准确地说：将对象插入或从ptr_vector分离的成员函数具有“指针接口”，其余的则具有“值接口”。

与标准`vector`的比较

一段代码胜过千言万语。以下示例比较了

stdx::ptr_vector<T>（一个用于指向T类型对象的指针的新容器），
std::vector<T>（一个用于T类型对象的标准C++容器），以及
std::vector<T*>（一个用于指向T类型对象的指针的标准C++容器）。

以下三个代码片段将打印相同的结果

Hello, world! Hello, world! Hello, world!

stdx::ptr_vector<T>

ptr_vector<string> vec;
vec.push_back (new string ("Hello, "));
vec.push_back (new string ("world! "));

cout << vec[0]       << vec.at(1)
     << *vec.begin() << vec.begin()[1]
     << vec.front()  << vec.back();

std::vector<T>

vector<string> vec;
vec.push_back (string ("Hello, "));
vec.push_back (string ("world! "));

cout << vec[0]       << vec.at(1)
     << *vec.begin() << vec.begin()[1]
     << vec.front()  << vec.back();

std::vector<T*>

vector<string*> vec;
vec.push_back (new string ("Hello, "));
vec.push_back (new string ("world! "));

cout << *vec[0]       << *vec.at(1)
     << **vec.begin() << *vec.begin()[1]
     << *vec.front()  << *vec.back();

`ptr_vector<T>`相对于`vector<T>`的优势

ptr_vector不会不必要地复制对象，因此它也适用于实体对象（没有公共复制构造函数和赋值运算符的对象）。
可以容纳多态对象（例如Base和Derived对象）。
具有更好的异常保证（只复制指针，不复制被指向的对象）。
性能更好（只复制指针，不复制...）。
当ptr_vector扩展时，迭代器保持有效。

`ptr_vector<T>`相对于`vector<T*>`的优势

ptr_vector更方便；你的代码中看不到那么多星号（*），尤其是。
（STL）算法可以直接使用，无需特殊的内部解引用指针的比较对象。
在const ptr_vector<T>中，你无法更改被指向的对象（但在const vector<T*>中可以）。
当ptr_vector扩展时，迭代器保持有效。

`ptr_vector<T>`相对于`vector<T>`和`vector<T*>`的缺点

与vector<T*>::iterator和vector<T>::iterator相比，解引用ptr_vector<T>::iterator的效率略低。

`ptr_vector`的设计原则

ptr_vector不构造、复制、赋值、克隆或销毁任何被指向的对象。
你不会失去对被指向对象的控制。
这是什么意思？ptr_vector通常用于存储堆分配的对象（尽管它也可以包含全局或栈上对象）。ptr_vector不提供clear()和assign()等成员函数，这些函数在调用时会使（尤其是基于堆的）被指向的对象变得无法访问，除非你有一个指向它们的第二个指针容器（另见下文）。

成员函数概览

function	`std::vector`	`stdx::ptr_vector`	comment
`复制构造函数`	+	-	(1)
`operator=(), assign()`	+	-	(1) (2)
`begin(), rbegin()`	+	+	-
`end(), rend()`	+	+	-
`resize()`	+	-	(1)
`size(), max_size(), empty()`	+	+	-
`capacity(), reserve()`	+	+	-
`operator[], at()`	+	+	-
`front(), back()`	+	+	-
`push_back()`	+	+	-
`pop_back()`	+	+	(3)
`insert()`	+	+	-
`erase()`	+	-	(2) (4)
`detach()`	-	+	(4) (5)
`swap()`	+	+	(6)
`clear()`	+	-	(2)
`sort()`	-	+	(7)

注释:

设计原则1：ptr_vector不构造、复制、赋值、克隆或销毁被指向的对象。
设计原则2：ptr_vector不提供此函数，因为您会失去对被指向对象的控制。
ptr_vector::pop_back()移除最后一个元素并返回被移除对象的指针！
使用ptr_vector::detach()代替vector::erase()；因为vector::erase()返回一个指向第一个未被移除对象的迭代器，它违反了设计原则2。
ptr_vector::detach()从容器中移除一个或多个元素；被移除的元素会返回给调用者。
ptr_vector::swap()与ptr_vector<T>和vector<T*>交换元素。
ptr_vector::sort()通过交换指针来对被指向的对象进行排序。

您可以在API文档（参见下载）中获取有关ptr_vector成员函数的更多信息。

使用`ptr_vector_owner`进行资源管理和异常安全

ptr_vector_owner是一个可选的辅助类模板，一个作用域守卫，它拥有ptr_vector中动态创建的对象（按照设计，ptr_vector本身不了解被指向对象的拥有者）。

“拥有”意味着ptr_vector_owner在作用域结束时（在析构函数中）删除ptr_vector中所有被指向的对象。当然，只有当您使用new分配了被指向的对象时，才需要ptr_vector_owner。

示例

void myFunc()
{
  ptr_vector<string> ptv;
  ptr_vector_owner<string> owner (ptv); // scope-guard

  ptv.push_back (new string ("Once upon a time ..."));
  // ...

  if (something.isWrong())
    throw exception ("something real wrong!");
  // ...

  return;
} // pointed-to objects in ptv are deleted here!

上述函数以异常结束或在正常执行路径上返回。在这两种情况下，ptr_vector<string> ptv中的所有对象都会被ptr_vector_owner<string> owner删除。换句话说，ptr_vector_owner是著名的C++惯用法RAII的一个变种。

建议

尽可能优先使用ptr_vector_owner（或其他资源管理器）进行自动资源管理，而不是临时删除对象。
拥有者（作用域守卫）最适合作为类成员，因为在这种情况下，资源管理是封装的。对象无需用户干预即可进行资源管理，例如：

MyClass
{
public:
  MyClass(): mOwner (mPtv) {}
  // ...
private:
  ptr_vector<string> mPtv;
  ptr_vector_owner<string> mOwner; // scope-guard
};

使用代码

以下是一个完整的示例（也请参见下载）。为方便起见，使用了std::string类型的对象，但任何类（包括不可复制的类）都可以。

完整示例

#include <iostream>
#include <string>
#include "ptr_vector.h"

using namespace std;    // for cout, endl, find, replace, ...
using namespace stdx;   // for ptr_vector, ptr_vector_owner

int main()
{
   cout << "---- ptr_vector demo ----" << endl;

   ptr_vector<string> ptv;
   ptr_vector_owner<string> owner (ptv);  // scope-guard: owner of new-ed objects

   ptv.push_back (new string ("Peter"));
   ptv.push_back (new string ("Paul"));
   ptv.insert    (ptv.end(), new string ("Margaret"));

   cout << " 1: " << ptv.front()  << " " << ptv.back() << endl;
   cout << " 2: " << ptv[1]       << " " << ptv.at(2)  << endl;
   cout << " 3: " << *ptv.begin() << " " << *(ptv.begin() + 1) << endl;

   cout << " 4:";
   for (ptr_vector<string>::iterator it = ptv.begin(); it != ptv.end(); ++it)
      cout << " " << *it;
   cout << endl;

   ptv.sort();
   cout << " 5: " << ptv[0] << " " << ptv[1] << " " << ptv[2] << endl;

   ptv.sort (greater<string>());
   cout << " 6: " << ptv[0] << " " << ptv[1] << " " << ptv[2] << endl;

   ptr_vector<string>::iterator iter;
   iter = find (ptv.begin(), ptv.end(), "Paul");
   if (iter != ptv.end())
      cout << " 7: " << *iter << endl;

   replace (ptv.begin(), ptv.end(), string ("Paul"), string ("Fred"));
   cout << " 8: " << ptv.begin()[1] << endl;

   string* str = ptv.pop_back();
   cout << " 9: " << *str <<  " - size: " << ptv.size() << endl;
   delete str;

   delete ptv.detach (ptv.begin());
   cout << "10: " << ptv[0] << " - size: " << ptv.size() << endl;

   ptr_vector<string> ptvTwo;
   ptr_vector_owner<string> ownerTwo (ptvTwo);

   ptvTwo.push_back (new string ("Elisabeth"));
   ptvTwo.push_back (new string ("Susan"));
   ptv.swap(ptvTwo);
   if (ptv < ptvTwo)
      cout << "11: " << *ptv.begin() << " - size: " << ptv.size() << endl;

   return 0;
}

程序输出为

 ---- ptr_vector demo ----
  1: Peter Margaret
  2: Paul Margaret
  3: Peter Paul
  4: Peter Paul Margaret
  5: Margaret Paul Peter
  6: Peter Paul Margaret
  7: Paul
  8: Fred
  9: Margaret - size: 2
 10: Fred - size: 1
 11: Elisabeth - size: 2

`ptr_vector`和标准算法

问题

考虑以下示例

ptr_vector<MyClass> ptv;
ptr_vector_owner<MyClass> owner (ptv);
// insert elements into ptv ...
std::stable_sort (ptv.begin(), ptv.end()); // exchanges MyClass objects :(

stable_sort是一个标准算法，它对传递范围内的元素进行排序，同时保持等效元素的相对顺序。在上面的示例中，算法会低效地交换（可复制的）被指向的对象（MyClass对象）进行stable_sort。但它应该只交换指针！

这同样适用于所有重新排列序列的算法。没有有效的方法来改变标准算法的行为以达到期望的目的。ptr_vector，这个指针向量看起来像值向量，在这方面做得太好了。我们如何保留当前便捷的接口并且使标准算法与底层指针高效工作？

解决方案

修改后的示例

ptr_vector<MyClass> ptv;
ptr_vector_owner<MyClass> owner (ptv);
// insert elements into ptv ... 
stdx::stable_sort (ptv.begin(), ptv.end()); // exchanges pointers to
                                            // MyClass objects!

与上一个示例的区别很容易被忽略。这里使用了stdx命名空间中的stable_sort算法，而不是std命名空间中的算法。（ptr_vector也位于stdx命名空间中。）

实际上，stdx::stable_sort只是std::stable_sort的一个薄封装，它在底层做了“正确的事情”：它通过交换指针而不是被指向的对象来对序列进行排序。

`stdx`命名空间中的算法

封装的算法适用于指针迭代器，如ptr_vector::iterator。
只有重新排列元素序列的算法才被封装为“指针感知”。
非修改性算法，如std::find，没有被封装也无需封装，它们照常工作。
remove、remove_if和unique已为指针迭代器重新实现，因为标准实现不适用于这种情况下的指针（它们与值处理也不顺畅）。这些算法现在只重新排列元素，而不删除或覆盖任何元素。
封装以一种直接且统一的方式完成。通常，在将参数传递给底层标准算法之前，会增加一个间接层级。因此，可以假设封装的算法与它们封装的标准算法一样可靠。
封装算法列表
- swap_ranges,
- reverse,
- rotate,
- random_shuffle,
- partition,
- stable_partition,
- sort,
- stable_sort,
- partial_sort,
- nth_element,
- inplace_merge,
- push_heap,
- pop_heap,
- make_heap,
- sort_heap,
- next_permutation,
- prev_permutation
使用提示：排序算法要求为被指向的对象定义operator<，或者将Compare对象作为第三个参数传递。对于其他算法，可能需要operator==。在使用算法之前，请务必检查算法相对于被指向对象的要求。违反要求通常会导致STL臭名昭著的、无法理解的编译器错误消息。

兼顾双方之长

我们现在两者兼得，即底层仅仅重新排列指针的效率，以及表面上处理值的便捷性。标准算法的武器库可用于ptr_vector迭代器，无论是直接使用（对于不交换元素的算法），还是通过轻量级封装（对于重新排列的算法）。

高级用户可以通过使用类似标准迭代器特性背景下发明的编译时分派技术（参见单元测试示例）来编写适用于标准迭代器和指针迭代器的自定义算法。

关注点

单元测试

提供了一套针对ptr_vector、ptr_vector迭代器和算法的单元测试（参见下载）。它们不仅检查实现是否正确，还用作

如何使用ptr_vector进行编程的示例，以及
如果您想在新的编译器上使用ptr_vector或将其移植到新编译器时提供帮助（尽管已避免了有问题的模板构造，但仍可能出现编译器和标准库不兼容的情况）。

单元测试已被证明对于开发和重构手头代码以及模板代码的普遍情况是不可或缺的。通常，除非模板函数被实际实例化，否则编译器甚至不会执行（彻底的）语法检查。

优化

ptr_vector的实现基于标准C++vector。它在调试模式（Debug build）下使用vector<T*>，在发布模式（Release build）下使用vector<void*>作为基础容器。这避免了发布程序中模板的“代码膨胀”。请注意，ptr_vector的接口（包括迭代器）始终是强类型的。优化仅在内部进行。

编译器兼容性

单元测试已成功编译并运行于：

VC++ 6.0（特别是为VC++ 6.0实现了一些变通方法）
VC++.NET 7.1、8.0
BCC 5.5
GCC 3.2、3.4（Windows）；3.3、4.0（Linux）
使用Dinkum Exam在线的EDG编译器。

除了常见的兼容性问题外，ptr_vector应该可以在大多数，至少是相当符合标准的主流C++编译器和标准库上编译。如果您使用上面未列出的编译器成功编译了测试用例，请给我发邮件，特别是如果您遇到了编译时错误。顺便说一句，在C++标准化（1998年）多年后，编译器制造商（商业和非商业）仍在每次小版本更新中更改模板处理。仅此一点就表明C++模板机制存在严重问题。

历史记录

各种指针容器和迭代器已由库供应商和个人开发者制作，无论是否基于STL。例如：

由于C++标准缺乏指针容器，可能存在许多自制实现。

谢谢

非常感谢Andreas R.审阅本文，并使用VC++.NET 7.1编译了代码。

结论

ptr_vector的主要目的是让用户更方便地在类STL的容器中处理对象（指针）。ptr_vector<T>在接口和用法上都接近标准vector<T>——无需学习新的“范式”。封装的标准算法以便捷且快速的方式重新排列序列。ptr_vector_owner为正常情况和异常情况提供了一个易于使用的默认资源管理器。

在线资源

SGI上的“STL”网站（注意：只有STL的一部分被包含在C++标准中）。
Ulrich Breymann所著的“Designing Components with the C++ STL”，Addison Wesley Longman，2000年。免费下载可打印的PDF文件，也有德语版（注意：并非所有示例都可以在VC++ 6.0下 unmodified 工作）。

历史

2004年6月6日 - 提交至CodeProject
2004年12月16日 - 提交更新版本至CodeProject
- 代码
  - 为ptr_vector 迭代器实现了封装算法
  - 添加了封装算法的测试用例
  - 代码已清理
- 文章
  - 添加了“ptr_vector 和标准算法”章节
  - 文章已修订和清理
2005年3月14日 - 提交更新版本至CodeProject
- 代码
  - 由于GCC 3.4强制执行的新模板查找规则（2相名称查找），迭代器实现中移除了私有继承；此重构不影响“外部”行为
- 文章
  - 小的更改和修正
2006年10月21日 - 提交更新版本至CodeProject
- 代码
  - 使用较新编译器版本测试了代码
- 文章
  - 更新了无效链接
  - 小的更改和修正