Node:Vector, Next:, Previous:Sequences, Up:Sequences


Vector

vector Sequence
vector is a kind of sequence (See Sequences.) that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency. See Reversible Container. 

template  class Allocator = allocator>
class vector {
public:

// typedefs:
    typedef iterator;
    typedef const_iterator;
    typedef Allocator::pointer pointer;
    typedef Allocator::reference reference;
    typedef Allocator::const_reference const_reference;
    typedef size_type;
    typedef difference_type;
    typedef T value_type;
    typedef reverse_iterator;
    typedef const_reverse_iterator;

// allocation/deallocation:
    vector();
    vector(size_type n, const T& value = T());
    vector(const vector& x);
    template 
    vector(InputIterator first, InputIterator last);
    ~vector();
    vector& operator=(const vector& x);
    void reserve(size_type n);
    void swap(vector& x);

// accessors:
    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
    reverse_iterator rbegin();
    const_reverse_iterator rbegin();
    reverse_iterator rend();
    const_reverse_iterator rend();
    size_type size() const;
    size_type max_size() const;
    size_type capacity() const;
    bool empty() const;
    reference operator[](size_type n);
    const_reference operator[](size_type n) const;
    reference front();
    const_reference front() const;
    reference back();
    const_reference back() const;

// insert/erase:
    void push_back(const T& x);
    iterator insert(iterator position, const T& x = T());
    void insert(iterator position, size_type n, const T& x);
    template 
    void insert(iterator position, InputIterator first, InputIterator last);
    void pop_back();
    void erase(iterator position);
    void erase(iterator first, iterator last);
};

template 
bool operator==(const vector& x, const vector& y);
template 
bool operator<(const vector& x, const vector& y);

iterator Typedef on vector
iterator is a random access iterator referring to T. The exact type is implementation dependent and determined by Allocator.

const_iterator Typedef on vector
const_iterator is a constant random access iterator referring to const T. The exact type is implementation dependent and determined by Allocator. It is guaranteed that there is a constructor for const_iterator out of iterator.

size_type Typedef on vector
size_type is an unsigned integral type. The exact type is implementation dependent and determined by Allocator.

difference_type Typedef on vector
difference_type is a signed integral type. The exact type is implementation dependent and determined by Allocator.

vector (InputIterator first, InputIterator last) Constructor on vector
The constructor template <class InputIterator> vector(InputIterator first, InputIterator last) makes only N calls to the copy constructor of T (where N is the distance between first and last) and no reallocations if iterators first and last are of forward, bidirectional, or random access categories. It does at most 2N calls to the copy constructor of T and \log N reallocations if they are just input iterators, since it is impossible to determine the distance between first and last and then do copying.

capacity () Method on vector
reserve () Method on vector
The member function capacity returns the size of the allocated storage in the vector. The member function reserve is a directive that informs vector of a planned change in size, so that it can manage the storage allocation accordingly. It does not change the size of the sequence and takes at most linear time in the size of the sequence. Reallocation happens at this point if and only if the current capacity is less than the argument of reserve. After reserve, capacity is greater or equal to the argument of reserve if reallocation happens; and equal to the previous value of capacity otherwise. Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. It is guaranteed that no reallocation takes place during the insertions that happen after reserve takes place till the time when the size of the vector reaches the size specified by reserve.

insert (iterator position, const T& x = T()); Method on vector
insert (iterator position, size_type n, const T& x); Method on vector
insert (iterator position, InputIterator first, InputIterator last); Method on vector
insert causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid. Inserting a single element into a vector is linear in the distance from the insertion point to the end of the vector. The amortized complexity over the lifetime of a vector of inserting a single element at its end is constant. Insertion of multiple elements into a vector with a single call of the insert member function is linear in the sum of the number of elements plus the distance to the end of the vector. In other words, it is much faster to insert many elements into the middle of a vector at once than to do the insertion one at a time. The insert template member function preallocates enough storage for the insertion if the iterators first and last are of forward, bidirectional or random access category. Otherwise, it does insert elements one by one and should not be used for inserting into the middle of vectors.

erase (iterator position); Method on vector
erase (iterator first, iterator last); Method on vector
erase invalidates all the iterators and references after the point of the erase. The destructor of T is called the number of times equal to the number of the elements erased, but the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements.

vector Sequence
To optimize space allocation, a specialization for bool is provided: 

class vector {
public:

// bit reference:
    class reference {
    public:
        ~reference();
        operator bool() const;
        reference& operator=(const bool x);
        void flip(); // flips the bit
    };

// typedefs:
    typedef bool const_reference;
    typedef iterator;
    typedef const_iterator;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef bool value_type;
    typedef reverse_iterator;
    typedef const_reverse_iterator;

// allocation/deallocation:
    vector();
    vector(size_type n, const bool& value = bool());
    vector(const vector& x);
    template 
    vector(InputIterator first, InputIterator last);
    ~vector();
    vector& operator=(const vector& x);
    void reserve(size_type n);
    void swap(vector& x);

// accessors:
    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
    reverse_iterator rbegin();
    const_reverse_iterator rbegin();
    reverse_iterator rend();
    const_reverse_iterator rend();
    size_type size() const;
    size_type max_size() const;
    size_type capacity() const;
    bool empty() const;
    reference operator[](size_type n);
    const_reference operator[](size_type n) const;
    reference front();
    const_reference front() const;
    reference back();
    const_reference back() const;

// insert/erase:
    void push_back(const bool& x);
    iterator insert(iterator position, const bool& x = bool());
    void insert (iterator position, size_type n, const bool& x);
    template 
    void insert (iterator position, InputIterator first, InputIterator last);
    void pop_back();
    void erase(iterator position);
    void erase(iterator first, iterator last);
};

void swap(vector::reference x,
          vector::reference y);

bool operator==(const vector& x,
                const vector& y);

bool operator<(const vector& x,
               const vector& y);

reference Typedef on vector<bool>
reference is a class that simulates the behavior of references of a single bit in vector<bool>.

Every implementation is expected to provide specializations of vector<bool> for all supported memory models.

At present, it is not possible to templatize a specialization. That is, we cannot write: 
            template