One of the challenges of coding in C++ is managing the data used by your programs. How, for example, do you store and manipulate a collection of objects that you intend to work with while your program is running?
The choice of an array as the underlying mechanism is not always the most flexible nor the most memory efficient approach. How, for instance, do you choose an initial size? How do you manage "holes" in the array caused by objects that are removed? How do you locate the objects you've stored in the array? What if you want to store and retrieve objects using a key? In all of these instances, you would have to write custom code around your array to accomplish all of these tasks.
This article will give you a head start to solving data management problems like these, using the Standard C++ Library that ships with C++ Builder. This library, which includes the containers and algorithms known as the Standard Template Library (STL), addresses these problems by employing C++ templates to implement containers that can store, manipulate, and retrieve objects. Although the examples in this article are extremely simple, they give you some idea of the power of the STL.
There are some concepts that you should understand before we explore the STL examples. The following sub-sections provide a quick overview.
An iterator is a pointer-like mechanism that allows you to reference items in a container. Iterators can be used to specify a particular item or range of items, and are used as parameters to some of the most powerful container management functions. Iterators will be used in the code throughout the article, and described in more detail with each example.
Containers can hold just about anything, including primitives (such as int, float, and char), user defined types (including objects), and pointers. There are some basic rules you should be aware of when working with them.
All values placed into a container are copied there using the assignment operator (=). The effects of this are clear when using primitive C++ types or pointers; the value of the primitive or the pointer is simply placed into the container.
If you are placing objects in a container, however, there are ramifications to the assignment operator. The objects are still copied, but how you code the class controls whether the copy is deep or shallow. For a detailed explanation of deep and shallow copies, you should consult a good C++ text.
In a nutshell, a deep copy is accomplished via a copy constructor, and should be used if your object contains pointers to anything (other objects, character buffers, etc). This insures that you get a distinct object that has allocated its own memory or instantiated its own version of any aggregate objects. In most cases this probably won’t be an issue, as you will often be storing pointers in containers instead of actual objects.
Here are some tips to remember when removing primitives, pointers, or objects from a container:
· Removing a primitive or a pointer causes it to be discarded by the container.
· Removing an object causes it to be discarded by the container as well, but the object’s destructor is called in the process.
· If you tell a container to remove a pointer (whether it’s a character buffer or an object), that memory is lost (leaked) unless you’ve retained a local copy of that pointer with which you can later call delete. Containers do not automatically delete memory!
Here are some tips to remember when retrieving primitives, pointers, or objects from a container:
· Retrieving a primitive gives you a copy in your local variable.
· Retrieving an object will copy it to your local variable (using a deep or shallow copy depending on whether you’ve supplied a copy constructor).
· Retrieving a pointer gives you the value of the pointer so that you can reference the "contained" object (to invoke methods, for example).
In large systems, the danger of names clashing between classes and libraries increases. To mitigate that risk, namespaces were added to C++. They are a means of packaging classes and data so that they can be referenced without conflict. The STL, for example, lives in a namespace called std.
If you look just below the #include statements in Listing A you’ll see this line:
using namespace std; The purpose of this is to let the compiler know that we’ll be using members of the std library. This saves you a bit of "resolution specification" typing later on. For example, look at the following vector definitions:
vector<int> x;
std::vector<int> y;The declaration for vector x appears in a file containing the using directive. The declaration for y does not, and requires that you supply sufficient information for the compiler to locate the correct vector.
We’ll start with the vector, as it is most like the C++ array. The major differences are the management of memory to hold the vector (dynamic), and the means of accessing the items therein. The sample program defines a vector of integers (see the VectorButtonClick() function in Listing A. It contains a vector declaration called myInts. You can create a vector of virtually any type by inserting that type within the <> symbols, such as:
vector<float> myFloats;
vector<TButton*> myButtons;The declarations simply indicate the type of elements the container holds, and a name by which to reference the container.
The VectorButtonClick() function creates a vector of integers, and shows you how to add and delete members. At first, manipulating the vector contents through pushes and pops may seem a little strange. It’s the price you pay for the flexibility of the particular container you’re using, and you get used to it with practice.
The code places the values 1 through 9 in the vector using the push_back() function. This appends the values to the existing vector. It then adds the value 10 to the end, and 0 at the front.
Adding the value 10 is easy because we already know how to use push_back(). To accomplish the insertion, though, we have to use an iterator. We call the insert() function and tell it which vector member to insert before via the begin() function (begin() returns an iterator pointing to the first value in the vector).
Notice that vectors support the use of the array subscript operator ([]) to access values at an absolute location (just like an array). You should only use the array subscript operator when you know that the offset you are accessing actually exists in the vector.
Next, the value 10 is popped off of the back of the array, and replaced with 25. After showing the values in ListBox1 one last time, the vector is cleared (removing all members). The call to clear() isn’t really necessary because the vector is about to go out of scope, but it’s a function you should be aware of.
Because we’ve stored primitives in the vector, we aren’t concerned with the container’s contents. If the vector were holding pointers, then we would have walked through them and deleted the memory prior to calling clear() or letting the container go out of scope. The following section on lists shows how pointers are dealt with.
To demonstrate any of the examples in this article, run the program and click on the button labeled with the name of the container you want to see.
A list stores a linear sequence of items. While it does share many of the characteristics of a vector, it doesn’t support random access (via the [] operator). You can, however, add, delete, or retrieve values anywhere in a list using an iterator.
If there is a lot of variation in the size of your collection throughout its lifetime, a list might be a better choice than a vector. Vectors can incur performance penalties for growth, whereas the overhead associated with list operations remains relatively constant regardless of the size of the list.
The ListButtonClick() function shown in Listing A implements the list example. The example stores a list of words and then re-arranges them to form a sentence. You’ll notice that the list template also supports some of the same functions as vector (such as the push_back() function).
In this example, we’re storing pointers instead of primitives. This means that we’re responsible for memory management. It also means that there’s an extra step (some indirection) when retrieving list contents.
The example begins by creating a list that holds pointers to four objects of type Wisdom (each of which manages a character buffer holding a word that we’ll use later to create the sentence). As each Wisdom object is instantiated, push_back() is used to add the new object’s address to the end of the list. We don’t show the Wisdom class definition, but you can download the complete code example from our Web site at www.bridgespublishing.com.
Next, we’ll use the wisIt iterator to step through the entire list (using the begin() and end() functions to signify the list’s boundaries). Not only can iterators be used in for loops, but they also support the increment (++) and decrement (--) operators to move back and forth. Don’t forget that the wisIt iterator is "pointing" to a pointer! The proper way to call the say method on the Wisdom object is:
(*wisIt)->say();Because we placed the word "Have" at the end of the list, the for loop used to print out the sentence dutifully constructs "a nice day Have." This is obviously wrong, but can be fixed by removing "Have" from the end of the list and placing it at the beginning. I do this by pointing wisIt to the end of the list, and retrieving Have’s pointer. Once I have the pointer, I supply it as an argument in a call to remove() to take it out of the list.
Next, the push_front() method is called to insert the pointer (which we’re still holding on to) at the beginning. Now when the sentence is constructed, the wording is correct.
One of the last things the list example does is call delete on all of the Wisdom objects after adding the words to a character array called sentence. This way no memory will be lost when myWisdom goes out of scope at the end of the ListButtonClick() function.
Maps are one of the most useful containers. You can store virtually anything in a map and retrieve it with a key (the key must be unique with the map container—if you need duplicate keys, check out the multimap template).
In the map example, the string type from the Standard C++ Library was used (note the lower case s). Don’t get this class confused with the VCL’s String class!
The example (found in the MapButtonClick() function in Listing A) stores some objects containing the full name of a president and a meaningless integer value. One of the most interesting features of maps is the ability to insert and retrieve objects using brackets (like array subscripting). For example, we added and retrieved Lincoln like this:
anyBody["honest"] =
Person("Abe Lincoln", 98);
Person who = anyPerson["honest"]; In this example anyBody is an STL map container, and Person is a class I created to manage people. Be aware, however, that searching for a person using a construct like anyPerson["honest"] will cause that person to be created in the map if he or she doesn’t exist! For this reason, any object you plan to store in a map must have a default constructor (one that takes no arguments so it can be called to create a "vanilla" object). An alternative search method (and one without any undesirable side effects) is the find() function, which sets an iterator to point to the object if it exists (or the end of the container if it doesn’t):
map<string, Person>::iterator persIter;
persIter = anyBody.find("honest");
if (persIter != anyBody.end())
// then the record existed
else
// it didn’t!There are many other useful functions that operate on the map container that you can learn from any good STL book.
Besides a number of containers and iterators, the STL also comes with some algorithms that you can apply to container contents. Table A describes some of the more interesting ones.
Table A: STL Algorithms
for_eachApply a function to each member of a container.
copyCopies a sequence of members from one container to another.
fillFills a range in a container with a specified value.
max_elementFinds the largest element within a range in a container.
mergeMerges two sequences into a third.
removeRemoves a specified range of elements from a container.
reverseReverses a specified range.
sortSorts a specified range.
Here’s an example of using the copy algorithm on two integer vectors. It copies the entire contents of vector a to vector b:
copy(a.begin(), a.end(), b.begin());The Standard C++ Library’s containers are powerful features of the language, and the simple examples in this article are only the tip of the iceberg. If you plan to explore containers in more depth, it’s a good idea to pick up some books about templates and the STL.
Listing A: Unit1.cpp
#include <vcl.h>
#include <stdlib>
#include <vector>
#include <list>
#include <map>
#include <string>
#pragma hdrstop
#include "Unit1.h"
#include "WrkObjs.h"
using namespace std;
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}void __fastcall
TForm1::QuitButtonClick(TObject *Sender)
{
exit(0);
}
void __fastcall
TForm1::VectorButtonClick(TObject *Sender)
{
vector<int> myInts;
ListBox1->Clear();
ListBox1->Items->Add("Vector Example");
ListBox1->Items->Add("==============");
// Add numbers 1-9 to myInts
for( int y = 1; y < 10; y++ )
myInts.push_back(y);
// Add them to ListBox1 using array subscripting
ListBox1->Items->Add(
"After adding 1 through 9:");
for(int y = 0; y < 9; y++)
ListBox1->Items->Add(String(myInts[y]));
// Add 10 to the end of the vector
myInts.push_back(10);
// Insert a 0 at the front of the list
myInts.insert(myInts.begin(), 0);
// Show the contents of the vector
ListBox1->Items->Add("After adding 0 and 10:");
for( int y = 0; y < 11; y++ )
ListBox1->Items->Add(String(myInts[y]));
// For practice, remove the 10 from the end
// and place a 25 in the there.
myInts.pop_back();
myInts.push_back(25);
// Show the contents of the vector again
ListBox1->Items->
Add("After deleting 10 and adding 25:");
for( int y = 0; y < 11; y++ )
ListBox1->Items->Add(String(myInts[y]));
myInts.clear();
ListBox1->Items->Add(
"Vector example complete!");
}
//----------------------------------
void __fastcall
TForm1::ListButtonClick(TObject *Sender)
{
list<Wisdom*> myWisdom;
list<Wisdom*>::iterator wisIt;
char sentence[50];
char* myWords[] = {
"a ", "nice ", "day ", "Have "};
ListBox1->Clear();
ListBox1->Items->Add("List Example");
ListBox1->Items->Add("============");
// Add all words to the list from the array.
for( int x = 0; x < 4; x++ ) {
char* wordMemory =
new char[strlen(myWords[x]+1)];
strcpy(wordMemory, myWords[x]);
myWisdom.push_back(new Wisdom(wordMemory));
}
// Form a sentence
ListBox1->Items->Add("My Words of wisdom:");
*sentence = NULL;
for(wisIt = myWisdom.begin();
wisIt != myWisdom.end(); wisIt++)
strcat(sentence, (*wisIt)->say());
ListBox1->Items->Add(sentence);
// Move "Have" to the beginning of the sentence
wisIt = myWisdom.end();
Wisdom* tmpWis = (*(--wisIt));
myWisdom.remove(tmpWis);
myWisdom.push_front(tmpWis);
ListBox1->Items->
Add("My Words of wisdom (corrected):");
*sentence = NULL;
// Rebuild the sentence again and delete the
// Wisdom objects as we go.
for(list<Wisdom*>::iterator li =
myWisdom.begin();
li != myWisdom.end(); li++) {
strcat(sentence, (*li)->say());
delete (*li);
}
ListBox1->Items->Add(sentence);
}
void __fastcall
TForm1::MapButtonClick(TObject *Sender)
{
map<string, Person> anyBody;
map<string, Person>::iterator persIter;
ListBox1->Clear();
ListBox1->Items->Add("Multimap Example");
ListBox1->Items->Add("================");
// Add some people to the map
anyBody["honest"] = Person("Abe Lincoln", 98);
anyBody["cherry tree"] =
Person("George Washington", 100);
anyBody["watergate"] =
Person("Richard Nixon", 74);
anyBody["pardon"] = Person("Gerald Ford", 76);
anyBody["peanuts"] = Person("Jimmy Carter", 80);
anyBody["scandal"] = Person("Bill Clinton", 92);
// Find a couple of people and show them
Person who = anyBody["honest"];
ListBox1->Items->Add((who.getName()).c_str());
who = anyBody["watergate"];
ListBox1->Items->Add((who.getName()).c_str());
// Delete Gerald Ford by calling erase function
anyBody.erase("pardon");
// The find function is a better way to look
// for entries in the list.
persIter = anyBody.find("pardon");
if (persIter != anyBody.end())
ListBox1->Items->Add((who.getName()).c_str());
else
ListBox1->Items->Add("No such president!");
}