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

Storing C++ Objects in a STL Vector Part 2

1. Introduction.

1.1 In part 1, we concluded that given a base class B, a class D derived from B, and a vector V of class B, it is not possible to store an instance of D in V. Any such instance will be constructed as an object of class B before being stored inside V.

1.2 This part will continue the discussion and explore ways (in spirit at least) to somehow achieve the above goal.

2. Using Pointers to Objects.

2.1 One way to accomplish our mission is to store pointers to objects instead.

2.2 For the purpose of our discussion, let’s use the same base and derived classes that we saw in part 1 :

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

	Base(const Base& rhs)
	{
		x = rhs.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;
	}

	Derived(const Derived& rhs) :
		Base(rhs)
	{
		y = rhs.y;
	}	

	virtual ~Derived()
	{
		y = 0;
	}	

	int y;

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

2.3 We can construct a vector as follows :

std::vector<Base*>	vecBasePointers;

Since the type of objects that we will store in this vectors are pointers, it will not matter whether we store a pointer to a Base class or to a Derived class.

2.4 Here is a simple function that we can use to test such a vector :

void DoTest_UseDirectPointers()
{
	std::vector<Base*>	vecBasePointers;

	vecBasePointers.push_back(new Base(0));
	vecBasePointers.push_back(new Derived(1, 2));
	vecBasePointers.push_back(new Base(3));

	std::vector<Base*>::iterator	theIterator;

	for (theIterator = vecBasePointers.begin(); theIterator != vecBasePointers.end(); theIterator++)
	{
		Base* pbase = *theIterator;

		pbase -> func();

		Derived* pderived = dynamic_cast<Derived*>(pbase);

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

	for (theIterator = vecBasePointers.begin(); theIterator != vecBasePointers.end(); theIterator++)
	{
		Base* pbase = *theIterator;

		delete pbase;
	}
}

The following is a summary of the code above :

  • A vector of Base class pointers (i.e. vecBasePointers) is declared.
  • 2 instances of Base and 1 instance of Derived (instantiated through a pointer to a Base) are created.
  • Pointers to these 3 objects are stored into the vector.
  • We then iterate through the items in the vector and for each pointer to a Base object, we call its Base func() function.
  • We then attempt to dynamically cast the current pointer to a Derived class.
  • If the dynamic cast is successful, we call its Derived func() function.

when this function is run, the following will be the console output :

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

which is consistent with the ordering of the Base and Derived objects which have been pushed back into the vector.

  • But that’s not all to the code above. The DoTest_UseDirectPointers() function also contains code to free all objects via their pointers which are stored in the vector.
  • This hand coded memory release (on all objects the pointers to which are stored in the vector) is necessary.
  • This is because a vector of pointers contains essentially integer values. Each integer being an address to an object.
  • As such when the memory for each item of the vector is released, the memory for each integer is recovered but the objects are not memory recovered.
  • Therefore, the memory for each object (the pointer to which is stored in the vector) must be freed manually as shown in the DoTest_UseDirectPointers() function.
  • Now here is where we see the virtual Derived destructor in action.
  • As delete is called on the pointer to the Derived object (via a pointer to the Base class), the Derived class destructor is called first followed by the Base class destructor.

2.5 We can conclude that storing pointers to objects in a vector will work towards storing instances of classes which are derived from the type for which the vector is declared.

2.6 Hence given a base class B, a class D derived from B, and a vector V of pointers to class B, it is possible to store a pointer to an instance of D in V.

2.7 However, automatic destruction of the underlying objects (the pointers to which are stored in the vector) is not possible and such destruction must be performed by hand.

2.8 To some, this may seem like a minor inconvenience at worst. But let’s explore better ways to accomplish the same thing.

3. Using std::auto_ptr.

3.1 An alternative to storing direct pointers is to use the std::auto_ptr class.

3.2 The std::auto_ptr class is a type-templated smart pointer class that owns the pointer that it is initialized with. When the std::auto_ptr class instance goes out of scope and is destroyed, it will automatically delete the pointer that it holds. And since it rightfully owns this pointer, it is perfectly legal for it to do so.

3.3 The following description of the auto_ptr class from MSDN best characterizes it :

The template class describes an object that stores a pointer to an allocated object of type Type* that ensures that the object to which it points gets destroyed automatically when control leaves a block.

3.4 Using code, let’s see the std::auto_ptr class in action :

void DoTest_AutoPtr()
{
	typedef std::auto_ptr<Base>	AutoBasePtr;

	AutoBasePtr	auto_base_ptr(new Base(0));

	auto_base_ptr -> func();
}

In the above function, as the DoTest_AutoPtr() function terminates and the “auto_base_ptr” object goes out of scope, its destructor will be called automatically :

~auto_ptr()
	{	// destroy the object
	if (_Myptr != 0)
		delete _Myptr;
	}

…and it is at this point that “_Myptr” (the internal pointer to the Base object which was used as the parameter to the constructor of auto_base_ptr) will be deleted.

3.5 It seems promising, then, to use a std::auto_ptr class object to store a pointer to an object and then store that std::auto_ptr object in a vector.

3.6 However, it will not work as far as using it in a vector is concerned. If we have code like the following :

void DoTest_AutoPtrInVector()
{
	typedef std::auto_ptr<Base>	AutoBasePtr;

	std::vector<AutoBasePtr>	vecAutoBasePtrs;

	vecAutoBasePtrs.push_back(AutoBasePtr(new Base(0)));
}

the compiler will raise a complaint :

error C2558: class ‘std::auto_ptr<_Ty>’ : no copy constructor available or copy constructor is declared ‘explicit’

The technical explanation for this error message will be examined in section 4 below. For now, I will assume a high-level explanation and explore its implications.

3.7 The compiler error message is a result of the fact that somewhere within the code for the std::vector class, a copy (or copies) of stored objects will have to be made.

3.8 Here is the special thing about the std::auto_ptr class : when an auto_ptr instance is assigned the value of another instance, the new instance takes over ownership of the pointer managed by the old one.

3.9 Consider the following example :

AutoBasePtr auto_base_ptr(new Base(0));

AutoBasePtr auto_base_ptr2 = auto_base_ptr;

The following is a summary of the code above :

  • A std::auto_ptr instance “auto_base_ptr” is created with a pointer to a new instance of Base (initialized with 0).
  • Another std::auto_ptr instance “auto_base_ptr2” is created and is instantiated with the value of the existing “auto_base_ptr”.
  • What will happen here is that the copy constructor for std::auto_ptr will be invoked :
auto_ptr(auto_ptr<_Ty>& _Right) _THROW0()
	: _Myptr(_Right.release())
	{	// construct by assuming pointer from _Right auto_ptr
	}
  • The code above is actually executed in favor of “auto_base_ptr2”, i.e. “auto_base_ptr2” is the object being created. And “_Right” refers to “auto_base_ptr”.
  • “_Myptr” is the pointer to Base that “auto_base_ptr2” is meant to internally hold.
  • Now “_Myptr” will be assigned the return value of the release() function called on “_Right” :
_Ty *release() _THROW0()
	{	// return wrapped pointer and give up ownership
	_Ty *_Tmp = _Myptr;
	_Myptr = 0;
	return (_Tmp);
	}
  • What release() will do is to set “_Right._Myptr” to 0 and then return the original value of its “_Myptr”.
  • Hence in summary, the copy constructor for “auto_base_ptr2” will assign “auto_base_ptr2._Myptr” to the value of “auto_base_ptr._Myptr” and after this assignment, “auto_base_ptr._Myptr” will be set to 0.
  • In order words, “auto_base_ptr2” will take over ownership of the pointer managed by “auto_base_ptr”.

3.10 This ownership takeover is important because it would not do to have 2 std::auto_ptr objects jointly share ownership of one single pointer.

3.11 The problem being : when one gets destroyed, the internally held pointer will be deleted and then when the other gets destroyed, it will attempt to delete the same pointer which has already been deleted.

3.12 Returning to points 3.6 and 3.7 above, we conclude that it is not possible to define a std::vector of std::auto_ptr types due to the internal algorithmic requirements of the std::vector to immutably make copies of stored items.

4. Copy Constructability.

4.1 The std::auto_ptr class is certainly copy constructable as we saw earlier in point 3.9. Yet the error message described in point 3.6 states :

error C2558: class ‘std::auto_ptr<_Ty>’ : no copy constructor available or copy constructor is declared ‘explicit’

There seems to be a contradiction here. This section attempts to explain the disconnect.

4.2 With reference to the code in point 3.6 :

vecAutoBasePtrs.push_back(AutoBasePtr(new Base(0)));

This error message is generated when the compiler scans through code for the push_back() function and then encounters the following line in the vector class :

void _Insert_n(const_iterator _Where,
	size_type _Count, const _Ty& _Val)
{
	...
	...
	...
	_Ty _Tmp = _Val;	// in case _Val is in sequence
	...
	...
	...
}

The following is a summary of the code above :

  • In the declaration cum construction (via assignment) code for _Tmp, _Ty is the template type defined for the vector. And _Val is a const reference to a _Ty instance.
  • The assignment will cause the compiler to generate code to invoke the copy constructor of _Ty using _Val as the reference parameter.
  • Now _Val is const (see the parameter list for the _Insert_n() function above.
  • The compiler will thus search for the _Ty copy constructor that takes as parameter a const reference to an instance of _Ty.
  • The problem is that for the std::auto_ptr class, the compiler is not able to find such a copy constructor.
  • Note the existing copy constructor for std::auto_ptr :
auto_ptr(auto_ptr<_Ty>& _Right) _THROW0()
	: _Myptr(_Right.release())
	{	// construct by assuming pointer from _Right auto_ptr
	}

Its parameter is a non-const reference to a std::auto_ptr.

  • This is the reason for the compiler error message.

4.3 Now it is generally known that the compiler will generate a default copy constructor for a C++ class that does not define one explicitly.

4.4 Furthermore, the default constructor that the compiler generates will be one that takes a const reference to an instance of the same type.

4.5 Why then does the compiler not generate a copy constructor for std::auto_ptr that takes a const reference parameter ?

4.6 The reason is that since a copy constructor that takes a non-const reference parameter already exists, and the author specifically did not define one that takes a const reference parameter, the compiler must assume that the author of the class does not intend such a constructor.

4.7 Not assuming so may inadvertently cause problems. The author of the class may want the copy constructor (that takes a non-const reference parameter) to make changes to the parameter. This certainly cannot be ruled out.

4.8 I will illustrate this with an example. Let’s say we have the following class :

class Test
{
public :
	Test(int i) :
		m_bEverBeenCopied(false),
		m_int(i)
	{
	}

	Test(Test& rhs) :
		m_bEverBeenCopied(false),
		m_int(rhs.m_int)
	{
		rhs.m_bEverBeenCopied = true;
	}

	int GetInt() const 
	{
		return m_int;
	}

	bool EverBeenCopied() const
	{
		return m_bEverBeenCopied;
	}

private :
	int m_int;
	bool m_bEverBeenCopied;
};

The following is a synopsis of the Test class above :

  • It is a simple class that contains an integer member m_int with an accessor function GetInt().
  • It has a special bool member m_bEverBeenCopied that indicates whether an instance of the Test class has ever been used to create another instance via a copy constructor.
  • Note the nature of Test’s copy constructor : it takes a non-const reference to another Test instance.
  • The reference parameter being non-const must be so in order that the copy constructor be able to modify the parameter’s m_bEverBeenCopied member to indicate that it has been copied to the current Test instance.
  • The following client code will illustrate this :
void DoTest()
{
	Test	test1(100);
	Test	test2(test1);
	Test	test3(test2);

	std::cout << "test1.m_int : " << test1.GetInt() 
		<< ". Ever been copied : " 
		<< (test1.EverBeenCopied() ? "YES" : "NO") 
		<< std::endl;
	std::cout << "test2.m_int : " << test2.GetInt() 
		<< ". Ever been copied : " 
		<< (test2.EverBeenCopied() ? "YES" : "NO") 
		<< std::endl;
	std::cout << "test3.m_int : " << test3.GetInt() 
		<< ". Ever been copied : " 
		<< (test3.EverBeenCopied() ? "YES" : "NO") 
		<< std::endl;
}

The following is a summary of the code above :

  • The client code DoTest() will make 3 instances of Test.
  • The first one test1 is created by using an integer.
  • The other 2 are created out of copies of Test objects.
  • test2 is created as a copy of test1.
  • test3 is created as a copy of test2.
  • test3 is then never used as a copy constructor parameter.
  • The integer values of test1, test2 and test3 are displayed.
  • The question of whether any of the instances have been used to make a copy is answered via using the EverBeenCopied() member function.
  • The following is the console output :

test1.m_int : 100. Ever been copied : YES
test2.m_int : 100. Ever been copied : YES
test3.m_int : 100. Ever been copied : NO

  • The output is fully consistent with the client code.

4.9 The important point to be understood from this simple example is that the author of the Test class specifically did not want a copy constructor with a const reference parameter (recall points 4.6 and 4.7).

4.10 The spirit of this being that when an instance is being used to create another instance as a copy of itself, we want this fact to be remembered (hence the m_bEverBeenCopied member).

4.11 Similarly, when a std::auto_ptr instance has been used to create another instance as a copy of itself, the current auto_ptr’s internal pointer must be set to NULL in order that ownership be transferred to the new instance.

4.12 This is why the copy constructor for std::auto_ptr must take a non-const reference parameter. And it is also why a copy constructor with a const reference parameter must not be defined automatically by the compiler.

4.13 If we change the DoTest() code such that the declaration for test1 is as follows :

const Test test1(100);

we will get the following compiler error :

error C2558: class ‘Test’ : no copy constructor available or copy constructor is declared ‘explicit’

Does this look familiar ?

5. Conclusion.

5.1 What then do we use ? Is there a smart pointer type that does not impose the same restriction as the std::auto_ptr class ?

5.2 Enter the boost shared_ptr class. According to the boost library description of the shared_ptr class :

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

5.3 We shall explore this class in the next part of this series of articles.

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

3 thoughts on “Storing C++ Objects in a STL Vector Part 2

  1. This is very helpful. Thanks for the very good article!

    Posted by raja | July 10, 2013, 7:38 am

Trackbacks/Pingbacks

  1. Pingback: Storing C++ Objects in a STL Vector Part 1 « limbioliong - December 25, 2012

  2. Pingback: Storing C++ Objects in a STL Vector Part 3. « limbioliong - January 3, 2013

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: