65.9K
CodeProject 正在变化。 阅读更多。
Home

triplet - 支持 3D 向量的 STL 模板

Mick Leong
starIconstarIcon
emptyStarIcon
starIcon
emptyStarIconemptyStarIcon

2.57/5 (5投票s)

2008 年 12 月 24 日

CPOL

10分钟阅读

viewsIcon

57463

downloadIcon

392

为 STL 添加 3D 向量支持。

引言

在 GIS/GPS 领域，我们通常用三个变量 XYZ（用于地心坐标）或极坐标（PLH）表示地球上的一个位置（纬度（phi）、经度（lambda）和高度（h））。三维图形应用程序也需要处理 XYZ 数据。创建此类应用程序需要跟踪数据的三元组。

在处理三元组数据时，例如添加或删除坐标点、将点连接成线或多边形，以及执行各种几何计算，我们不可避免地需要某种形式的数组或链表。您可以使用许多方法，例如：- 结构体 或三维数组作为三元组的容器，或者根据需求使用链式结构列表。或者，您也可以使用 CArray 或 CList 类。我认为这些相当通用，许多商业开发环境都支持它们。

然后是标准模板库（STL），它有很多变体。流行的库包括 STLPort 和 Boost。这些模板库以通用的方式为向量和列表数据的操作提供了出色的支持。在本文中，当我提到 STL 时，我指的是一般的 STL — 即使某些特定的库不支持某种风格的实现。

不幸的是，虽然 STL 容器如 map<>、multimap<> 和 vector<> 使数组处理变得容易，但它们本身并不容易使用。例如，我们如何使用 map<> 或 vector<> 创建 XYZ 坐标列表？标准的 STL vector<> 只提供标量或“单变量”数组，并且网上许多文章都展示了如何创建一维数组。

其次是使用 struct 作为 STL vector<> 的参数 — 但然后 vector<> 模板并不完全支持 structs。回到原点。唯一的方法是结合使用 pair<> 模板和 vector<> 来创建多对 pairs<> 来实现 n 维。否则，您必须创建自己的 struct STL 模板。

本文并非讨论哪个算法或库拥有更好的数据结构或算法，而是介绍一种存储和处理三元组数据（如上述地理坐标）的替代方法。

这里我将介绍我为使用标准模板库（STL）支持此类 3D 向量而创建的 "triplet<>" 模板的使用。（“triplet”是根据 VS2008 和 STLPort 模板改编的 STL 模板 — 请参阅文章末尾的注释）。triplet 模板是一个专门的模板，它扩展了 vector<> 和 map<> 模板，并且与 MS 或 STLPort 的库兼容。

有一些全面的、强大的 STL 库支持 n 维数组，例如 Boost。您需要下载几兆字节的数据，然后花一些时间弄清楚构建选项，然后再花几个小时来编译/构建。如果您只需要几个容器而不是 Boost 的所有功能，那么这会导致过多的臃肿。

使用 Pair<> 模板模拟多维数组

// Single dimension vector example
vector<double> vArray1d;

// 2-dimensional array
// Declaring vector as:
vector<double,double> vArray2d;		//error!
// will cause the compiler to spew out! Because vector<> does not support
// multi-dimensions natively except through template

// You need to enlist the services of the pair<> template as follows:
vector< pair<double,double> > vArray2d;
double x1, x2;
vArray2d.push_back ( make_pair(x1,x2) );
// And to access the values
x1 = vArray2d[id].first;
x2 = vArray2d[id].second;

// 4-dimensional array
// make a pair out of two pairs! //punny?
// This is messy code!
vector< pair< pair<double,double>, pair<double,double> > > vArray4d; 
double x1, x2, x3, x4;
vArray4d.push_back ( make_pair( make_pair(x1,x2), make_pair(x3,x4) ) );
// And to access the values
x1 = vArray4d[id].first.first;
x2 = vArray4d[id].first.second;
x3 = vArray4d[id].second.first;
x4 = vArray4d[id].second.second;

// Even dimension arrays are easy, but odd dimension arrays?
// For odd dimension arrays we have to use a filler variable - to make pair<> happy
// Example: for a 3D array, we create a 4D array and "ignore" one of the variables
// Eaxmple of a 3-dimensional array using pair<> construct
vector< pair< pair<double,double>, pair<double,double> > > vArray3d; 
double x1, x2, x3, dummy;
vArray3d.push_back ( make_pair< make_pair(x1,x2), make_pair(x3,dummy) );

// As the dimension gets higher, the code gets more unwieldy, not to mention the accessor
// code which is even more confusing

