12,896,953 members (51,364 online)
alternative version

#### Stats

36.4K views
11 bookmarked
Posted 24 Dec 2008

# triplet - An STL template to support 3D Vectors

, 24 Dec 2008 CPOL
 Rate this:
Adding support to STL for 3D Vectors

## Introduction

In the GIS/GPS world, we represent a position on Earth with three variables XYZ (for Earth centered coordinates) or latitude (phi) , longitude (lambda) and height (h) in polar (PLH) representation. Three-D graphic applications also requires processing of XYZ data. Creating such applications requires keeping track of the triplets of data.

When it comes to processing the triplet data, such as adding or removing coordinate points, or linking the points to form lines or polygons, and performing various geometrical calculations we inevitably need some sort of arrays or linked list. There are many methods that you could use eg: - `structs` or a 3-dimensional arrays as the container for the triplets or perhaps linked structure list depending on the requirements. Alternatively one can also use `CArray` or `CList` class. I believe these are fairly generic such that many commercial development environments support them.

Then there is the Standard Template Library (STL) which comes in many flavors. Popular libraries include STLPort and Boost. These template libraries provide excellent support for manipulation of vector and list data in a generic manner. In this article, when I refer to STL I mean STL in general - even though particular library(ies) does not support a certain style implementation.

Unfortunately, whilst STL containers such as `map<>`, `multimap<>` and `vector<>` makes processing of arrays easy, it is not easy to use as is. For example how do we create lists of XYZ coordinates using `map<>` or `vector<>`? The standard STL `vector<>` only provides for scalar or "1 variable" arrays and many articles available on the web illustrates creation of 1-dimensional arrays.

The next best thing is to use `struct` as a parameter for the STL `vector<>` - but then the `vector<>` template does not fully support `structs`. Back to square one. The only way is to use the `pair<>` template in conjunction with the `vector<>` to create multi-pairs `pairs<>` to achieve n-dimensions> Otherwise you have to create your own `struct` STL template.

This article is not about which algorithm or library has a better data structure or better algorithm, but to present an alternative to existing methodology in relation to storing and processing of triplet data such as geographical coordinates above.

Here I shall present the use of the `"triplet<>"` template which I created for use with the Standard Template Library (STL) to support such 3D vectors. ("triplet" is an STL template adapted from VS2008 and STLPort templates - see note at end of article). The triplet template is a specialized template that extends the `vector<>` and `map<>` templates and is compatible with MS's or STLPort's libraries.

There are some comprehensive and powerful STL libraries that supports n-dimensional arrays such as Boost. You have to download megabytes and then spend some time in figuring out the build options and then a couple of hours letting it compile/build. If you only need a few containers and not all the Boost's features, then it is too much bloat.

## Simulating Multi-Dimension Arrays Using Pair<> Template

```// 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```

There are quite a number of ways to provide support for XYZ coordinates using STL:

1. make XYZ into strings and store them as a list of strings (messy & huge programming overhead)
2. store XYZ as arrays (not much better than normal array)
3. create an array of XYZ and store pointers to the XYZ array

The outline code below illustrates these methods.

In the examples and code below I shall use XYZ to mean coordinate (X,Y,Z). The units could be in feet, meters, kilometers, etc.

## Storing as Strings

```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++)
{

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 ...
}```

## Storing as Values

```// 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 ...
}```

## Storing as Pointers to an Array

```vector<double* /> 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]);
}```

The above shows three very simple methods that enable us to use STL to provide support for 3D vectors - such as XYZ coordinates. However, the code looks horrible and is difficult to maintain. The most efficient of the above is the third method (storing as pointers to an array), but it comes at a price! In the 3rd example above, the `dArray[]` is created as a static allocation. If you need dynamic allocation, you have to manage the allocation/destruction of your coordinate array dynamically. In addition you have to be careful of referential integrity.

If you use a linked list instead of an array to store your coordinates, then there is quite a high probability that you will hit the referential integrity problem. Consider if you have implemented your coordinate array as a linked list, then sort the list, the `vector<>` which you previously created may not point to the correct sequence of your link list elements. Another potential source of problem is when you delete the elements from the array and forget to delete the `vector<>` pointer. You have to perform messy manual synchronization between the linked list and the `vector<>` container.

Of course you can create a `Class` to provide support for 3D vectors, but then you will need quite a number of overloaded functions to cater for a mix of variable types if you want it to be generic and re-usable. Again this is not an attractive option although feasible. So templates are the way to go.

For a long time I have been using MS `CArray and CList` Classes and they are not well documented and this is my chance of jumping out! Writing a new `Class` from scratch will take too much time not to mention of portability issues. Thus I decided to write a 3D vector/array support for STL.

There are many variants of STL. Microsoft's STL does not supports multi-dimension arrays natively and so too STLPort. I believe that Boost's version 5.20 supports multi-dimension arrays (maybe even earlier version, but this is the first time I am looking at STL - I am still a beginner in STL!). Boost supports multi-dimension arrays - in this case 3 dimensions. However, Boost lacks the certain features that STLPort possess. All I needed was some quick and simple code. So "`triplet<>`" template was born!

I shall not go into the details of the `triplet<>` template code itself in this article, rather I shall illustrate the use of the template instead. The template code is provided in the above download link so you can peruse it at your own leisure.

## The triplet<> Template

I am using Microsoft Visual Studio 2008 (MS) so there may be references specific to this tool. I am not familiar with Linux nor GCC so I shall not discuss them. But suffice to say the `triplet<>` template should work with any STLPort v5.2.0 environment. There are two versions of `triplet`<> - one for MS and one for STLPort. If there is time I may release a version suitable for BOOST at a later date (but may defeat the purpose of Boost's n-dimensional templates). The template code is different for the MS STL and STLPort, but the usage is the same:

1. Include the `triplet<>` template
2. Use `namespace std`
3. Declare your vector eg` vector< triplet<int,int,int> > myIntVector;`
4. Enter values into vector via `myIntVector.push_back (make_triplet(...))`

Thats it! There are only 2 functions to remember - `triplet<>` and `make_triplet<>`. The rest of the `vector<>` functionality is provided by the base class itself and supporting routines like sort are provided for by the standard library.

```#include <span class="code-keyword"><map></span>
#include <span class="code-keyword"><vector></span>
#include <span class="code-keyword"><iostream></span>
#include <span class="code-string">"triplet"	// This is the triplet template</span>
// 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;```

The above code snippet shows usage of 3D vector of type `double`. It is much cleaner. The use of `first, second` and `third` to reference X,Y,Z makes the program more readable.

In essence you can also use it for `int, bytes, words, long int, bools` and `chars`. The only type it does not yet support is `strings`. It will certainly be nice to do things like:

```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") );```

I shall look into this again when I have some time.

The next step is to add support for GPS trackpoints (latitude, longitude, height and time) for GPS tracking. This is easy to do as you can enhance the `triplet<>` template to create your own `quad<>` template. I shall release this in future if there is demand for it.

## Performance

In a test of 50,000 loops of 10,000 vector allocations and retrievals (done separately), the results are as follows:

 Release Build: Vector Type AllocationTime RetrievalTime: viaoper[] RetrievalTime: viaiterator MS STL `vector` 7 1 6 `vector>` 19 8 26 STLPort `vector` 7 0 0 `vector>` 6 0 0
* All above timings are in seconds (resolution is 1 second). Above tests were from an Athlon XP 2400 cpu.

The sample code includes a routine to perform the timing test above. In MS STL implementation, there is a substantial performance penalty to be paid for using the `triplet<>` code! But this is not so in the STLPort's implementation of `triplet<>`. The timings are almost identical whether you use `triplet<>` or `vector<double *>.`

At this moment, `triplet<>` is still new to myself and I have not had the time to benchmark some real world applications as yet. I would certainly appreciate if anyone who use the `triplet<> `template post some real-world timing data.

## Background

I have created lots of linked lists and vector based code through a few years of programming. Not only were they non-portable, they were also tightly optimized into the application. Until recently when I came across some STL articles, read it and realize that STL is an extremely useful tool. I thought that its about time I made my code more portable and thus reducing the maintenance burden.

Although STL is useful, there were a few features that I really wanted but did not have. I needed support for 3D (x,y,z) and 4D (x,y,z,t) vectors which could only be created indirectly in STL - using either the `map<>`, `multimap<>` and `vector<>` templates in conjunction with `pair<>` template. The `pair<>` template requires the creation of extra filler value (when the array dimension is odd) which I did not like. In addition, the code to retrieve the (x,y,z) values gets more convoluted as the dimension increases.

So, I thought why not create my very own 3D vector template? I then looked at the VS2008 STL map and vector templates code. Its frightening to look at template sources - especially for a beginner! Then I realize that what I really needed was a `triplet<>` template and that would solve the problem.

## Using the Code

Refer to "The `triplet<>` template" above section for usage example.

## Points of Interest

It was surprisingly easy to modify the `pair<>` template to become a `triplet<>` template. It would have taken me very much longer if I had to create a new `Class` or just write code to perform link list operations. I think this is an avenue many developers seem to miss. Instead of writing new `Class`, why not write supporting templates? I know there are some potential dangling and null pointers in my older code that I know have a very small probably being triggered - the `triplet<>` will be a good replacement.

## Notes

The `triplet<>` template was derived from the `pair<>` and `utility<>` templates in VS2008 and STLPort. Required member template functions were extracted and enhanced to support 3D vectors. Additional code were written where required. The original `pair<>` and `utility<>` templates style and structure was maintained as far as possible in the `triplet<>` template to allow easy maintenance and cross referencing.

`Triplet<>` is open source. You may use it wherever you wish. However, since this code was derived from MS and STLPort, you may have to consult them for commercial distribution. However, a note crediting me as the author of the `triplet<>` template would be nice.

## History

2008-12-22 - Ver 1.0
Adapted triplet<> from pair<> template found in the file "utility" from VS2008.
Adapted _pair.h file from STLPort v5.20

2008-12-24 - Ver 1.1
Fixed predicate functions `TripletCompareAscending231()` and `TripletCompareAscending321()`
to return true only when strictly "less than" to satisfy MS requirements for strict weak ordering. This will
prevent MS from runtime abort.

## Share

 Malaysia
No Biography provided

## You may also be interested in...

 Pro

 First Prev Next
 vector vArray2d; // Funny! .Shoaib13-Jun-10 21:38 .Shoaib 13-Jun-10 21:38
 tuple jlatorref13-Jul-09 21:33 jlatorref 13-Jul-09 21:33
 Re: tuple Mick Leong19-Jul-09 21:26 Mick Leong 19-Jul-09 21:26
 Re: tuple jlatorref20-Jul-09 0:11 jlatorref 20-Jul-09 0:11
 Re: tuple Mick Leong20-Jul-09 21:00 Mick Leong 20-Jul-09 21:00
 Don't be discouraged by some negative responses. wtwhite2-Jan-09 14:49 wtwhite 2-Jan-09 14:49
 Re: Don't be discouraged by some negative responses. Mick Leong19-Jul-09 21:19 Mick Leong 19-Jul-09 21:19
 My vote of 1 paulmcq31-Dec-08 7:11 paulmcq 31-Dec-08 7:11
 My vote of 1 Bernard Gressing30-Dec-08 15:14 Bernard Gressing 30-Dec-08 15:14
 My vote of 1 Jon Summers29-Dec-08 23:42 Jon Summers 29-Dec-08 23:42
 std::vector Jon Summers29-Dec-08 23:42 Jon Summers 29-Dec-08 23:42
 valarray LotharLanger27-Dec-08 1:21 LotharLanger 27-Dec-08 1:21
 Re: valarray Mick Leong29-Dec-08 20:36 Mick Leong 29-Dec-08 20:36
 Re: valarray LotharLanger4-Jan-09 0:17 LotharLanger 4-Jan-09 0:17
 Better solution gfaraj24-Dec-08 21:25 gfaraj 24-Dec-08 21:25
 Re: Better solution [modified] User of Users Group25-Dec-08 1:42 User of Users Group 25-Dec-08 1:42
 Re: Better solution Mick Leong29-Dec-08 20:54 Mick Leong 29-Dec-08 20:54
 Re: Better solution the.Kris29-Dec-08 23:42 the.Kris 29-Dec-08 23:42
 Re: Better solution Mick Leong19-Jul-09 21:30 Mick Leong 19-Jul-09 21:30
 Re: Better solution Mick Leong20-Jul-09 21:08 Mick Leong 20-Jul-09 21:08
 Re: Better solution the.Kris21-Jul-09 1:15 the.Kris 21-Jul-09 1:15
 Re: Better solution Stefan6329-Jan-09 22:59 Stefan63 29-Jan-09 22:59
 Re: Better solution Mick Leong19-Jul-09 21:36 Mick Leong 19-Jul-09 21:36
 Last Visit: 31-Dec-99 18:00     Last Update: 29-Apr-17 18:11 Refresh 1