Vector

Vector Definition

• A vector is mostly a data structure as it is usually language specific.

• A vector can be sometimes be treated as an ADT, when focusing on the data organization and behaviors only. Implementations are ignored.

• Vector: A sequential ADT, similar to list ADT with some specific behaviors

• Behaviors

  • access by index

  • insert remove by index

  • add remove at the end

  • check size/empty

C++ std::vector

• A C++ implementation of the Vector ADT

• An STL container

• #include <vector>

• vector is a class template, not a type! vector<int> is a class type

• Based on a dynamic array internally

  • fast access by indexing

  • slow erase/insert in the middle

  • may re-allocate memory when out of space (capacity)

    • create a larger array

    • duplicate/move all elements from existing array

    • delete the existing array

  • resize

• Variable length allowed

• Out-of-boundary check with .at(n) method

• automatic memory re-allocation

• Methods

  • Constructors

    • default: empty vector

    • (n): vector of size n, default values

    • (n, v): vector of size n, fill values as v

    • (aVectorOfSameType): copy another vector, must be same base type

    • {item1, item2, ...}: fill items from index 0

  • Operator =

    • v1 = {1, 2, 3}: initializer_list assignment

    • v1 = v2: copy assignment

  • at()

    • can assign value like v.at(0) = 10;

    • with boundary check. Triggers out_of_boundary exception

    • preferred over [] syntax

  • clear() clear the content

  • empty() check empty

  • size()

  • push_back()

    • push the value as the last element

    • does not return value

  • pop_back()

    • removes the last element

    • does not return value! Be careful! Many pop methods in other languages returns a value.

  • back()

    • returns the value of the last element

  • resize()

    • may or may not re-allocate memory

    • does not erase data if downsized

  • find() find an element by value, returns an iterator

  • insert() requires the use of iterators

  • erase() requires the use of iterators

Initialization

When the braces are used, the initialization will use the values as items. Must use parentheses when triggering other constructors.

• vector<int> v{1, 2, 3, 4, 5} size 5 vector with values

• vector<int> v = {1, 2, 3, 4, 5} size 5 vector with values, preferred for sequence initialization

• vector<int> v(5) size 5 vector with 0s, v{5} will make a size 1 vector

• vector<int> v(5, 1) size 5 vector with 1s, warning: v{5, 1} will make a size 2 vector instead

• vector<int> v1(v) make a copy of v

C++ Iterator Type (Extended reading)

In C++, an iterator is an object that enables traversal through the elements of a container, such as a vector, list, or map, without exposing the underlying implementation of the container. Iterators provide a consistent interface to access and modify the elements of a container, regardless of the specific container type. They allow for efficient manipulation of container elements by providing methods for moving between elements, accessing the value at the current position, and modifying the value at the current position. Iterators are an essential tool for generic programming in C++ and allow for efficient, type-independent algorithms to be written for a variety of container types.

• A derived type of STL containers such as vector, list, map, etc.

  • e.g. vector<int>::iterator is used to iterate through a vector of int.

  • May use auto to simplify the type declaration: auto it = v.begin();

• Vector methods using iterator

  • begin() returns an iterator pointing to the first element

  • end() returns an iterator pointing to the element after the last element

  • erase(iterator) removes the element at the iterator position and returns the iterator pointing to the next element

  • insert(iterator, value) inserts the value before the iterator position and returns the iterator pointing to the inserted element

• Functions using iterators

  • find(begin, end, value) returns an iterator pointing to the first element that matches the value in the range defined by a beginning iterator and an ending iterator. It return the end iterator if not found.

• Example:

  vector<int> v = {1, 2, 3, 4, 5};
  vector<int>::iterator it = find(v.begin(), v.end(), 3);
  it = v.erase(it);  // remove the element at the iterator position, returns
                    // the iterator pointing to the next element
  

Passing vector around

• As parameter

  • by-value (object duplication): void func1(vector<int> vec);

  • read-only reference: void func1(const vector<int> &vec);

  • by-reference (allow modifications of the actual parameter): void func1(vector<int> &vec);

  • example:

    // Assume that the Patient class is ready for use
    // read data from a csv file and create the vector of Patient objects
    loadData(vector<Patient> &patients, string filename);
    
    class TextMenuApp {
      vector<Patient> &patients;  // takes a reference to avoid copy overhead
     public:
      TextMenuApp(vector<Patient> &patients): patients(patients) {}
      void run();
      // ...
    };
    
    int main() {
      // Only one vector is created in the scope of the main function
      // Its reference is passed around
      vector<Patient> patients;
      loadData(patients, "patients.csv");
      TextMenuApp app(patients);
      app.run();
      return EXIT_SUCCESS;
    }
    

• As returned value

  • return by value (object not necessary duplicated, some optimization will happen)

  • see the filter example

Algorithms

• Works with all algorithms on arrays

  • change arr[i] to vec.at(i)

  • no longer need to pass a separate size variable

• Particularly good for out-of-place algorithms with variable length output

  • filter type of algorithm, i.e. find all positive value in a vector:

    vector<int> positiveOnly(const vector<int> &v) {
      vector<int> result;
      for (int i = 0; i < v.size(); ++i)
        if (v.at(i) > 0)
          result.push_back(v.at(i));
      return result;
    }
    

Pitfalls

• use [] rather than at()

• int a = v.pop_back(); should be int a = v.back(); v.pop_back()

• cout << v.length(); Wrong! There is no length() method

• if (v.size() == 0) this works but better use if (v.empty())

Extended Readings

• Use .emplace_back() with object vector

• Use for each loop with vectors