有相当多的方法可以使用 STL 为 XYZ 坐标提供支持

  1. 将 XYZ 转换为字符串并将其存储为字符串列表（混乱且编程开销巨大）
  2. 将 XYZ 存储为数组（与普通数组相比没有太大优势）
  3. 创建一个 XYZ 数组并存储指向 XYZ 数组的指针

下面的概述代码说明了这些方法。

在下面的示例和代码中，我将使用 XYZ 来表示坐标（X、Y、Z）。单位可以是英尺、米、公里等。

存储为字符串

vector<string> vXYZStr;

// Creating the vector list
double X, Y, Z;
TCHAR szXYZ[30];
string strXYZ;
// Put the XYZ coordinates into a list and store the list
// But this will burden the processing - extracting the XYZ back out from the strings
// Problems:
// - sorting is almost impossible
// - precision loss in conversion to/from string operations
for ( int i=0; i<NoCoords; i++)
{
    // read XYZ ...
    sprintf (szXYZ, "%lf %lf %lf", X, Y, Z);
    strXYZ = szXYZ;
    vXYZStr.push_back (szXYZ);
}

// Extracting the XYZ
for ( int i=0; i<NoCoords; i++ )
{
    szXYZ = vXYZStr[i];
    sscanf ("%lf %lf %lf", &X, &Y, &Z);
    ... process XYZ ...
}

存储为值

// Using pair<> template to store the XYZ coords - this is terrible!
vector< pair< pair<double,double>, pair<double,double> > > vXYZ;

// Because we use the pair<> template, we must have an even number of values
// so a filler value is required. (variable t)
double X, Y, Z, t;	//	t is a filler variable
for (int i=0; i<=NoCoords; i++)
{
    ... read/get XYZ from somewhere ...
        vXYZ.push_back ( make_pair( make_pair(X,Y), make_pair(Z,t) ) );
}

// Accessing the variables XYZ is messy and hard to read
for ( int idx=0; idx<=1 ; idx++)
{
    X = ComplexVector[idx].first.first;	//first pair, first value
    Y = ComplexVector[idx].first.second;	//first pair, second value 
    Z = ComplexVector[idx].second.first;	//second pair, first value

    //in case you have use for the filler value
    t = ComplexVector[idx].second.second;	//second pair, second value
    ... process XYZ ... 
}

// You can also make use of the "spare" filler value as the Coordinate ID or number:
int id;
vXYZ.push_back ( make_pair( make_pair(id,X), make_pair(Y,Z) ) );
// in which case you will retireve the data as follows:
for ( int idx=0; idx<=1 ; idx++)
{

    id = ComplexVector[idx].first.first;	//first pair, first value
    X = ComplexVector[idx].first.second;	//first pair, second value 
    Y = ComplexVector[idx].second.first;	//second pair, first value
    Z = ComplexVector[idx].second.first;	//second pair, second value
    ... do something with the XYZ ...
}

存储为数组的指针

vector dVector<double *>;
#define VECTOR_SIZE 1000	//static 
double dArray[VECTOR_SIZE][3];
for ( int idx=0; idx<=NoOfCoordinates ; idx++)
{
    // initialize the coordinate array
    dArray[i][0] = i+0.1;
    dArray[i][1] = i+0.2;
    dArray[i][2] = i+0.3;
    // store pointer to the array into vector container
    dVector.push_back (&dArray[i][0]);
}

以上展示了三种非常简单的方法，使我们能够使用 STL 来支持 3D 向量 — 例如 XYZ 坐标。然而，代码看起来很糟糕，并且难以维护。以上方法中最有效的是第三种方法（存储为数组的指针），但这需要付出代价！在上面的第三个示例中，dArray[] 是作为静态分配创建的。如果您需要动态分配，则必须动态管理坐标数组的分配/销毁。此外，您还必须注意引用完整性。

如果您使用链表而不是数组来存储坐标，那么很可能会遇到引用完整性问题。考虑一下，如果您已将坐标数组实现为链表，然后对列表进行排序，那么您之前创建的 vector<> 可能不再指向链接列表元素的正确顺序。另一个潜在的问题来源是当您从数组中删除元素时，忘记删除 vector<> 指针。您必须在链表和 vector<> 容器之间执行混乱的手动同步。

当然，您可以创建一个 Class 来支持 3D 向量，但是如果您希望它具有通用性和可重用性，则需要大量的重载函数来处理混合变量类型。这同样不是一个有吸引力的选项，尽管可行。所以模板是正确的选择。

