Vectors (or std::vector) are a C++ implementation of the dynamic array data structure. Their interface emulates the behavior of a C array (i.e., capable of fast random access) but with the additional ability to automatically resize itself when inserting or removing an object.
A vector is a template class that is a part of the C++ Standard Template Library. They can store any type, but are limited to storing only one type per instance. Therefore, they could not store data in the form of both char and int within the same vector instance. Vectors can, however, store pointers to several class objects provided they are all from the same class. Vectors provide a standard set of methods for accessing elements, adding elements to the start or end, deleting elements and finding how many elements are stored.
Comparison with arrays
In C++, arrays are contiguous pieces of memory. They are somewhat like blocks aligned together, each block is then given a number, and to look at the contents of each block one only has to supply the number of the block. All the elements of an array must be of the same type.
A vector is similar to an array but with extended functionality. One of the features of a vector is that if you use the at() function, an exception will be thrown if you try to access an element that doesn't exist. A vector is a template class, a generic array of whatever type you want it to be. This gives vectors a great deal of flexibility, as they can be used as an array of anything. For instance, you can even have a vector of vectors. Vectors can automatically detect out of bounds errors (see Bounds checking) by using the at() method, or skip bounds checking by using operator[]. When using the latter they are very fast for random access. Vectors also have a number of useful functions which can tell you certain properties of the vector. For a full description of each function see functions further down the page.
Usage
A C++ program that is to use vectors must #include <vector>. Header <vector.h> is non-standard and deprecated. GCC accepts both, but gives a compiler warning when <vector.h> is used.
A vector is initialized using:
std::vector<type> instance;
where "type" is the data type the vector is to store, and "instance" is the variable name of the vector.
"Type" can be a primitive or any user defined class or struct. However care must be taken to avoid object slicing.
Functions
The vector class models the Container concept, which means it has begin(), end(), size(), max_size(), empty(), and swap() methods.
- informative
vector::front - Returns reference to first element of vector.vector::back - Returns reference to last element of vector.vector::size - Returns number of elements in the vector.vector::empty - Returns true if vector has no elements.vector::capacity - Returns current capacity (allocated memory) of vector.
- standard operations
vector::insert - Inserts elements into a vector (single & range), shifts later elements up. Inefficient.vector::push_back - Appends (inserts) an element to the end of a vector, allocating memory for it if necessary. Amortized O(1) time.vector::erase - Deletes elements from a vector (single & range), shifts later elements down. Inefficient.vector::pop_back - Erases the last element of the vector, (possibly reducing capacity - usually it isn't reduced, but this depends on particular STL implementation[1]). Amortized O(1) time.vector::clear - Erases all of the elements.
- allocation/size modification
vector::reserve - Changes capacity (allocates more memory) of vector, if needed. In many STL implementations capacity can only grow, and is never reduced.[1]vector::resize - Changes the vector size.
- iteration
vector::begin - Returns an iterator to start traversal of the vector.vector::end - Returns an iterator that points just beyond the end of the vector.
vector<int> v;
for (vector<int>::iterator it = v.begin(); it!=v.end(); ++it/* increment operand is used to move to next element*/) {
cout << *it << endl;
}
Vector usage example
// note: the following requires #include <vector>
vector<int> myVector; // declare a vector of integers named "myVector"
vector<int>::iterator Iter; // creates an iterator necessary to traverse vector
// print a message if the vector is initially empty
if( myVector.empty() )
{
cout << endl << "The vector is currently empty.";
}
cout << endl;
cout << "Adding 1 to the end of the vector." << endl;
myVector.push_back(1); // add 1 to the end of the vector
cout << "Adding 2 to the end of the vector." << endl;
myVector.push_back(2); // add 2 to the end of the vector
cout << "Adding 3 to the end of the vector." << endl;
myVector.push_back(3); // add 3 to the end of the vector
cout << "Adding 4 to the end of the vector." << endl;
myVector.push_back(4); // add 4 to the end of the vector
// show the size of the vector
cout << endl << "Current vector size = " << myVector.size() << endl;
int atTheEnd;
atTheEnd = myVector.back(); // assign the last element to variable "atTheEnd"
cout << "The last element, " << atTheEnd << ", is being removed." << endl << endl;
myVector.pop_back(); // remove the element at the end of the vector
// show the size of the vector again
cout << "Current vector size: " << myVector.size() << endl;
// printing the contents of a vector
// requires traversing through it with an iterator (declared above as "Iter")
cout << "myVector =";
for (Iter = myVector.begin(); Iter != myVector.end(); Iter++ )
{
cout << " " << *Iter;
}
cout << endl;
cout << endl;
// if the vector isn't empty
// use the clear() function to empty it
if( !myVector.empty() )
{
myVector.clear();
}
// print out a successful message if cleared correctly
if( myVector.empty() )
{
cout << "The vector is now empty again." << endl;
}
cout << endl;
The output will be the following:
The vector is currently empty.
Adding 1 to the end of the vector.
Adding 2 to the end of the vector.
Adding 3 to the end of the vector.
Adding 4 to the end of the vector.
Current vector size = 4
The last element, 4, is being removed.
Current vector size = 3
myVector = 1 2 3
The vector is now empty again.
Vector visualization
Picturing the vector push_back( data ) operation. Note the size of the vector increases from 6 to 7 after the operation.
Picturing the vector pop_back() operation. Note the size of the vector decreases from 7 to 6 after the operation.
Picturing the vector resize( int ) operation. Note the size of the vector increases to 9, and the new elements are filled with a default value.
Useful metaphor
It is often helpful to use examples from everyday life as metaphors for the different methods of data storage. In this way, one could think of a vector as people on a crowded subway train. Anytime a person steps onto the train, it represents the v.push_back(data) function, with those persons representing the recurring data type. Upon reaching their destination, the first person to enter would be standing furthest from the platform. This person would be referred to by the v.front() operation. Closest to the exit platform would be the v.back() reference -- the last person to have entered. Although very similar to a traditional Last-In-First-Out data structure (such as a stack), the vector class differs slightly in that it also has an insert function. This insert function would be analogous to somebody from a different car of the train entering from the sides.
Pros and cons
The most convenient part of the vector data structure is its ability to quickly and easily allocate the necessary memory needed for specific data storage without explicit memory management. Like other STL containers, they can be sent primitive data types, or complex, user-defined classes or structs and create an array to store them in a few simple steps. Unlike other STL containers, such as deques and lists, vectors allow the explicit reservation of memory, which can result in faster execution if implemented in programs that require frequent expansion of the vector. Vectors also allow random access; that is, an element of a vector may be referenced in the same manner as elements of arrays are by array indices, and array-style pointer arithmetic also works with vectors. Lists and sets do not support random access or pointer arithmetic. On the other hand, erasing elements from a vector or even clearing the entire vector, however, do not free memory allocated to it, unlike some other containers such as lists and sets. Vectors also are inefficient at removing or inserting elements other than from the end; such operations have O(n) complexity, compared with O(1) for lists. Vectors, along with other STL containers, incur a very small overhead compared to static arrays (depending on the quality of your compiler), and cannot be initialized through an initialization list. Vector is known to be slow when using the MSVC compiler due to the SECURE_SCL flag that, by default, forces bounds checking even in optimized builds.
References
- William Ford, William Topp. Data Structures with C++ and STL, Second Edition. Prentice Hall, 2002. ISBN 0-13-085850-1. Chapter 4: The Vector Class, pp.195–203.
- ^ a b STL Vector reserve() questions - GameDev.Net Discussion Forums
External links
|
