Implementing Vector

CSCI 362: Data Structures

Prof. William Killian

Vector

vector overcomes the limitations of array

• Dynamically resizable
• Know their length and capacity
• Elements still stored contiguously -- $O(1)$ element access
• Easily copied

std::vector API

Defined in header <vector>

namespace std {
  template <
    typename T,                            // value type to store
    typename Allocator = std::allocator<T> // how to allocate data
  > class vector;
}

std::vector Special Member Datatypes

Name	Description
T	template parameter for value type to store
value_type	alias to T
size_type	unsigned integer type (usually std::size_t)
difference_type	signed integer type (usually std::ptrdiff_t)
reference	alias to value_type&
const_reference	alias to value_type const&
pointer	usually just value_type*
const_pointer	usually just value_type const*
iterator	aliased to value_type*
const_iterator	aliased to value_type const*
reverse_iterator	std::reverse_iterator<iterator>
const_reverse_iterator	std::reverse_iterator<const_iterator>

std::vector Contructors

vector ();
vector (size_type n);
vector (size_type n, T const& value);

template <typename InputIterator>
vector (InputIterator first, InputIterator last);

vector (std::initializer_list<T>);

std::vector Access Operations

reference back ();
      reference front ();
      reference operator[] (size_type i);  
      reference at (size_type i);
      pointer   data ()                         noexcept;

std::vector Access Operations (const versions)

const_reference back ()                  const;
const_reference front ()                 const;
const_reference operator[] (size_type i) const;  
const_reference at (size_type i)         const;
const_pointer   data ()                  const noexcept;

reference back ();

• return the value of the item at the rear (or back) of the vector
• Precondition: the vector must contain at least one element

 

const_reference back() const;

• const version of back()

reference operator[] (size_type i);

• Allows the vector element at index $i$ to be retrieved or modified
• Precondition: $0 \le i < n \mid n=$ size of the vector
• Postcondition: If the operator appears on the left side of an assignment statement, the expression on the right side modifies the element referenced by the index

 

reference at (size_type i);

• Behaves exactly like operator[] but does run-time bounds checking
• Throws an exception if the precondition isn't met

std::vector Capacity Operations

bool      empty ()                     const;
size_type size ()                      const;
size_type capacity ()                  const;
size_type max_size ()                  const;
void      shrink_to_fit ();
void      reserve (size_type newcap);

bool empty() const;

• returns true IFF the vector's size is zero

 

size_type size () const

• returns the current size of the vector

 

size_type capacity() const;

• returns the number of elements that the container has currently allocated space for.

void shrink_to_fit();

• Requests the removal of unused capacity by reducing capacity() to size()
• Postcondition: if reallocation occurs, all iterators and all references are invalidated

 

void reserve(size_type newcap);

• Increase the capacity of the vector to a value that is $\ge newcap$
• If $newcap$ > capacity() then new storage is allocated; otherwise, the method does nothing
• Postcondition: capacity() $\ge newcap$, size is unchanged

std::vector Iterator Operations

iterator               begin ()  noexcept;
iterator               end ()    noexcept;
reverse_iterator       rbegin () noexcept;
reverse_iterator       rend ()   noexcept;
const_iterator         begin ()  const noexcept; // and cbegin()
const_iterator         end ()    const noexcept; // and cend()
const_reverse_iterator rbegin () const noexcept; // and crbegin()
const_reverse_iterator rend ()   const noexcept; // and crend()

std::vector Modifying Operations

void     clear();

void     pop_back ();
iterator erase (...);  // 2 versions

iterator insert (...); // 5 versions
void     push_back (const_reference value); // and "move" variant

template <typename ... Args>
iterator emplace (const_iterator pos, Args&& ... value);

template <typename ... Args>
void     emplace_back (Args&& ... value);

void     resize(...);  // 2 versions

void push_back (const_reference value);

• Adds a value at the rear of the vector
• Postcondition: The vector has a new element at the rear; size is increased by 1

 

void pop_back ();

• Removes a value from the rear of the vector
• Precondition: The vector is not empty
• Postcondition: The vector's last element has been removed or is empty; size decreases by 1

iterator insert (iterator pos, const_reference value);

• inserts $value$ before $pos$ and returns an iterator pointing to the position of the new value in the vector
• NOTE: this operation may invalidate any existing iterators if the capacity needs increased
• Postcondition: The vector has a new element; size is increased by 1

 

iterator erase (iterator pos);

• Erase the element pointed to by $pos$
• NOTE: all iterators beyond the elements erased are invalidated
• Precondition: The vector is not empty
• Postcondition: The vector has one less element; size is decreased by 1

iterator erase (const_iterator first, const_iterator last);

• Erases the range of all elements in [first, last)
• NOTE: all iterators beyond the elements erased are invalidated
• Precondition: The vector is not empty
• Postcondition: Size decreases by std::distance(first, last); the same number of elements are removed

 

void resize(size_type n);

• Modify the size of the vector. If the size is increased, the default value T() is filled for the increase in elements at the end. If the size is decreased, the original values at the front are retained.
• Postcondition: The vector has size $n$

Implementation Details

---

Most of which will be on the board :)

template <typename T>
class Vector {
// private members:

size_t m_size;
    size_t m_capacity;
    T*     m_array;
};

Constructors

// Default Constructor
Vector()

// Size Constructor
Vector(size_t pSize, const T& value = T())

// Range Constructor *
Vector(Iterator first, Iterator last)

// Copy Constructor **
Vector(const Vector& v)

Other Special Member Functions

// Destructor
~Vector

• should relinquish all memory allocated / in use by our vector

// Copy Assign *
Vector& operator=(const Vector& v)

• assigns 'v' to this object
• NOTE: must check for self assignment
• NOTE: must return reference to self

// Indexing Operator *
T& operator[](size_t index)

Capacity Operations

size_t size()     const;
bool   empty()    const;
size_t capacity() const;

Iterator Operations

// refers to the first element of the vector *
iterator       begin();
const_iterator begin() const;

// refers to one-past-the-last element of the vector *
iterator       end();
const_iterator end() const;

Modifying Operations

// ensures that capacity() >= space *
void reserve (size_t space);

// ensures size() == newSize *
// - if newSize < size(), remove elements from end
// - if newSize > size(), insert copies of 'value' at end
void resize (size_t newSize, const T& value = T());

// adds a single element to the end *
void push_back(const T& item);

// removes a single element from the end *
void pop_back();

Iterator Modifying Operations

// inserts "item" before "pos" in the vector
// NOTE: must shift all elements from [pos, end()) right *
iterator insert (iterator pos, const T& item);

// removes element referred to by "pos" from the vector
// returns iterator to the element that comes after
// NOTE: must shift all elements from [pos + 1, end()) left **
iterator erase  (iterator pos);

Homework

Implement the following Vector functions:

template <typename T>
class Vector {
public:
    // Copy Constructor
    Vector (const Vector& v);

    // Range Constructor
    Vector(const_iterator first, const_iterator last);

    // Resize Operation
    void resize (size_t newSize, const T& value = T());

    // Erase
    iterator erase  (iterator pos);
};

Include your name; separate each function with whitespace; include comments where appropriate