Click here to Skip to main content
15,867,488 members
Articles / Programming Languages / C++
Article

ptr_vector - A Container For Pointers

Rate me:
Please Sign up or sign in to vote.
4.74/5 (51 votes)
25 Oct 200610 min read 230.6K   1.1K   53   62
Convenient STL-compliant vector for pointers.

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

functionstd::vectorstdx::ptr_vectorcomment
copy constructor+-(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)

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:

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

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Web Developer
Austria Austria
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralRe: Sorry Pin
Roland Pibinger24-Oct-06 22:38
Roland Pibinger24-Oct-06 22:38 
GeneralRe: Sorry Pin
Vytas24-Oct-06 22:53
Vytas24-Oct-06 22:53 
GeneralRe: Sorry Pin
Roland Pibinger24-Oct-06 23:11
Roland Pibinger24-Oct-06 23:11 
GeneralRe: Sorry Pin
Vytas24-Oct-06 23:42
Vytas24-Oct-06 23:42 
GeneralRe: Sorry [modified] Pin
Roland Pibinger25-Oct-06 2:08
Roland Pibinger25-Oct-06 2:08 
class A{
//blalala
};
class B{
/...
// next line from your sample...
stdx::ptr_vector<A> ptv;
stdx::ptr_vector_owner<A> owner(ptv); //<<-error C2061: syntax error : identifier 'ptv'  ???
};


Ok, I can see the problem now. You need to initialize owner (a member) in the constructor (see also the similar example in the article):

class B{
//...
  B(): owner(ptv) {}
 
  stdx::ptr_vector<A> ptv;
  stdx::ptr_vector_owner<A> owner;
};





-- modified at 13:17 Wednesday 25th October, 2006
JokeRe: Sorry Pin
Vytas25-Oct-06 2:20
Vytas25-Oct-06 2:20 
GeneralO, thanks a lot, I just have the same question, now it's solved. Thanks for your work Pin
Wiseman Chang27-May-07 21:56
Wiseman Chang27-May-07 21:56 
General2-phase name lookup Pin
Roland Pibinger21-Mar-05 9:37
Roland Pibinger21-Mar-05 9:37 
GeneralSTL Value Semantics Pin
Roland Pibinger21-Mar-05 9:16
Roland Pibinger21-Mar-05 9:16 
GeneralDifferences to boost::ptr_vector Pin
Roland Pibinger21-Mar-05 8:58
Roland Pibinger21-Mar-05 8:58 
GeneralHi GoodWork But Pin
sanjit_rath24-Dec-04 16:16
sanjit_rath24-Dec-04 16:16 
GeneralRe: Hi GoodWork But Pin
Roland Pibinger26-Dec-04 5:52
Roland Pibinger26-Dec-04 5:52 
GeneralRe: Hi GoodWork But Pin
sanjit_rath26-Dec-04 15:57
sanjit_rath26-Dec-04 15:57 
GeneralRe: Hi GoodWork But Pin
Roland Pibinger27-Dec-04 8:41
Roland Pibinger27-Dec-04 8:41 
GeneralRe: Hi GoodWork But Pin
sanjit_rath27-Dec-04 20:28
sanjit_rath27-Dec-04 20:28 
GeneralGreat stuff! Pin
Don Clugston16-Dec-04 13:04
Don Clugston16-Dec-04 13:04 
GeneralRe: Great stuff! Pin
Roland Pibinger16-Dec-04 14:19
Roland Pibinger16-Dec-04 14:19 
GeneralRe: Great stuff! Pin
Emilio Garavaglia26-Oct-06 2:04
Emilio Garavaglia26-Oct-06 2:04 
AnswerRe: Great stuff! Pin
Roland Pibinger29-Oct-06 1:38
Roland Pibinger29-Oct-06 1:38 
GeneralThere is also the boost::indirect_iterator Pin
Jim Xochellis15-Jun-04 12:43
Jim Xochellis15-Jun-04 12:43 
GeneralRe: There is also the boost::indirect_iterator Pin
Roland Pibinger15-Jun-04 14:15
Roland Pibinger15-Jun-04 14:15 
GeneralRe: There is also the boost::indirect_iterator Pin
Jim Xochellis15-Jun-04 20:10
Jim Xochellis15-Jun-04 20:10 
GeneralRe: There is also the boost::indirect_iterator Pin
Roland Pibinger15-Jun-04 20:49
Roland Pibinger15-Jun-04 20:49 
QuestionBoost candidate? Pin
Johannes Gustafsson13-Jun-04 23:13
Johannes Gustafsson13-Jun-04 23:13 
AnswerRe: Boost candidate? Pin
Roland Pibinger14-Jun-04 1:49
Roland Pibinger14-Jun-04 1:49 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.