—By 5ean Kent
|
A |
s you have been reading through this book, you have no doubt heard plenty about the mathematical construct known as a vector. Well, here you are going to be introduced to another kind of vector, a
data storage vector.
The Standard Template Library (STL) is a collection of container classes, iterator classes, and other utility classes and functions. A container is just that, it contains data of a user-specified type. The nice thing about STL containers is that they clean up after themselves, meaning that any memory they allocate, they also free. However, this doesn’t include any memory you allocated. Iterators are a type of class that points to the data contained within a container class. An iterator has the capability to move through the elements inside of the container, giving you access to the elements that the iterator points to.
The STL vector class (from now on just called a vector) is a container object that stores its elements in a linear arrangement, allowing for fast insertions and deletions at the end of the vector, and slower insertions and deletions in the middle or at the beginning.
When using the function vector<>::end, the return value will be the element after the last element in the vector. You will find that this “past the end” theme is repeated throughout STL.
The first thing you need to do to use a vector is to include the header file that it is contained in:
#include <vector>
You will notice that there is no. h extension on it, which is not a typo. STL headers in all of the implementations that I have used do not
have an extension. The next thing you need to do is to declare a vector; in this case, you are declaring a vector of integers:
std::vector<int> vec; // Declares a vector that will contain integers.
So what is up with this std:: thing? Well, std is a namespace, which I won’t go into much, other than to say that for a C++ program, all you need to do to avoid using this std:: is to add this line after the include:
using namespace std;
However, in a C++ program where you have multiple files, including headers and such, it is generally a good idea to just stick to using the std:: extension to prevent including namespaces unintentionally.
All right, so far you have included and declared a vector that will contain integers. Now you will insert some data into it. Inserting data at the end of a vector is easy; you just use the push_back function. The following code will insert the numbers 0-9 at the end of the vector:
for(int i=0; i < 10; i++)
vec. push_back(i); // Inserts i onto the end of the vector
To remove data from the end of a vector, you simply use the pop_back function. The pop_back function takes no arguments, and returns void. So, if you wanted to remove that last nine from the vector, you would do the following:
vec. pop_back(); // Removes the 9 from the end of the vector
Now that you have some data stored in your vector, you need to learn how to access the data. To do so, you use a little thing called an iterator. An iterator at its most basic form is just a class that gives you access to the data stored in a container on an element-by-element basis. You can use iterators for inserting, deleting, searching, and sorting the data stored within said container. So let’s create an iterator in order to walk through your data and print it:
std::vector<int>::iterator l, endi;
endi = vec. end(); // Returns the element "Past the end" of the // last element
for(l = vec. begin(); // Returns the first element in the vector
l!= endi; // Checks to make sure that we are not at the end ++l) // Moves l to the next element, using ++l instead of l++ is // faster because you don’t create a copy
}
Not that difficult, eh? To insert data into a vector at any point, you must use the vector<>::insert() function. A warning, though: If you find that you are doing a lot of insertions and deletions anywhere except at the end of a vector, it is advisable that you look into one of the other container classes instead. Insertions at points other than the end of a vector are more expensive than at the end. To insert at, say, the beginning of a vector, you must first obtain an iterator pointing to the beginning, and then you merely call the insert function with the iterator, as well as the data you want to insert.
std::vector<int>::iterator l = vec. end(); while(l!= vec. begin())
{
—l;
vec. insert(vec. begin(), *l) // Insert at the beginning
// the element contained in l
}
There are two ways to remove data from a vector at points other than the end. One is to use the vector<>::erase function and the other is to use the remove functions. The difference between them is that erase will remove and resize the vector, whereas remove will preserve the relative placements of the elements, but will remove the specified elements.
// Using remove:
std::vector<int>::iterator newend;
// Searches the vector for all 7’s and removes them newend = std::remove ( vec. begin( ), vec. end( ), 7 );
cout << "Vector vec with value 7 removed is [ " ; for ( l = vec. begin( ) ; l!= vec. end( ) ; l++ ) cout << *l << " "; cout << "]." << endl;
// To change the sequence size, use erase
The
^ v1-1 ■"_^ ^ ‘ lJ
vec. erase (newend, vec. end( ) );
cout << "Vector vec resized with value 7 removed is [ " ; for ( l = vec. begin( ) ; Iter1 != l. end( ) ; l++ ) cout << *l << " "; cout << "]." << endl;
The next section of code removes all occurrences of 7 and resizes the vector.
// Using just erase: vec. erase(vec. begin(), vec. end(), 7);
The complete set of the remove functions includes remove_if, remove_copy, and remove_copy_if. The remove_copy and remove_copy_if functions create a new range of values, copying only those values that are not part of the value specified. The remove_copy_if and remove_if functions take a function argument called a binary predicate, which is a true-false function that will return true for those elements that match the predicate, and false for all others. These functions then remove all elements that meet the binary predicate.
bool gt6( int val )
{
return (val > 6); //returns true if greater than 6
}
std::vector<int> v2;
newend = std::remove_copy_if ( vec. begin( ), vec. end( ), v2.begin( ), gt6 ); // copies to a new vector containing all values // less than or equal 6
At some point, you will likely want to sort your vector so that you may do cool things like use a binary search to find elements. Sorting a vector is a fairly simple process; you just use the sort function. The sort functions are included using the algorithm header.
#include <algorithm>
// The following code will sort your vector of ints in ascending order std::sort(vec. begin(), vec. end());
The sort algorithm can also take a function argument that will be used to determine whether an item should be moved. STL has several of these functions already; you just need to include the <functional> header.
#include <functional>
#include <algorithm>
//sorts using the greater function object ( descending order ) std::sort(vec. begin(), vec. end(), greater<int>());
The greater<int>() part is actually a function object, which is basically an overloaded operator() that’s contained within a structure or a class.
There are a few methods for searching a vector; however, this section covers only the use of the find functions as well as the binary search functions. The find functions work on both sorted and unsorted vectors. They work by comparing every element to the value being searched for. The binary search functions require a sorted vector, but they take significantly less time to find the element.
The find function has four versions. They are find, find_end, find_first_of, and find_if. The find function finds the first occurrence of an element. The find_if function finds the first occurrence of an element that meets a specified condition. The other two functions,
find_end and find_first_of, aren’t covered here.
To use find, simply call it with the range you want to search and the element you want to find. So, to find a number within a vector of integers, you would do the following:
#include <algorithm>
// Starts at the beginning of the vector, and proceeds to the end
// Till it finds a 7, or returns the element past the end if it doesn’t
std::vector<int>::iterator i;
i = find(vec. begin(), vec. end(), 7);
if(i!= vec. end()) // We found it
To use the find_if function, you simply do the following: #include <algorithm>
bool IsGreaterThan5( int val ) {
return (val > 5);
}
std::vector<int>::iterator i;
//Will find the first element that is greater than five i = find_if(vec. begin(), vec. end(), IsGreaterThan5); if(i!= vec. end()) // if we found it
. // Do stuff
The binary search functions require a sorted vector, but can take significantly less time to find the element you are searching for. The binary search functions are binary_search, lower_bound, upper_bound, and equal_range. The binary_search function returns true if the element searched for exists. The lower_bound function finds the first occurrence of an element within a vector, or the position it would be at if it existed. The upper_bound function finds the element past the last occurrence of the element searched for within a vector, or where it would be if the element searched for existed. The equal_range function is just a combination of the lower_bound and upper_bound functions.
To use the binary search functions, you simply pass it the range of sorted elements you want to search and the element you want to find.
#include <algorithm>
std::vector<int> vec; for(int j = 0; j < 10; j++)
{
vec. push_back(j); // Insert 2 copies of the number at the end. vec. push_back(j);
}
sort(vec. begin(), vec. end()); // Sort the vector
bool found = binary_search(vec. begin(), vec. end(), 7); //Is there a 7? assert(found == true); //should be std::vector<int>::iterator k, l;
k = lower_bound(vec. begin(), vec. end(), 5); // Find the first five
l = upper_bound(vec. begin(), vec. end(), 5); // Find the item past the five
assert(*k == 5); // should be the first five
assert(*l == 6); // Should equal the element after the last five
So far, you have just been using vectors containing integers. Although integers are fine and dandy, you will probably want to use your own user-defined types with vectors. This section covers a few issues about using your own objects with vectors.
The first thing you need to do before you can store an object in a vector is define that object. An object that is going to be stored in a vector should include a copy constructor, because copy constructors are used when moving objects around. An overloaded assignment operator can also be helpful.
class MyObject { int age int height; //in CM public:
MyObject() {}
MyObject( int a, int h) : age(a), height(h) {}
// Copy Constructor MyObject(const MyObject& a) : age(a. age), height(a. height) {} void SetAge(int a) { age = a; } void SetHeight(int a) { height = a; } int GetAge() { return age; } int GetHeight() { return height; }
//Overloaded assignment operator MyObject& operator=(const MyObject& r) { age = r. age; height = r. height; return *this; }
};
There is the basic object. To tell a vector to use it, you simply replace the int portion of the vector with MyObject:
std::vector<MyObject> vec; //vector to hold MyObject types
Now comes the tricky part—storing a MyObject inside of the vector.
To do so, you call push_back with a MyObject, like so:
// Stick 10 random MyObject’s into the vector for(int j = 0; j < 10; j++)
{
vec. push_back(MyObject(rand()%20+1, rand()%120 + 1));
}
To sort the objects, you must either overload the < operator or supply the sort function with another function. You will notice in the example code that you are passing everything by reference. This avoids a copy and thus saves you memory and time. This example sorts the vector by age:
#include <algorithm>
bool LesserAge( MyObject& l, MyObject &r) {
return (l. GetAge() < r. GetAge());
}
//or:
bool operator<( MyObject& l, MyObject &r) {
return (l. GetAge() < r. GetAge());
}
sort(vec. begin(), vec. end(), LesserAge); // Sorts by age sort(vec. begin(), vec. end()); // Sorts by age using <
Because the find function uses the == operator, you must overload it to work with your class. This is a simple operation:
#include <algorithm>
bool operator==(MyObject l, MyObject r) {
if(l. GetAge() != r. GetAge()) return false; if(l. GetHeight() != r. GetHeight()) return false; return true;
}
std::vector<MyObject>::iterator j;
j = std::find(vec. begin(), vec. end(), MyObject(10, 120)); if(j!= vec. end()) //We found it
The equality operator (== operator) is used in comparisons to determine whether one element equals another. However, it will only work on C++ defined types. To get around this limitation, you can overload it to accept other types. In this case, it is overloaded to accept MyObject types and to compare them based on both age and height. However,
you could just as easily compare based on age alone, thus allowing for levels of equality.
One of the disadvantages of storing an object inside of a vector is that whenever it gets moved, it has to copy the entire object to its new location. For small vectors, this may be possible, but when you start to get larger vectors, it becomes unacceptable. The way to avoid this is to use pointers. A pointer is quite a bit smaller than most objects, so moving them around takes a lot less time. However, because pointers use memory you have allocated, you must also remember to free that memory when you are done.
Declaring a vector to hold pointers to objects is fairly simple; you just replace the MyObject portion with the appropriate conversion:
std::vector<MyObject*> vec;
To put something into the vector, all you really have to do, from the last code, is add the new operator:
// Stick 10 random MyObject’s into the vector for(int j = 0; j < 10; j++)
{
vec. push_back( new MyObject(rand()%20+1, rand()%120 + 1));
}
Sorting the vector is a bit different, because the sort operator will use a binary predicate that you specify or the < operator by default. Because a pointer is just an integer, the < operator will sort by the memory address and not the contents of the MyObject.
#include <algorithm>
bool GreaterAgePtr( MyObject* l, MyObject *r) {
return (l->GetAge() > r->GetAge());
sort(vec. begin(), vec. end(), GreaterAgePtr); // Sorts by age sort(vec. begin(), vec. end()); // Sorts by age using < (memory address)
Searching has the same problem as sorting because it uses the == operator, except in this case there is a way around it:
#include <algorithm>
bool operator==(MyObject *l, MyObject r) {
if(l->GetAge() != r. GetAge()) return false; if(l->GetHeight() != r. GetHeight()) return false; return true;
}
std::vector<MyObject>::iterator j;
= std::find(vec. begin(), vec. end(), MyObject(10, 120)); f(j!= vec. end()) //We found it
Again, you are overloading the equality operator (==) just as you did earlier. However, this time, it can compare a pointer to a MyObject object and compare a MyObject object to itself. After you are done with your vector of pointers, you must free the memory that you allocated. This is a fairly simple process:
#include<algorithm>
}
};
std::for_each(vec. begin(), vec. end(), DeletePtr<MyObject>());
The class DeletePtr with the member function operator () is called a function object. All it does is delete MyObject pointers. If you wanted to, you could make it delete integer pointers by simply changing this line:
for_each(vec. begin(), vec. end(), DeletePtr<MyObject>());
to:
for_each(vec. begin(), vec. end(), DeletePtr<int>());
Simple and easy (and useful too).
If you are wondering about some of the applications of vectors in games, I have an idea. My idea is for a simple scene-graph. If you derive all of your objects from some base object, you could use a vector of pointers to the base object. This would allow you to easily do updates, collisions, and rendering. Because you would know that all objects before the current object had already moved and had been collision tested, you wouldn’t have to test against them for your current object. Also, you could reuse vector elements, such as when a creature dies, so you set its vector element to an empty object, and when you need a new object, just reuse the empty ones.
Finally I would recommend that you do some more research into template programming, especially pertaining to the Standard Template Library. It has many types of containers, including deques, lists,
sets, multisets, and maps. Each container has its own advantages and disadvantages, so picking the right one is not always easy. There is generally one container that will be better suited for a certain application than another.