C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
The Standard Template Library is a C++ software library which later evolved into the C++ Standard Library. It provides four components called algorithms, containers, functors, and iterators. More specifically, the C++ Standard Library is based on the STL published by SGI. Both include some...
In computer science, a dynamic array, growable array, resizable array, dynamic table, or array list is a random access, variable-size list data structure that allows elements to be added or removed...
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s called containers, some of the others being sets
Set (C++)
A set is an associative container data structure that is available as part of the C++ Standard Library , and contains a sorted set of unique objects....
The class template std::map is a standard C++ container. It is a sorted associative array of unique keys and associated data. The types of key and data may differ, and the elements of the map are internally sorted from lowest to highest key value...
Templates are a feature of the C++ programming language that allow functions and classes to operate with generic types. This allows a function or class to work on many different data types without being rewritten for each one....
, and can thus be used as a generic framework that may be instantiated e. g. as a vector of integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
In the C++ programming language, the std::string class is a standard representation for a string of text. This class alleviates many of the problems introduced by C-style strings by putting the onus of memory ownership on the string class rather than on the programmer...
, a vector of instances of a user-defined class.
Design
The vector template is defined in header file . Like all other standard library components, it resides in namespace
Namespace
In general, a namespace is a container that provides context for the identifiers it holds, and allows the disambiguation of homonym identifiers residing in different namespaces....
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
In computer science, an array type is a data type that is meant to describe a collection of elements , each selected by one or more indices that can be computed at run time by the program. Such a collection is usually called an array variable, array value, or simply array...
In computer science, random access is the ability to access an element at an arbitrary position in a sequence in equal time, independent of sequence size. The position is arbitrary in the sense that it is unpredictable, thus the use of the term "random" in "random access"...
) but with the additional ability to automatically resize itself when inserting or removing an object.
The vector template can be instantiated with any type that fulfills the CopyConstructible and Assignable requirements:
expression
return type
requirement
t = u
T&
t is equivalent to u
T(t)
n/a
t is equivalent to T(t)
T(u)
n/a
u is equivalent to T(u)
&u
(const) T*
denotes the address of u
t.~T
n/a
n/a
Where T is the type used to instantiate the vector, t is a value of T and u is a value of (possibly const) T.
For a given vector all elements must belong to the same type. For instance, one cannot store data in the form of both char
Character (computing)
In computer and machine-based telecommunications terminology, a character is a unit of information that roughly corresponds to a grapheme, grapheme-like unit, or symbol, such as in an alphabet or syllabary in the written form of a natural language....
In computer science, an integer is a datum of integral data type, a data type which represents some finite subset of the mathematical integers. Integral data types may be of different sizes and may or may not be allowed to contain negative values....
within the same vector instance. Vectors provide a standard set of functions for accessing elements, adding elements to the end or anywhere, deleting elements and finding how many elements are stored.
Individual element access
Individual elements of a vector can be accessed using the operation shown in the table below. Following the standard convention for C and C++, the first element has index 0, and the last element has index size - 1.
In computer programming, undefined behavior is a feature of some programming languages—most famously C. In these languages, to simplify the specification and allow some flexibility in implementation, the specification leaves the results of certain operations specifically undefined.For...
if i >= v.size
v.front
T& or const T& to the first element
undefined behaviour if v.empty is true
v.back
T& or const T& to the last element
undefined behaviour if v.empty is true
Where v is an object of type (possibly const) vector and i represents the index.
In generic programming, a concept is a description of supported operations on a type, including syntax and semantics. In this way, concepts are related to abstract base classes but concepts do not require a subtype relationship.-Languages using:...
, which means it has begin, end, size, max_size, empty, and swap methods.
vector::vector(constructor) - Constructs the vector from variety of sources
vector::~vector(destructor) - Destructs the vector and the contained elements
vector::resize - Changes the number of stored elements
vector::swap - Swaps the contents with another vector
Vector iterators
In addition to the direct element access functions outlined above, the elements of a vector can be accessed through vectoriterator
Iterator
In computer programming, an iterator is an object that enables a programmer to traverse a container. Various types of iterators are often provided via a container's interface...
s.
Capacity and reallocation
A typical vector implementation consists, internally, of a pointer to a dynamically allocated array, and possibly data members holding the capacity and size of the vector. The size of the vector refers to the actual number of elements, while the capacity refers to the size of the internal array.
When new elements are inserted, if the new size of the vector becomes larger than its capacity, reallocation occurs. This typically causes the vector to allocate a new region of storage, move the previously held elements to the new region of storage, and free the old region.
A digital computer's memory, more specifically main memory, consists of many memory locations, each having a memory address, a number, analogous to a street address, at which computer programs store and retrieve, machine code or data. Most application programs do not directly read and write to...
of the elements change during this process, any references or iterators to elements in the vector become invalidated. Using an invalidated reference causes undefined behaviour
Undefined behaviour
In computer programming, undefined behavior is a feature of some programming languages—most famously C. In these languages, to simplify the specification and allow some flexibility in implementation, the specification leaves the results of certain operations specifically undefined.For...
. Example:
include
int main
{
std::vector v(1); // create a vector holding a single int with value 0.
int& first = *v.begin; // make a reference to the first element
v.insert(v.end, v.capacity, 0); // append more elements to the vector, forcing a reallocation
int i = first; // undefined behaviour; the reference has been invalidated
}
The reserve operation may be used to prevent unnecessary reallocations. After a call to reserve(n), the vector's capacity is guaranteed to be at least n. Example:
include
int main
{
std::vector v(1); // create a vector holding a single int with value 0.
v.reserve(10); // reserve space to prevent reallocation
int& first = *v.begin; // make a reference to the first element
v.insert(v.end, 5, 0); // append more elements to the vector
int i = first; // OK, no reallocation has occurred
}
The vector maintains a certain order of its elements, so that when a new element is inserted at the beginning or in the middle of the vector, subsequent elements are moved backwards in terms of their assignment operator or copy constructor
Copy constructor
A copy constructor is a special constructor in the C++ programming language creating a new object as a copy of an existing object. The first argument of such a constructor is a reference to an object of the same type as is being constructed , which might be followed by parameters of any type...
. Consequently, references and iterators to elements after the insertion point becomes invalidated. Example:
include
int main
{
std::vector v(2); // constructs a vector holding two ints
// make references to the two ints
int& first = v.front;
int& last = v.back;
v.insert(v.begin + 1, 1, 1); // insert a new int in the middle of the vector.
int i = first; // undefined behaviour if the previous insert caused reallocation
int j = last; // undefined behaviour per the C++ standard, §23.2.4.3/1
}
vector specialization
The Standard Library defines a specialization of the vector template for bool. The description of this specialization indicates that the implementation should pack the elements so that every bool only uses one bit of memory. This is widely considered a mistake. vector does not meet the requirements for a C++ Standard Library
C++ standard library
In C++, the C++ Standard Library is a collection of classes and functions, which are written in the core language and part of the C++ ISO Standard itself...
container. For instance, a container::reference must be a true lvalue of type T. This is not the case with vector::reference, which is a proxy class convertible to bool. Similarly, the vector::iterator does not yield a bool& when dereferenced
Dereference operator
The dereference operator or indirection operator, denoted by "*" , is a unary operator found in C-like languages that include pointer variables. It operates on a pointer variable, and returns an l-value equivalent to the value at the pointer address. This is called "dereferencing" the pointer...
. There is a general consensus among the C++ Standard Committee and the Library Working Group that vector should be deprecated and subsequently removed from the standard library, while the functionality will be reintroduced under a different name.
Usage
A C++ program that is to use vectors must #include . A vector is declared using:
std::vector instance;
where "T" is the data type the vector is to store, and "instance" is the variable
Variable (programming)
In computer programming, a variable is a symbolic name given to some known or unknown quantity or information, for the purpose of allowing the name to be used independently of the information it represents...
name of the vector. T can be any Assignable type, including user-defined types.
An alternative to storing objects of type T is to store objects of type T*. This is useful if T is not Assignable, or is expensive to copy.
In computer science, an array type is a data type that is meant to describe a collection of elements , each selected by one or more indices that can be computed at run time by the program. Such a collection is usually called an array variable, array value, or simply array...
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
Type system
A type system associates a type with each computed value. By examining the flow of these values, a type system attempts to ensure or prove that no type errors can occur...
.
A vector is similar to a dynamically allocated array but with the ability to resize itself, and without the need for manual deallocation of memory.
Because the elements of a vector are stored contiguously, the address of the first element of a vector can be passed to functions expecting an array (a pointer to the first element). The following example shows how a vector can be used with the C Standard Library
C standard library
The C Standard Library is the standard library for the programming language C, as specified in the ANSI C standard.. It was developed at the same time as the C POSIX library, which is basically a superset of it...
Printf format string refers to a control parameter used by a class of functions typically associated with some types of programming languages. The format string specifies a method for rendering an arbitrary number of varied data type parameter into a string...
:
include // memcpy
include
include // printf
int main
{
using namespace std;
const char arr[] = "1234567890";
// construct a vector with 11 zero-initialized chars.
vector vec(sizeof arr);
// copy 11 chars from arr into the vector
memcpy(&vec[0], arr, sizeof arr);
// prints "1234567890"
printf("%s", &vec[0]);
}
Note that such use of memcpy and printf is generally discouraged in favour of type safe alternatives from the C++ Standard Library
C++ standard library
In C++, the C++ Standard Library is a collection of classes and functions, which are written in the core language and part of the C++ ISO Standard itself...
.
Usage example
The following example demonstrates various techniques involving a vector and C++ Standard Library
C++ standard library
In C++, the C++ Standard Library is a collection of classes and functions, which are written in the core language and part of the C++ ISO Standard itself...
Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. Shuffling is often followed by a cut, to help ensure that the shuffler has not manipulated the outcome.-Shuffling techniques:...
Sorting is any process of arranging items in some sequence and/or in different sets, and accordingly, it has two common, yet distinct meanings:# ordering: arranging items of the same kind, class, nature, etc...
, finding the largest element, and erasing from a vector using the erase-remove idiom
Erase-remove idiom
The erase-remove idiom is a common C++ technique to eliminate elements that fulfill a certain criterion from a C++ Standard Library container.- Motivation :...
.
include
include
include // sort, max_element, random_shuffle, remove_if, lower_bound
include // greater, bind2nd
// used here for convenience, use judiciously in real programs.
using namespace std;
int main
{
int arr[4] = {1, 2, 3, 4};
// initialize a vector from an array
vector numbers(arr, arr+4);
// insert more numbers into the vector
numbers.push_back(5);
numbers.push_back(6);
numbers.push_back(7);
numbers.push_back(8);
// the vector currently holds {1, 2, 3, 4, 5, 6, 7, 8}
// randomly shuffle the elements
random_shuffle( numbers.begin, numbers.end );
// locate the largest element, O(n)
vector::const_iterator largest =
max_element( numbers.begin, numbers.end );
cout << "The largest number is " << *largest << "\n";
cout << "It is located at index " << largest - numbers.begin << "\n";
// sort the elements
sort( numbers.begin, numbers.end );
// find the position of the number 5 in the vector, O(log n)
vector::const_iterator five =
lower_bound( numbers.begin, numbers.end, 5 );
cout << "The number 5 is located at index " << five - numbers.begin << "\n";
// erase all the elements greater than 4
numbers.erase( remove_if(numbers.begin, numbers.end,
bind2nd(greater, 4) ), numbers.end );
// print all the remaining numbers
for(vector::const_iterator it = numbers.begin; it != numbers.end; ++it)
{
cout << *it << " ";
}
return 0;
}
The output will be the following:
The largest number is 8
It is located at index 6 (implementation-dependent)
The number 5 is located at index 4
1 2 3 4 Example of 2 dimensional dynamic vector array, and accessing and modifying it:
typedef std::vector< std::vector > pxMP;
void function
{
int sizeX, sizeY; // size can be set on-the-fly.
pxMP pxMap(sizeX, std::vector(sizeY)); // X/Y array of pixels 0,1.
pxMap[0][5] = 1; /* accessing it */
// delete left and right columns:
pxMap.pop_back;
pxMap.erase(pxMap.begin);
// delete top and bottom rows of all columns, first make some tools:
std::vector< std::vector >::iterator iterlvl2; // iterator level 2 dimension.
std::vector< int >::iterator iterlvl1; // iterator level 1 dimension
// lets' go deeper. We must go deeper.
for (iterlvl2=pxMap.begin;iterlvl2 != pxMap.end;iterlvl2++)
{
iterlvl1 = (*iterlvl2).begin; // demo purpose only.
(*iterlvl2).pop_back;
(*iterlvl2).erase((*iterlvl2).begin); // where are we?
sizeY = (*iterlvl2).size; // set new sizeY while on this level, once we return to the higher level we cannot retrieve...
}
/* that was cool */
}
Example of 1 dimensional dynamic vector array, and sorting and removing all duplicate entries:
include
include
include // for generic algorithms: sort / unique / erase
// sort all the elements of the vector
sort(v_str.begin, v_str.end);
// the result is the sorting of the elements: {"aa", "aa", "bb", "dd", "xx", "xx", "zz"}
// remove duplicate entries
v_str.erase( unique(v_str.begin, v_str.end ), v_str.end );
// the result is sorted and unique elements: {"aa","bb","dd","xx","zz"}
return void;
}
Vector visualization
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.
In computer science, a dynamic array, growable array, resizable array, dynamic table, or array list is a random access, variable-size list data structure that allows elements to be added or removed...
In computer science, locality of reference, also known as the principle of locality, is the phenomenon of the same value or related storage locations being frequently accessed. There are two basic types of reference locality. Temporal locality refers to the reuse of specific data and/or resources...
and data cache utilization.
The vector data structure is able to quickly and easily allocate the necessary memory needed for specific data storage. This is particularly useful for storing data in lists whose length may not be known prior to setting up the list but where removal (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.
In computer science, a double-ended queue is an abstract data structure that implements a queue for which elements can only be added to or removed from the front or back...
s and lists, vectors allow the user to denote an initial capacity for the container.
In computer science, random access is the ability to access an element at an arbitrary position in a sequence in equal time, independent of sequence size. The position is arbitrary in the sense that it is unpredictable, thus the use of the term "random" in "random access"...
; that is, an element of a vector may be referenced in the same manner as elements of arrays (by array indices). Linked-lists and sets, on the other hand, do not support random access or pointer arithmetic.
Erasing elements from a vector or even clearing the vector entirely does not necessarily free any of the memory associated with that element. This is because the maximum size of a vector since its creation is a good estimate of the future size of the vector.
Vectors are 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.
C++ vectors do not support in-place reallocation of memory, by design; i.e., upon reallocation of a vector, the memory it held will always be copied to a new block of memory using its elements' copy constructor, and then released. This is inefficient for cases where the vector holds plain old data and additional contiguous space beyond the held block of memory is available for allocation.
.gif)
