ptr_vector - A Container For Pointers

• Download source + test + demo project - 137 Kb

Introduction

STL containers, iterators and algorithms are designed for values, not objects. The value semantics becomes evident when you try to store pointers in a Standard container, e.g., in a std::vector. You immediately feel the "impedance mismatch" between the Standard vector value interface and the stored pointers. One extra * (dereference) is necessary to reach the pointed-to objects. This is annoying especially when you use algorithms.

ptr_vector<T> is a wrapper for Standard vector<T*> that cuts one level of indirection for iterators and member functions. In essence, ptr_vector lets you treat a vector of pointers as if it were a vector of values. In many cases, this is exactly what you want.

If you are not familiar with STL, take a look at the Tutorials and Beginners articles at CodeProject.

ptr_vector is also available from Sourceforge.

See History for recent changes to code and article.

Background

Core Features

• ptr_vector is implemented as a wrapper for the Standard C++ (STL) vector.
• iterators iterate over pointed-to objects, not pointers.
• iterators are stable: ptr_vector iterators remain valid when the ptr_vector container expands (Standard vector iterators become invalid).
• some (i.e., the 'right') ptr_vector member functions (operator[], at(), front(), back(), ...) refer to pointed-to objects, not pointers ^[1].
• no dependency on third party libraries - just:

  #include "ptr_vector.h"

• ptr_vector<T> has the same exception guarantees as Standard vector<T*>; member functions provide the no-throw or the strong exception guarantee.
• ptr_vector is non-intrusive for pointed-to objects (e.g., they don't need to derive from a common base class).
• precondition: pointers for ptr_vector must not be 0 or NULL.

[1] To be more precise: Member functions that insert objects into or detach objects from ptr_vector have a 'pointer interface', the rest have a 'value interface'.

Comparison To Standard vectors

One piece of code is worth a thousand words. The following example compares:

1. stdx::ptr_vector<T> (a new container for pointers to objects of type T),
2. std::vector<T> (a Standard C++ container for objects of type T), and
3. std::vector<T*> (a Standard C++ container for pointers to objects of type T).

The three code snippets below print the same result:

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

1. 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();

2. 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();

3. 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();

Advantages of ptr_vector<T> compared to vector<T>

• ptr_vector does not copy objects unnecessarily, therefore it is also suitable for entity-objects (objects without a public copy constructor and assignment operator).
• can hold polymorphic objects (e.g., Base and Derived objects).
• has far better exception guarantees (only pointers are copied, not pointed-to objects).
• performs much better (only pointers are copied, not ...).
• iterators remain valid when ptr_vector expands.

Advantages of ptr_vector<T> compared to vector<T*>

• ptr_vector is more convenient; you don't see so much stars (*) in your code, especially.
• (STL) algorithms can be used directly without a special compare object that dereferences pointers internally.
• you cannot change a pointed-to object in a const ptr_vector<T> (you can change pointed-to objects in a const vector<T*>).
• iterators remain valid when ptr_vector expands.

Disadvantage of ptr_vector<T> compared to vector<T> and vector<T*>

• dereferencing an iterator is slightly less efficient for ptr_vector<T>::iterator compared to vector<T*>::iterator and vector<T>::iterator.

Design Principles of ptr_vector

1. ptr_vector does not construct, copy, assign, clone, or destroy any pointed-to objects.
2. You don't lose control of pointed-to objects.

   What does this mean? ptr_vector is often used to hold heap-allocated objects (although it can also contain global or stack-based objects). ptr_vector does not offer member-functions like clear() and assign() that would make (especially heap-based) pointed-to objects inaccessible when invoked unless you have a second container of pointers (see also below).

Member Function Overview

Comments:

1. Design Principle 1: Pointed-to objects are not constructed, copied, assigned, cloned, or destroyed by ptr_vector.
2. Design Principle 2: This function is not provided for ptr_vector because you would lose control of pointed-to objects.
3. ptr_vector::pop_back() removes the last element and returns a pointer to the removed object!
4. Use ptr_vector::detach() as substitute for vector::erase(); since vector::erase() returns an iterator to the first object not removed, it violates Design Principle 2.
5. ptr_vector::detach() removes one or more element(s) from the container; the removed elements are passed back to the caller.
6. ptr_vector::swap() exchanges elements with ptr_vector<T> and vector<T*>.
7. ptr_vector::sort() sorts pointed-to objects by swapping pointers.

You can get more information about ptr_vector member functions from the API documentation (see download).

Resource Management And Exception Safety With ptr_vector_owner

ptr_vector_owner is an optional helper class template, a scope-guard, that takes ownership of dynamically created objects in ptr_vector (by design, ptr_vector itself does not know anything about the owner(s) of the pointed-to objects).

'Ownership' means that ptr_vector_owner deletes all pointed-to objects in a ptr_vector when it goes out of scope (in its destructor). Of course, you only need ptr_vector_owner when you have allocated your pointed-to objects with new.

Example:

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!

The above function ends with an exception or returns on the regular path of execution. In both cases, all objects in ptr_vector<string> ptv are deleted by ptr_vector_owner<string> owner. In other words, ptr_vector_owner is a variant of the well known C++ idiom called RAII.

Recommendations:

• Prefer automatic resource management with ptr_vector_owner (or another resource manager) to ad-hoc deletion of objects whenever possible.
• Owners (scope-guards) work best as class members because in that case resource management is encapsulated. The object takes care of resource management without user intervention, eg.

MyClass
{
public:
  MyClass(): mOwner (mPtv) {}
  // ...

private:
  ptr_vector<string> mPtv;
  ptr_vector_owner<string> mOwner; // scope-guard

};

Using The Code

The following is a complete example (see also download). Objects of type std::string are used for the sake of example, but any class (also non-copyable) would do as well.

Complete Example

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

Program output is:

 ---- 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 and Standard Algorithms

The Problem

Consider the following example:

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 is a Standard algorithm that sorts the elements in the passed range preserving the relative order of equivalent elements. In the above example, the algorithm inefficiently exchanges (copyable) pointed-to objects (MyClass objects) during stable_sort. But it should only swap pointers!

The same applies to all algorithms that rearrange the elements in a sequence. There is no effective way to change the behavior of Standard algorithms as desired. ptr_vector, the vector of pointers that appears to be a vector of values, just works too good in this case. How do we preserve the current convenient interface and make Standard algorithms work efficiently with the underlying pointers?

The Solution

The revised example:

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!

The difference to the previous example can easily be overlooked. The stable_sort algorithm from namespace stdx is used instead of the algorithm from namespace std. (ptr_vector also resides in namespace stdx.)

Actually, stdx::stable_sort is just a thin wrapper over std::stable_sort that under the hood does "The Right Thing": it sorts the sequence by exchanging pointers, not pointed-to objects.

Algorithms in namespace stdx

• wrapped algorithms work with pointer iterators like ptr_vector::iterator.
• only algorithms that rearrange a sequence of elements are wrapped to become "pointer aware".
• non-mutating algorithms like std::find are not and need not be wrapped, they work as they are.
• remove, remove_if, and unique have been re-implemented for pointer iterators because the Standard implementations don't work with pointers in these cases (they don't work smoothly with values, either). These algorithms now only reorder elements without deleting or overwriting any elements.
• wrapping is done in a straightforward and uniform way. Usually, one level of indirection is added to the arguments before they are passed to the underlying Standard algorithm. It can therefore be assumed that the wrapped algorithms are as reliable as the Standard algorithms they wrap.
• list of wrapped algorithms:
  • 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
• usage hint: sort algorithms require that operator< is defined for the pointed-to object or that a Compare object is passed as third argument. For other algorithms, operator== might be necessary. Always check the requirements of an algorithm with respect to the pointed-to object before you use it. Violating a requirement typically produces a bunch of unintelligible compiler error messages for which STL is notorious.

Best of Both Worlds

We've got both now, the efficiency of merely rearranging pointers under the hood and the convenience of handling values on the surface. The arsenal of Standard algorithms is available for ptr_vector iterators, either directly (for algorithms that don't exchange elements) or thinly wrapped (for rearranging algorithms).

Advanced users can write their own algorithms that work for Standard iterators and pointer iterators alike by using compile-time dispatch techniques similar to those invented in the context of Standard iterator traits (see unit tests for an example).

Points of Interest

Unit Tests

A set of Unit Tests is provided for ptr_vector, ptr_vector iterators, and algorithms (see download). They not only check the correctness of the implementation but also serve as:

• examples of how to program with ptr_vector and as
• aid if you want to use ptr_vector with or port ptr_vector to a new compiler (although problematic template constructs have been avoided, expect compiler and Standard library incompatibilities).

Unit tests have proved indispensable for developing and refactoring the code at hand and for template code in general. Usually compilers perform not even a (thorough) syntax check unless a template function is actually instantiated.

Optimization

ptr_vector's implementation is based on the Standard C++ vector. It uses a vector<T*> in Debug mode (Debug build) and a vector<void*> in Release mode (Release build) as base container. This avoids template 'code bloat' in the released program. Please note that ptr_vector's interface (including iterators) is always strongly typed. The optimization takes place only internally.

Compiler Compatibility

The Unit Tests were successfully compiled and run with:

• VC++ 6.0 (several workarounds were implemented especially for VC++ 6.0)
• VC++.NET 7.1, 8.0
• BCC 5.5
• GCC 3.2, 3.4 (Windows); 3.3, 4.0 (Linux)
• EDG compiler using Dinkum Exam online.

Apart from the usual incompatibilities, ptr_vector should compile with most, at least modestly, Standard conforming C++ compilers and Standard libraries. Please drop me a note if you have compiled the test cases with a compiler not listed above, also (especially!) if you have encountered compile time errors thereby. By the way, many years after C++ standardization (1998), compiler producers (commercial and non-commercial) still change template processing with every minor release. This fact alone indicates severe problems in the C++ template mechanism.

Historical Notes

Various containers and iterators for pointers have been produced by library vendors and individual developers, STL-based or not. For example:

• CTypedPtrArray,
• RWTPtrVector,
• QPtrVector,
• WCPtrVector,
• CArrayPtr,
• boost::ptr_vector,
• pointerator,
• deref_iterator,
• boost::indirect_iterator,
• ...

Since the C++ Standard lacks containers for pointers, probably many home-made implementations exist.

Thanks

Many thanks to Andreas R. for reviewing this article and for compiling the code with VC++.NET 7.1.

Conclusion

The main purpose of ptr_vector is to make the handling of objects (pointers) in a STL-like container more convenient for users. ptr_vector<T> is close to Standard vector<T> with respect to interface and usage - there is no need to learn a new 'paradigm'. Wrapped Standard algorithms rearrange sequences in a way that is convenient and fast. ptr_vector_owner offers an easy to use default resource manager for normal and exceptional cases.

Online Resources

• "The" STL site at SGI (Note: only a subset of STL was included into the C++ Standard.).
• "Designing Components with the C++ STL" by Ulrich Breymann, Addison Wesley Longman 2000. Free download as printable PDF-file, also in German (Note: not all examples may work unmodified with VC++ 6.0.).

History

• June 6, 2004 - Submission to CodeProject
• December 16, 2004 - Submission of updated version to CodeProject
  • Code:
    • wrapped algorithms for ptr_vector iterators implemented
    • test cases for wrapped algorithms added
    • code cleaned up
  • Article:
    • chapter ' ptr_vector and Standard Algorithms' added
    • article amended and cleaned up
• March 14, 2005 - Submission of updated version to CodeProject
  • Code:
    • private inheritance dropped in iterator implementation due to new template lookup rules (2-phase name lookup) enforced by GCC 3.4; this refactoring does not affect 'outside' behavior
  • Article:
    • minor changes and corrections
• October 21, 2006 - Submission of updated version to CodeProject
  • Code:
    • code tested with newer compiler versions
  • Article:
    • invalid links updated
    • small changes and corrections