ADTvector and the STL vector Container Class
Actually you will not normally find "vector" as one of the "usual" ADTs in traditional textbooks on data structures. The vector just kind of "grew up" as a "better array". On the other hand, there is no reason why we can't consider it a bona fide ADT, with the operations conveniently provided by the Standard Template Library of C++ (in our case, at least).
| vector Operations | |
|---|---|
| Generic (ADT) | Specific (STL) |
| Construct a vector |
vector<T> v; vector<T> v(num); vector<T> v(num, someValueOfTypeT); vector<T> v(otherVector); vector<T> v(inputIter1, inputIter2); |
| Test for emptiness | empty() |
| Add one or more values | |
| Add value to back | push_back(val) |
| Insert values |
insert(iter, val) insert(iter, num, val) insert(iter, startIter, endIter) |
| Assign values |
assign(startIter, endIter) assign(num, val) |
| Remove one or more values | |
| Remove all values | clear() |
| Remove value pointed to | erase(iter) |
| Remove a range of values | erase(startIter, endIter) |
| Remove value from back | pop_back() |
| Retrieve a value (without removing it) | |
| Get value at front | front() |
| Get value at back | back() |
| Get value at index location |
at(index) operator[ ] (i.e., v[index]) |
| Retrieve size or capacity | |
| Get current size | size() |
| Get maximum size | max_size() |
| Get current capacity | capacity() |
| Miscellaneous operations affecting the entire container | |
| Change size |
resize(num) resize(num, val) |
| Reserve a certain capacity | reserve(num) |
| Exchange contents of self with another vector | swap(otherVector) |
The vector<T>::iterator and vector<T>::reverse_iterator iterators are random access iterators, the most powerful kind of STL iterator and the same kind of iterator provided by the deque container class. The member function begin() returns an iterator pointing at the first element of the vector, while end() is a member function returning an iterator pointing at the position "one past the end" of the vector. Analogously, rbegin() and rend() return iterators pointing at the last and "one before the first" positions, respectively.
The vector class has an underlying architecture which makes vectors ideal for storing components whose order is important and for situations in which fast numeric indexing for component access is critical. Inserting elements anywhere except at the back end of a vector is slow, so they should not be used where this kind of operation is prevalent. In such cases consider using a list or a deque instead.
The vector class is one of the three "sequential" container classes in the STL (the deque and the list are the other two). Usually, if you're wondering about using a vector, the choice will be between using a vector or using a deque, since they have so much in common, although there is still occasionally even a place for "old-fashioned" arrays. Element access tends to be a bit faster in vectors, though both vectors and deques offer constant-time access to elements (from a big-Oh perspective). If there are to be many insertions and deletions at the ends, and particularly at the front, the deque would be a better choice. In general, though, when an array-like object which can grow and shrink dynamically is needed, the vector tends to be the container of choice.