//
you're reading...
C++, Programming Issues/Tips

Storing C++ Objects in a STL Vector Part 3.

1. Introduction.

1.1 In part 2 of this series of articles, we discussed how to use a STL vector to store pointers to objects.

1.2 The purpose of this was to store items in a vector that are linked to base class objects and through this we create the opportunity to downcast base objects to derived ones.

1.3 We saw that with such an arrangement, we have to manually free the memory occupied by the objects (the pointers to which are stored in the vector).

1.4 We then tried to use the std::auto_ptr smart pointer class which promises to automatically free objects via their pointers on deletion.

1.5 We saw that this is not possible to store std::auto_ptr instances in a vector. The std::auto_ptr class is such that, as part of the copy-construction process of an instance, modification of the copied instance (i.e. setting its internal pointer to zero) is required. This requirement is necessary so that the ownership of the stored pointer be transferred to the new instance.

1.6 This is a problem for a STL vector because, as part of its object insertion process, the vector expects copies be created from constant objects. We therefore conceded that it is not possible to use the STL vector to contain std::auto_ptr objects.

1.7 This part explores the boost::shared_ptr type to see whether it can be used as a viable alternative to the std::auto_ptr.

2. The boost::shared_ptr.

2.1 The Boost library is a set of C++ classes, structures and routines which can be used in addition to the standard C++ libraries. Due to its popularity and usefulness, some of boost’s classes and routines have been incorporated into the C++ standard. The boost library is available from its web site.

2.2 According to the Boost library documentation :

Every shared_ptr meets the CopyConstructible and Assignable requirements of the C++ Standard Library, and so can be used in standard library containers.

The boost::shared_ptr class internally uses reference counting to keep track of joint references to one single pointer across one or more boost::shared_ptr instances.

2.3 Reference counting is the mechanism by which the boost::shared_ptr class code determines the actual time to delete the pointer that an instance jointly-owns with other instances. We shall briefly examine the reference counting mechanism in a later section.

2.4 And before moving on to studying how we can use the boost::shared_ptr class to store pointers to instances of a base class, we will study how to use such a class in the first place.

2.5 To this end, we shall use the same 2 classes that we first defined in part 1 :

class Base 
{
public:
	Base(int _x)
	{
		x = _x;
	}

	virtual ~Base()
	{
		x = 0;
	}

	int x;

	void func()
	{
		std::cout << "Base func(). x == " << x << std::endl;
	}
};

class Derived : public Base
{		
public:
	Derived(int _x, int _y) :
		Base(_x)
	{
		y = _y;
	}

	virtual ~Derived()
	{
		y = 0;
	}	

	int y;

	void func()
	{
		std::cout << "Derived func(). y == " << y << std::endl;	
	}
};

2.6 The typical starting point of using a boost::shared_ptr class is to #include the <boost/shared_ptr.hpp> header file and then type define a specific template instantiation of such a class :

#include <boost/shared_ptr.hpp>

...
...
...

typedef boost::shared_ptr<Base>	BasePtr;

The above typedef statement defines a type named BasePtr which is essentially a boost::shared_ptr of type Base.

You would of course need to first have the boost library installed on your system and have your Visual Studio C++ Project’s “Additional Include Directories” setting point to your boost library folder.

2.7 Similar to the std::auto_ptr type, when we declare an instance of a boost::shared_ptr, it is standard practice to code it as follows :

BasePtr	base_ptr(new Base(0));

with the parameter to the constructor being the result of a new allocation of the type. This is inline with the principles of the Resource Allocation Is Initialization (RAII) idiom.

2.8 The following is a simple example code that uses the BasePtr class :

BasePtr	base_ptr(new Base(0));

base_ptr -> func();

The following is a list of pertinent points about the code above :

  • An instance of BasePtr is created, named base_ptr.
  • It is instantiated with a pointer to an instance of the Base class.
  • The new Base class instance is allocated on the heap.
  • The base_ptr object can then be used to access its properties and methods.
  • When base_ptr goes out of scope, its destructor is invoked.
  • Now take note that when base_ptr is destroyed, what is destroyed is not a Base class instance.
  • That is, the first destructor that gets invoked is not ~Base().
  • It is actually ~BasePtr() or boost::shared_ptr<Base>::~shared_ptr<Base>(), to be accurate.
  • Now as part of the process for the destruction of the BasePtr object, the destructor for Base will be invoked.
  • Getting from ~BasePtr to ~Base() is a fairly complex process which involves reference counting.
  • We shall examine this in some detail in another section.