长期以来，我一直在使用 MS CArray 和 CList 类，它们文档不完善，这是我跳出的机会！从头开始编写新的 Class 将花费太多时间，更不用说可移植性问题了。因此，我决定为 STL 编写一个 3D 向量/数组支持。

STL 有许多变体。Microsoft 的 STL 不支持多维数组，STLPort 也不支持。我相信 Boost 的 5.20 版本支持多维数组（可能更早的版本，但这是我第一次接触 STL — 我仍然是 STL 的初学者！）。Boost 支持多维数组 — 在本例中是 3 维。然而，Boost 缺乏 STLPort 所拥有的某些功能。我只需要一些快速简单的代码。所以“triplet<>”模板应运而生！

在本文中，我将不深入探讨 triplet<> 模板代码本身，而是说明该模板的使用。模板代码已包含在上面的下载链接中，您可以随时查阅。

triplet<> 模板

我使用的是 Microsoft Visual Studio 2008（MS），因此可能有一些特定于此工具的引用。我不熟悉 Linux 或 GCC，因此我将不讨论它们。但可以肯定的是，triplet<> 模板应该适用于任何 STLPort v5.2.0 环境。triplet<> 有两个版本 — 一个用于 MS，一个用于 STLPort。如果时间允许，我可能会在以后发布一个适用于 BOOST 的版本（但这可能会违背 Boost 的 n 维模板的目的）。MS STL 和 STLPort 的模板代码不同，但用法相同。

  1. 包含 triplet<> 模板
  2. 使用 namespace std
  3. 声明您的向量，例如 vector< triplet<int,int,int> > myIntVector;
  4. 通过 myIntVector.push_back (make_triplet(...)) 将值添加到向量中

就是这样！只有 2 个函数需要记住 — triplet<> 和 make_triplet<>。其余的 vector<> 功能由基类本身提供，而排序等支持例程则由标准库提供。

#include <map>
#include <vector>
#include <iostream>
#include "triplet"	// This is the triplet template
// Use #include "triplet" if you put the template into you project folder
// or use #include <triplet> if you put the template into your VS "include" folder

using namespace std;	// triplet<> also uses std namespace to be consistent

main ()
{
    TestTriplet();
}

