- Vector (STL)
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 charand intwithin 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
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.
A C++ program that is to use vectors must
is non-standard and deprecated. GCC accepts both, but gives a compiler warning when
A vector is initialized using:where "
type" is the data type the vector is to store, and "
instance" is the
variablename of the vector.
Type" can be a primitive or any user defined
struct. However care must be taken to avoid
vectorclass models the [http://www.sgi.com/tech/stl/Container.html Container] concept, which means it has
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.
vector::insert- Inserts elements into a vector (single & range), shifts later elements up. O(n) time.
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. O(n) time.
vector::pop_back- Erases the last element of the vector, O(1) time. Does not usually reduce the memory overhead of the vector Amortized O(1) time.
vector::clear- Erases all of the elements. (For most STL implementations this is O(1) time and does not reduce capacity)
vector::reserve- Changes capacity (allocates more memory) of the vector, if needed. In many STL implementations capacity can only grow, and is never reduced. O(n) if the vector expands. O(1) if not.
vector::resize- Changes the vector size. O(n) time.
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 usage example
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."
Semantically picturing the vector "push_back( data )" operation. Note the size of the vector increases from 6 to 7 after the operation.
Semantically picturing the vector "pop_back()" operation. Note the size of the vector decreases from 7 to 6 after the operation.
Semantically 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.
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. This makes them particularly useful for storing data in lists whose length may not be known prior to setting up the variable, but where removal from the array (other than perhaps at the end) is rare.
Like other STL containers, vectors may contain both primitive data types and complex, user-defined classes or structs. Unlike other STL containers, such as
deques and lists, vectors allow the user to denote an initial capacity for the container, which, if used correctly can allow for faster execution of the program.
One major benefit of vectors is that they 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 whereas linked-lists and sets do not support random access or pointer arithmetic. Array-style pointer arithmetic can also be used with vectors - for instance the address of the (zero-indexed) 7th element in a vector "v" is &v  .
Erasing elements from a vector or even clearing it entirely does not necessarily free any of the memory associated with that element. The rationale here is that a good estimate of the future size of the vector is the maximum size of the vector since its creation.
Vectors are also inefficient at removing or inserting elements other than at the end. Such operations have O(n) (see
Big-O notation) complexity compared with O(1) for linked-lists. This is offset by the speed of access - access to a random element in a vector is of complexity O(1) compared with O(n) for general linked-lists and O(log n) for link-trees.
* 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.
* [http://www.sgi.com/tech/stl/Vector.html SGI STL specification of vector]
* [http://www.cplusplus.com/reference/stl/vector/ C++ reference: vector]
* [http://www.roguewave.com/support/docs/sourcepro/edition9-update1/html/stdlibref/vector.html C++ Header description]
Wikimedia Foundation. 2010.
Look at other dictionaries:
Vector — may refer to: In mathematics * Euclidean vector, a geometric entity endowed with both length and direction, an element of a Euclidean vector space * Coordinate vector, in linear algebra, an explicit representation of an element of any abstract… … Wikipedia
Vector (C++) — Стандартная библиотека языка программирования C++ fstream iomanip ios iostream sstream Стандартная библиотека шаблонов algorithm … Википедия
STL (file format) — Infobox file format name = STL icon = caption = extension = .stl mime = type code = uniform type = magic = owner = 3D Systems released = latest release version = latest release date = genre = Stereolithography container for = contained by =… … Wikipedia
Vector (informática) — Para otros usos de este término, véase Matriz. Matriz unidimensional con 10 elementos. En programación, una matriz o vector (llamados en inglés arrays) es una zona de almacenamiento continuo, que contiene una serie de elementos del mismo tipo,… … Wikipedia Español
List of vector graphics markup languages — The following is a list of vector graphics markup languages. =2D vector graphics= *SVG *XAML User interface language using vector graphics for images. *CGM *VML *Xar *MetaPost *Asymptote *Graphics Layout Engine *Remote imaging protocol *PSTricks… … Wikipedia
Standard Template Library — C++ Standard Library fstream iomanip ios iostream sstream string … Wikipedia
Стандартная библиотека шаблонов — Стандартная библиотека языка программирования C++ fstream iomanip ios iostream sstream Стандартная библиотека шаблонов … Википедия
C++ — У этого термина существуют и другие значения, см. C. См. также: Си (язык программирования) C++ Семантика: мультипарадигмальный: объектно ориентированное, обобщённое, процедурное, метапрограммирование Тип исполнения: компилируемый Появился в … Википедия
Standard Template Library — Стандартная библиотека шаблонов (STL) (англ. Standard Template Library) набор согласованных обобщенных алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций. Стандартная библиотека шаблонов до включения в… … Википедия
C++ — Desarrollador(es) Bjarne Stroustrup, Bell Labs Información general … Wikipedia Español