2.9 Note that in order to ensure proper reference counting, the original Base object created on the heap must be completely owned by the initial BasePtr object. After that, two or more BasePtr objects can jointly share ownership of the Base object. For example :

void ThreeBasePtrShareOneBase()
{
	BasePtr	base_ptr(new Base(100));
	BasePtr	base_ptr_2(base_ptr);
	BasePtr	base_ptr_3 = base_ptr;

	base_ptr -> func();
	base_ptr_2 -> func();
	base_ptr_3 -> func();
}

The following is a summary of the code above :

  • In the above code, only one Base instance is actually created with constructor parameter value 100.
  • This Base object is then owned by base_ptr.
  • After that, a new base_ptr_2 object is created with base_ptr as constructor parameter.
  • This essentially invokes the BasePtr copy constructor.
  • This is where the boost::shared_ptr differs from the std::auto_ptr : the boost::shared_ptr allows the copy construction of an instance from another without requiring that the other instance (the one used for copying) be non-const.
  • Recall from part 2 that the copy constructor of the std::auto_ptr class is such that as part of copy construction, it will call the release() method of the std::auto_ptr instance that was used for copying.
  • This is necessary because no 2 instances of the std::auto_ptr class may hold the same pointer. One must give up ownership.
  • But as far as the boost::shared_ptr is concerned, the instance used for copying can be const or non-const.
  • It does not matter because the copy constructor will not need to modify the instance used for copying.
  • Two or more boost::shared_ptr instances may jointly own a single pointer.
  • Returning back to the code above, we see that after base_ptr_2, we create yet another boost::shared_ptr : base_ptr_3.
  • In the code, base_ptr_3 is created using the assignment (‘=’) syntax. This implicitly calls the copy constructor.
  • In the end, the Base pointer will be jointly shared across 3 boost::shared_ptr instances.
  • When all 3 boost::shared_ptr instances go out of scope, the single Base pointer will be deleted.

2.10 Note that it would not be proper if the initial boost::shared_ptr instance either does not completely own the pointer, or that additional code somehow hijacks it and either deletes it or uses it to instantiate another boost::shared_ptr.

2.11 The following is one example :

void ImproperUseOfSharedPtr1()
{
	Base* pBase = 0;
	BasePtr	base_ptr(pBase = new Base(100));

	delete pBase;
}
  • In the above code, the pointer to the Base class instance (pBase) is kept after being used as constructor parameter to base_ptr.
  • After that, pBase is deleted and base_ptr carries on to perform internal deletion of the same object pointed to by pBase causing a crash.

2.12 The following is another example :

void ImproperUseOfSharedPtr2()
{
	Base* pBase = 0;
	BasePtr	base_ptr(pBase = new Base(100));
	BasePtr	base_ptr_2(pBase);
}
  • In the above code, the pointer to Base which was used as constructor parameter to base_ptr is again kept and is used as constructor parameter to base_ptr_2.
  • This caused 2 boost::shared_ptr instances to separately own pBase.
  • When base_ptr and base_ptr_2 are eventually destroyed, their individual reference counts on pBase has not been kept in sync, causing each to delete pBase.

2.13 In section 4, we will begin to explore how to store boost::shared_ptr instances inside a STL vector. Before that, in the next section, we will briefly study the reference counting mechanism of the boost::shared_ptr class.

3. The Reference Counting Mechanism of the boost::shared_ptr Class.

3.1 The reference counting mechanism of the boost::shared_ptr class is accomplished via the boost::detail::shared_count class.

3.2 This class in turn uses the boost::detail::sp_counted_base class for actual reference counting.

3.3 The boost::shared_ptr class internally declares a member instance of boost::detail::shared_count and initializes it with the same pointer to the object which a boost::shared_ptr instance owns.

3.4 I shall attempt to demonstrate the inner working of the boost::detail::shared_count and boost::detail::sp_counted_base classes by using a simpler client class named Test which will be defined in the next point below.

3.5 The Test class is defined as follows :

class Test
{
public :
	Test(int i) :
		m_int(i),
		pn((int*)0)
	{
	}

	int GetInt()
	{
		return m_int;
	}