void TestTriplet()
{
    vector<triplet>< triplet<double,double,double> > Vector3d;

    cout << "Generating vectors using triplet<>:" << endl;

        double x = 1.1;
    double y = 1.2;
    double z = 1.3;
    int NoOfCoords = 5;

    for ( int id=0; id<NoOfCoords; id++)
    {
        cout << "\tVector[" << id << "]"
            << "\tx=" << x 
            << "\ty=" << y 
            << "\tz=" << z 
            << endl;
        Vector3d.push_back ( make_triplet(x, y, z) );
        // Alternatively you can use:
        // triplet<double,double,double> CoordXYZ;  //define this before the loop starts
        // CoordXYZ.first = x;
        // CoordXYZ.second = y;
        // CoordXYZ.third = z;
        // Vector3d.push_back ( CoordXYZ );
        // increment by 1 to make it easily identifiable
        x += 1;
        y += 1;
        z += 1;
    }
    //
    // Retrieve the generated vectors using oper[]
    //
    cout << "Retrieving data via operator []:" << endl;
    for ( idx=0; idx<NoOfCoords; idx++)
    {
        // The accessor code is very much more readable and easier to maintain.
        cout << "\tVector[" << idx << "]"
            << "\tx=" << Vector3d[idx].first 
            << "\ty=" << Vector3d[idx].second 
            << "\tz=" << Vector3d[idx].third 
            << endl;
    }
    cout << endl;

    //
    // Retrieve the generated vectors using iterator
    //
    cout << "Retrieving data via iterator:" << endl;
    vector<triplet>< triplet<double,double,double> >::iterator Vector3d_Iter;
    Vector3d_Iter = Vector3d.begin();
    int idx = 0;
    while ( Vector3d_Iter != Vector3d.end() )
    {
        // The accessor code is very much more readable and easier to maintain. 
        // Compared to using vector< pair< pair<double,double>, pair<double,double> > >

        cout << "\tVector[" << idx << "]"
            << "\tx=" << Vector3d_Iter->first 
            << "\ty=" << Vector3d_Iter->second 
            << "\tz=" << Vector3d_Iter->third 
            << endl;
        idx ++;
        Vector3d_Iter++;
    }
    cout << endl;

上面的代码片段展示了 double 类型 3D 向量的使用。它更简洁。使用 first, second 和 third 来引用 X、Y、Z 使程序更具可读性。

本质上，您也可以将其用于 int, bytes, words, long int, bools 和 chars。唯一尚不支持的类型是 strings。做类似的事情肯定很好

vector< triplet<double,double,string> > Vector3d;

Vector3d.push_back ( make_triplet (X,Y, "Front of house") );
Vector3d.push_back ( make_triplet (X,Y, "Archeological treasure!") );
Vector3d.push_back ( make_triplet (X,Y, "End of road") );

等我有时间再来看看。

下一步是为 GPS 轨迹点（纬度、经度、高度和时间）添加支持以进行 GPS 跟踪。这很容易做到，因为您可以增强 triplet<> 模板来创建您自己的 quad<> 模板。如果需求旺盛，我将来会发布它。

性能

在一项包含 50,000 次循环、10,000 次向量分配和检索（分别进行）的测试中，结果如下：

发布版本
向量类型 分配
时间		 检索
时间：通过
oper[]		 检索
时间：通过
iterator
MS STL
vector<double*> 7 1 6
vector<triplet<double,double,double>> 19 8 26
STLPort
vector<double*> 7 0 0
vector<triplet<double,double,double>> 6 0 0
* 以上所有计时均以秒为单位（分辨率为 1 秒）。以上测试来自 Athlon XP 2400 CPU。

示例代码包含一个执行上述计时测试的例程。在 MS STL 实现中，使用 triplet<> 代码会产生显著的性能损失！但在 STLPort 的 triplet<> 实现中并非如此。使用 triplet<> 或 vector<double *> 时的计时几乎相同。

目前，triplet<> 对我来说仍然是新的，我还没有时间测试一些实际应用。如果您使用 triplet<> 模板，我非常希望您能发布一些实际的计时数据。

背景

经过几年的编程，我编写了大量的链表和基于向量的代码。它们不仅不可移植，而且被紧密地优化到应用程序中。直到最近，当我看到一些 STL 文章时，我才意识到 STL 是一个极其有用的工具。我认为是时候让我的代码更具可移植性，从而减轻维护负担了。

尽管 STL 有用，但有些功能我非常想要但却没有。我需要支持 3D (x,y,z) 和 4D (x,y,z,t) 向量，而这些在 STL 中只能间接创建 — 通过使用 map<>、multimap<> 和 vector<> 模板与 pair<> 模板结合使用。pair<> 模板需要创建额外的填充值（当数组维度是奇数时），我不喜欢这样。此外，检索 (x,y,z) 值的代码随着维度的增加而变得更加复杂。

所以，我想为什么不创建我自己的 3D 向量模板呢？然后我查看了 VS2008 的 STL map 和 vector 模板代码。查看模板源代码是一件令人恐惧的事情 — 尤其是对于初学者！然后我意识到我真正需要的是一个 triplet<> 模板，它将解决这个问题。

Using the Code

请参阅上面“The triplet<> template”部分以获取用法示例。

关注点

将 pair<> 模板修改为 triplet<> 模板出奇地容易。如果我必须创建一个新的 Class 或编写代码来执行链表操作，那将花费我更长的时间。我认为这是一个许多开发人员似乎错过的途径。与其编写新的 Class，为什么不编写支持模板呢？我知道我的旧代码中可能存在一些悬空指针和空指针，但我知道触发它们的可能性非常小 — triplet<> 将是一个很好的替代品。

注释

triplet<> 模板源自 VS2008 和 STLPort 中的 pair<> 和 utility<> 模板。提取并增强了所需的成员模板函数以支持 3D 向量。在需要的地方添加了额外的代码。尽可能在 triplet<> 模板中保留了原始的 pair<> 和 utility<> 模板的风格和结构，以便于维护和交叉引用。

Triplet<> 是开源的。您可以在任何您想使用的地方使用它。但是，由于此代码源自 MS 和 STLPort，因此您可能需要咨询他们以获取商业发行。但是，如果您能以作者身份注明 triplet<> 模板，那将是对我的一种认可。

历史

2008-12-22 - Ver 1.0
从 VS2008 文件“utility”中的 pair<> 模板改编 triplet<>。
改编 STLPort v5.20 的 _pair.h 文件

2008-12-24 - Ver 1.1
修复了谓词函数 TripletCompareAscending231() 和 TripletCompareAscending321()
仅当严格“小于”时才返回 true，以满足 MS 对严格弱序的要求。这将
防止 MS 在运行时中止。

© . All rights reserved.