Author : Mumit Khan
Page : << Previous 2 Next >>
Step 3a requires the construction of a data member of type X as in the Step 1, and hence requires a default constructor. Step 2b uses the STL allocator interface to construct the object from argument x using placement new and hence requires a copy constructor. The typical construct looks like the following:
template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
new (p) T1(value);
}
Step (3) requires a copy constructor (3b) in addition to a default constructor (3a).
Here we are replacing the first element of the list with a new object, x2. Here the front method returns a reference (lvalue) to the data member of the first element in the list and it is assigned a new value x2. This operation hence requires the assignement operator (ie., operator=).
Step (4) requires an assignment operator, ie., operator=(const X& x).
Here we want to remove the element, if any, in the list that equals the value x3. The code looks like the following:
template <class T>
void list<T>::remove(const T& value) {
iterator first = begin();
iterator last = end();
while (first != last) {
iterator next = first;
++next;
if (*first == value) // <-------- (5a)
erase(first);
first = next;
}
}
The remove member starts in the beginning of the list and searches till either the end is reached or a value equalling value argument is found; if found, remove removes the element from the list and calls the destructor. Note in Step (6a), we need the equality operator (operator==) defined for this to work.
Step (5) requires an equality operator, ie., bool operator==(const X& x).
Now we sort the list. The sort member use an in-place merge sort algorithm that requires the less-than relation defined for the object (Step 6a below).
template <class T>
void list<T>::merge(list<T>& x) {
iterator first1 = begin();
iterator last1 = end();
iterator first2 = x.begin();
iterator last2 = x.end();
while (first1 != last1 && first2 != last2)
if (*first2 < *first1) { // <-------- (6a)
iterator next = first2;
transfer(first1, first2, ++next);
first2 = next;
} else
first1++;
if (first2 != last2) transfer(last1, first2, last2);
length += x.length;
x.length= 0;
}
template <class T>
void list<T>::sort() {
if (size() < 2) return;
list<T> carry;
list<T> counter[64];
int fill = 0;
while (!empty()) {
carry.splice(carry.begin(), *this, begin());
int i = 0;
while(i < fill && !counter[i].empty()) {
counter[i].merge(carry);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if (i == fill) ++fill;
}
while(fill--) merge(counter[fill]);
}
Step (6) requires a less-than operator, ie., bool operator<(const X& x).
Here the list object goes out of scope and is automatically destructed by the C++ runtime system. The destructor for list in turns calls the destructor for all the elements that are in the list. Hence the object requires a destructor.
Step (7) requires a destructor
The following are automatically supplied by the compiler if not defined by the user:
X() -- default constructor, but only when no other constructor is defined
X(X const&) -- copy constructor
operator=(X const&) -- assignment operator
~X() -- destructor
If X in this example contains pointers, please be sure to define all of these instead of leaving it to the compiler.
The following must be defined explicitly by the user:
bool operator==(X const&) -- equality operator
bool operator<(X const&) -- less-than operator
Note that if we had not used the remove and sort members, most smart compilers would not require X to define these two operators.
Pointers and STL
As you might've noticed, STL containers manage the storage for objects, not pointers, and this has caused some trepidation about using STL for projects which need to store pointers in various STL containers. I strongly suggest people revisit their designs and not store pointers, but if you have no choice, here's what I have found so far regarding STL containers and pointers to defined types.
Gotcha's with storing pointers to objects
Contrary to what some believe, STL does not care if you're storing pointers to objects instead of objects in its containers. However, more often than not, containers of pointers may be a design flaw that leads to memory leaks and such lovely things. There are a few obvious exceptions:
Large objects that are too expensive to duplicate and are already constructed on the heap.
Single object stored in multiple containers. This is quite common and I believe the right way to do is to wrap the pointers into a class the manages the objects, perhaps via a reference count.
When you need to store objects derived from a (or a set of) base objects in a container. This is quite common in CAD systems where most manipulable objects are derived from a common base with a set of common semantics. See here for an example. Remember that C++ != Smalltalk, and true heterogeneous containers are simply too messy to do in C++.
There are few notable gotcha's:
No pointers to local variables please. See the function change_phno for an example of this.
Who manages the destruction? See here for an example of templatized sequence destructor.
Most STL containers use < for comparison which may be meaningless in some contexts. This is where Smart pointers shine.
Be careful when supplying a Comparator to STL containers need one, such as SET, MAP, etc. See here for a rather involved example. Also see here for another example.
A better solution is to wrap the pointers in a simple class that you store in STL containers. For a trivial example, see here.
Some compilers and STL implementations seem to have inordinate amount of trouble when you store pointers to objects instead of objects, and it stems from construct and destroy functions in STL allocator design; eg., HP reference implementation comes with destroy specialized for pointers to all built-in types, so it works fine if you store int* in a container, but not when you store X*, where X is some user-defined data type. See here for Benjamin Scherrey's note on how to manage this.
Storing pointers in STL containers: Example code
Deallocating pointers stored in STL containers
Who owns the storage?
More gotchas in storing char*
Storing pointers in STL containers: Example code
The following example is an excerpt from my c.l.c++ posting on the subject of storing the same object in multiple container.
#include <stl.h> // or individual includes if you like
// need list.h, set.h and algo.h
#include <iostream.h>
//
// THIS IS VERY IMPORTANT (see note above). You have to tell the set
// or multiset or map to compare the objects pointed to rather than
// the pointers these containers are storing.
//
struct compare {
bool operator() (const int* i1, const int* i2) const {
return *i1 < *i2;
}
};
void print(int* i) {
cout << " " << *i;
}
int main(int, char*[]) {
list<int*> list1;
//
// create a list of new'd integers.
//
for(int i = 0; i < 5; ++i) {
list1.push_back(new int(i * i));
}
cout << "List of int*: (";
for_each(list1.begin(), list1.end(), print);
cout << ")" << endl;
//
// now put these integers into a set. Note that I'm using a
// custom comparator to compare the integers, not the pointers.
//
set<int*, compare> set1;
copy(list1.begin(), list1.end(),
insert_iterator<set<int*, compare> > (set1, set1.begin())
);
cout << "Set of int* : [";
for_each(set1.begin(),
Page : << Previous 2 Next >>