	long GetUseCount()
	{
		return pn.use_count();
	}

private :
	int m_int;
	boost::detail::shared_count pn;    // reference counter
};

The purpose of the Test class is to demonstrate how the boost::detail::shared_count can be used to perform reference counting of Test instances.

As Test instances are copy constructed, its boost::detail::shared_count member will keep increasing a central global reference count and as each Test instance is destroyed, this central global reference count is decremented.

The following is a short summary of the Test class :

  • It is a simple class which encapsulates a member integer m_int which is initialized via constructor parameter.
  • Test exposes m_int through a getter function named GetInt().
  • The more important part of the Test class is the member pn which is of type boost::detail::shared_count.

A more detailed study of the Test class will be given in a later point below after some introduction has been made of the client functions that will make use of the reference counting feature of Test.

3.5 The following client functions demonstrate the reference counting mechanism inherent in Test :

void InvokeTest(Test test)
{
	// test use count will increase by 1 upon every new recursion
	// of InvokeTest().
	std::cout << "InvokeTest(). test.GetInt() : " 
	<< test.GetInt() 
	<< ". test use count : " 
	<< test.GetUseCount() 
	<< std::endl;

	if (test.GetUseCount() < 5)
	{
		InvokeTest(test);
	}
}

void DemonstrateSharedCount()
{	
	// Call InvokeTest() with a temporary instance 
	// of the Test class initialized with value 100.
	InvokeTest(Test(100));
}

The following is a summary of the InvokeTest() function :

  • InvokeTest() takes an instance of Test as parameter.
  • Note that the parameter is not a reference to a Test instance but is a complete copy of one.
  • This is specifically intended as I plan to show how the test parameter will be copy constructed.
  • Inside the function, the current value of the Test instance’s m_int is displayed together with the use count of the original test instance which was first passed as parameter to InvokeTest().
  • This use count is then used as a control measure to perform a recursion on InvokeTest().
  • As long as the current use count is less than 5, InvokeTest() is recursively called.

The following is a summary of the DemonstrateSharedCount() function :

  • It is a very simple function which makes the initial call to InvokeTest() with a temporary instance of Test with integer value 100.
  • The temporary instance of Test is also the first instance to be constructed.
  • The constructor function used is the one which takes an integer as parameter.
  • This test instance is constructed on the stack and will remain in existence until the first call to InvokeTest() returns.
  • When InvokeTest() is called a second time (inside InvokeTest() itself), the original test parameter is copied and the copy is passed as the parameter to the second call to InvokeTest().
  • The Test copy constructor is thus called. More on this as we examine the Test class in more detail below.

When the DemonstrateSharedCount() function is run, the following will be the console output :

InvokeTest(). test.GetInt() : 100. test use count : 1
InvokeTest(). test.GetInt() : 100. test use count : 2
InvokeTest(). test.GetInt() : 100. test use count : 3
InvokeTest(). test.GetInt() : 100. test use count : 4
InvokeTest(). test.GetInt() : 100. test use count : 5

3.6 The following are some further noteworthy points about the Test class :

  • As a Test instance is first created without the use of the copy constructor, the boost::detail::shared_count member of Test, i.e. pn, is initialized to a null pointer :
Test(int i) :
	m_int(i),
	pn((int*)0)
{
}
  • The null pointer is one that points to an integer, hence the (int*) cast.
  • This is how we indicate to pn that the type of the pointer that it is to own is the int type.
  • In other words, we want pn to manage a pointer to an int.
  • pn itself holds a member pointer to a boost::detail::sp_counted_base object (pi_) which is shared across multiple instances of shared_count instances.
  • When pn is being initialized as in the above constructor code, its internal sp_counted_base pointer member pi_ is constructed as an instance of the templated sp_counted_impl_p<> class.
  • Since pn is initialized with a pointer to an integer, pi_ is instantiated as a sp_counted_impl_p<int> instance :
template<class Y> explicit shared_count( Y * p ): pi_( 0 )
{
    try
    {
        pi_ = new sp_counted_impl_p<Y>( p );
    }
    catch(...)
    {
        boost::checked_delete( p );
        throw;
    }
}
  • The sp_counted_impl_p class is derived from sp_counted_base.
  • The sp_counted_base class contains the long member use_count_ which is the actual reference counter.

Note that the above points apply to an instance of Test which was not constructed via another instance (i.e. not via the copy constructor).

Therefore, when DemonstrateSharedCount() calls InvokeTest() for the first time, and the first Test instance is created and passed as parameter, the Test instance’s shared_count member (pn) will be initialized this way. As a result, pn’s sp_counted_base object member, pi_, will be instantiated in the heap for the first time.

  • Now, when InvokeTest() is called a second time, the Test instance which was passed to the first call to InvokeTest() will be used as parameter.
  • However, because this parameter is not passed by reference, a complete copy of it will be made and then pushed onto the stack of the second call to InvokeTest().
  • This will invoke the copy constructor of the Test class.
  • I have deliberately left out the copy constructor in order to make the Test class more closely resemble the boost::shared_ptr class – the shared_ptr class also does not define any copy constructor.
  • This leaves the Test class with a default copy constructor which is generated by the compiler.
  • The copy constructor generated by the compiler for the Test class will have the following signature :
Test::Test(const Test & rhs);
  • This default copy constructor will be such that for each of the members data of the Test class, either a complete bit-wise duplicate is made from the same member of the instance to be copied from, or the copy constructor of the member is invoked.
  • For integer member m_int, a complete bit-wise duplicate is made.
  • For the shared_count member pn, the copy constructor for the shared_ptr class is called :
shared_count(shared_count const & r): pi_(r.pi_) // nothrow
{
    if( pi_ != 0 ) pi_->add_ref_copy();
}
  • Notice that the value of the pointer to the sp_counted_base member pi_ is simply assigned from the copy’s pi_.
  • This maintains the fact that there is always only one central sp_counted_base object no matter how many shared_count objects (and their owning Test objects) there are.
  • This is the first step in ensuring proper reference counting of the client Test objects.
  • Returning back to the copy constructor code above, notice that the add_ref_copy() function of pi_ is called. This is the second and very crucial step in the control of the reference count of the client Test object.
  • Let’s have a look at the add_ref_copy() function :
void add_ref_copy()
{
    BOOST_INTERLOCKED_INCREMENT( &use_count_ );
}
  • Simply put, pi_’s use_count_ is incremented.
  • Hence, as a new instance of Test gets created from another instance, the global use_count value is incremented.

3.7 The recursive calls to InvokeTest() will carry on until it is called with a final Test instance whose GetUseCount() function returns a value of 5.

3.8 When this happens, InvokeTest() is not called again. The current InvokeTest() call returns and subsequently, each previous InvokeTest() call up the call stack returns.

3.9 As each function call returns, the Test instance involved in that call will be destroyed as it gets out of scope. When this happens, each boost::detail::shared_count member (pn) of the Test instance that is being destroyed will be destroyed as well :

~shared_count() // nothrow
{
    if( pi_ != 0 ) pi_->release();
}

The shared_count instance member pointer to a sp_counted_base object, pi_, will be activated at this time. Recall that this sp_counted_base object is a central object shared by all instances of shared_count. It is by implication shared by all instances of Test. Its release() function will be called :

void release() // nothrow
{
    if( BOOST_INTERLOCKED_DECREMENT( &use_count_ ) == 0 )
    {
        dispose();
        weak_release();
    }
}

The use_count_ member will be decremented. If its value is zero, its member dispose() function will be called.

3.10 We know that at the time when the final call to InvokeTest() returns, after being decremented, use_count_ will not be zero. It will be 4. Hence dispose() will not be called. The current Test instance gets destroyed and control reaches the immediate previous call to InvokeTest().

3.11 The Test instance involved in that InvokeTest() call gets destroyed and once again we reach the release() function and use_count_ is again decremented. This repeats until use_count_ reaches zero and dispose() is called :

virtual void dispose() // nothrow
{
    boost::checked_delete( px_ );
}

The boost::checked_delete() function is called on px_ (i.e. sp_counted_impl_p::px_) which is the pointer to the actual resource that all Test instances are supposed to share.

We saw in section 3.5, in the code for the Test class, that this has been set to zero (the constructor parameter for the Test::pn member).

3.12 Continuing our focus on the boost::checked_delete() function, we see that px_ will be deleted :

template<class T> inline void checked_delete(T * x)
{
    // intentionally complex - simplification causes regressions
    typedef char type_must_be_complete[ sizeof(T)? 1: -1 ];
    (void) sizeof(type_must_be_complete);
    delete x;
}

