vector (STL)
From Wikipedia, the free encyclopedia
 |
It has been suggested that this article or section be merged into Dynamic array. (Discuss) |
 |
The introduction to this article provides insufficient context for those unfamiliar with the subject. Please help improve the article with a good introductory style. |
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. There would need to be at least two vector instances for such a case -- one for the int variables and one for the char variables. Vectors can, however, store 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.
Contents |
[edit] 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.
[edit] Usage
A C++ program that is to use vectors must #include <vector>. <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.
[edit] 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; }
[edit] 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.
[edit] 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.
[edit] 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.
[edit] 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. It 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. However, vectors do 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.
[edit] 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.
