triplet - An STL template to support 3D Vectors

• Download demo project - 19.77 KB
• Download source - 15.87 KB

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++)
{
    // 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 ...
}

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 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 <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;

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	Allocation Time	Retrieval Time: via oper[]	Retrieval Time: via 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

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.