Now in the context of the Test class, parameter x will be 0 and so there will be a call to delete 0. This is allowed in C++ and no runtime exception will be thrown.

In the context of an actual boost::shared_ptr instance, x will be the pointer to the actual shared object. In the case of BasePtr (i.e. boost::shared_ptr<Base>) x will be a pointer to a Base instance and it will be deleted this way.

This is how such a shared instance of Base gets finally deleted when the last instance of BasePtr is destroyed.

4. Using the boost::shared_ptr In A STL Vector.

4.1 Now that we are thoroughly familiar with the boost::shared_ptr class, it is time to use it to store object pointers in a vector.

4.2 Recall that our long term objective is to store items in a vector that are linked to base class objects and through this we create the opportunity to downcast base objects to derived ones. Further, we want the stored objects of a vector to self-destruct when the vector itself is destroyed.

4.3 We will continue to require the typedef that we defined earlier :

typedef boost::shared_ptr<Base>	BasePtr;

and with this typedef, we can create a standard STL vector of BasePtr :

std::vector<BasePtr>

4.4 The following is a simple function which demonstrates the insertion of an instance of Base and an instance of Derived into a vector. After the insertion, retrieval of each object is performed together with dynamic down-casting when possible :

void DoTest_VectorOfSharedPtr()
{
	std::vector<BasePtr>	vecBasePtr;

	vecBasePtr.push_back(BasePtr(new Base(0)));
	vecBasePtr.push_back(BasePtr(new Derived(1, 2)));

	std::vector<BasePtr>::iterator theIterator;

	for (theIterator = vecBasePtr.begin(); theIterator != vecBasePtr.end(); theIterator++)
	{
		BasePtr& base_ptr = (BasePtr&)(*theIterator);

		base_ptr -> func();

		Derived* pDerived = dynamic_cast<Derived*>(base_ptr.get());

		if (pDerived)
		{
			pDerived -> func();
		}
	}
}

The following is a summary of the code above :

  • A STL vector of BasePtr, vecBasePtr, is declared.
  • One Base class instance, initialized with integer value 0, is inserted into vecBasePtr via a BasePtr wrapper.
  • One Derived class instance, initialized with integer values 1 and 2, is inserted into vecBasePtr via a BasePtr wrapper.
  • When the pointer to the Derived instance is inserted into BasePtr, it is stored inside the BasePtr object as a pointer to Base.
  • This is perfectly fine and the fact that it is actually a pointer to a Derived object is preserved.
  • An iteration is performed and for each BasePtr object retrieved, we call the inner Base class pointer’s func() function.
  • After that, an attempt is made to perform a dynamic_cast from the Base class pointer to a Derived class pointer.
  • The happy result is that when the dynamic_cast is performed on the pointer to the Derived class, it will succeed and we will be able to call the Derived::func() function.

At runtime the code above will yield the following console output :

Base func(). x == 0
Base func(). x == 1
Derived func(). y == 2

4.5 Finally, when the vector is destroyed, its items, which are boost::shared_ptr<Base> objects and not direct pointers to Base or Derived class instances, are destroyed. We have already studied deeply how the destruction process of boost::shared_ptr objects cater to the proper deletion of its stored pointers. Hence there is no need for hand deletion of pointers.

5. In Conclusion.

5.1 This has certainly been a very long discussion and I hope that the reader has gleaned some useful knowledge from the 3 parts of this article.

5.2 I certainly had great pleasure researching into the inner workings of the boost::shared_ptr class. I hope to do more writeups on other boost classes in the future.

5.3 The wonderful thing about the boost library is how its classes seamlessly integrate with standard C++ library ones, e.g. the boost::shared_ptr class with std::vector.

5.4 I hope the reader will download the boost C++ library and discover many more great classes that can be used in various C++ projects.

Advertisements

About Lim Bio Liong

I've been in software development for nearly 20 years specializing in C , COM and C#. It's truly an exicting time we live in, with so much resources at our disposal to gain and share knowledge. I hope my blog will serve a small part in this global knowledge sharing network. For many years now I've been deeply involved with C development work. However since circa 2010, my current work has required me to use more and more on C# with a particular focus on COM interop. I've also written several articles for CodeProject. However, in recent years I've concentrated my time more on helping others in the MSDN forums. Please feel free to leave a comment whenever you have any constructive criticism over any of my blog posts.

Discussion

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: