Chapter 17 - Notes

Static and Dynamic Arrays

Static Arrays

• Size is required at compile time

• Lifetime is scoped

• Cannot be deleted/resized

Dynamic Arrays

• Size can be deferred to runtime

• Dynamically allocated, therefore lifetime is not scoped

• Created with the new keyword

• Can be "resized" by deleting and creating a new array

STL Dynamic Arrays

• std::vector or std::deque

• std::list is not a dynamic array, it is akin to a linked list

Vector

Characteristics

• Addition and removal of elements to the end of the array in constant time

• The time required for the insertion or removal of elements at the middle is directly proportional to the number of elements behind the element being removed

• Memory usage is automatically managed

Operations

Instantiation

std::vector<int> intVector;  // Vector of integers 
std::vector<float> floatVector;  // Vector of floats 
std::vector<Human> humanVector;  // Vector of Humans 

Iterators

• The type for iterators for std::vectors can be obtained simply by appending ::iterator to the vector type:

std::vector<int>::iterator intVectorIt; 

• If you need a read-only iterator, use const_iterator instead:

std::vector<int>::const_iterator intVectorConstIt;

Initialisation

int main() {
    // vector of integers
    std::vector<int> integers;
    // vector initialized using C++11 list initialization
    std::vector<int> initVector{ 202, 2017, -1 };

    // Instantiate a vector with 10 elements (it can still grow)
    std::vector<int> tenElements (10);

    // Instantiate a vector with 10 elements, each initialized to 90
    std::vector<int> tenElemInit (10, 90);

    // Initialize vector to the contents of another
    std::vector<int> copyVector (tenElemInit);

    // Vector initialized to 5 elements from another using iterators
    std::vector<int> partialCopy (tenElements.cbegin(), tenElements.cbegin() + 5);
}

Inserting at the end

• Insertion at the end is done with .push_back()

vector <int> integers; // declare a vector of type int

// Insert sample integers into the vector:
integers.push_back (50);
integers.push_back (1);

Insertion to the middle

• Insertion to the middle is done with .insert()

• You use an iterator (often returned by .begin() or .end()) to tell the .insert() function the position you want the new elements to be placed.

// insert an element at the beginning
integers.insert(insert.begin(), 25);

// insert 2 elements of value 45 at the end
integers.insert(integers.end(), 2, 45);

// Another vector containing 2 elements of value 30
vector<int> another(2, 30);
// Insert two elements from another container in position [1]
integers.insert(integers.begin() + 1, another.begin(), another.end());

• Although .insert() is a versatile function, using .push_back() should be preferred because inserting to anywhere but the back of a vector is inefficient.

• If you find yourself calling .insert() often on an std::vector, perhaps it's a sign that you should be using a different container type.

Accessing using array semantics

• Elements can be accessed with array semantics using the subscript operator ([]) or using the .at() member function, or using iterators.

elements[3] = 2011;  // Set the 4th element 
auto value = elements.at(3);   // Access the 3rd element

• Using the subscript operator ([]) with vectors comes with the same dangers as with an array - you should not cross the boundaries of a container.

• On the flipside, .at() performs a runtime check against the size() of the container and throws an exception if you cross the boundaries.

Accessing using pointer semantics

• Elements can be accessed with pointer-like semantics by using iterators

vector<int> numbers { 50, 1, 987, 1001 };

vector<int>::const_iterator element = numbers.cbegin();

while (element != numbers.end()) {
    // de-reference like a pointer
    std::cout << *element << std::endl;  
    // move to next element
    element++;
}

• Iterators behave more or less like pointers; you can dereference an iterator to get the value stored, increment it to get the next element, and perform pointer arithmetic to get the relative distance from the start.

Removing elements from the back

• Removal of elements from the back of a vector is done with .pop_back(), which takes constant time.

numbers.pop_back();

Size and Capacity

• The size of a vector is the number of elements currently stored in the vector.

• The capacity of a vector is the number of elements that can be stored in the vector before it has to resize.

Resizing is an expensive operation; if you (roughly) know the number of elements your vector would store, you can use the .reserve() member function to resize the vector ahead of time to reduce the number of reallocations later.

Deque

• std::deque (pronounced as deck) is similar to std::vector except that it allows insertion and removal to the front of the array in addition to the back.

Operations

Instantiation

std::deque<int> intDeque;

Insertion and Deletion

• Insertion and deletion is similar to std::vector via .push_back() and .pop_back()

• Also supports insertion and deletion to the front with .push_front() and .pop_front()

Access

• Access can be done with array semantics with the subscript operator ([]) or the .at() member variable

• Access can be done with pointer-like semantics with iterators.