# Chapter 17 - Notes

## Static and Dynamic Arrays

### Static Arrays&#x20;

* Size is required at compile time
* Lifetime is scoped&#x20;
* Cannot be deleted/resized&#x20;

### Dynamic Arrays

* Size can be deferred to runtime&#x20;
* Dynamically allocated, therefore lifetime is not scoped&#x20;
* Created with the `new` keyword&#x20;
* Can be "resized" by deleting and creating a new array&#x20;

## STL Dynamic Arrays&#x20;

* `std::vector` or `std::deque`
* `std::list` is not a dynamic array, it is akin to a linked list&#x20;

## Vector&#x20;

### Characteristics&#x20;

* 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&#x20;

### Operations&#x20;

#### Instantiation&#x20;

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

#### Iterators&#x20;

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

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

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

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

#### Initialisation&#x20;

```cpp
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&#x20;

* Insertion at the end is done with `.push_back()`

```cpp
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&#x20;

* 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.&#x20;

```cpp
// 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.&#x20;
* 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&#x20;

* Elements can be accessed with array semantics using the subscript operator (`[]`) or using the `.at()` member function, or using iterators.&#x20;

```cpp
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.&#x20;
* On the flipside, `.at()` performs a runtime check against the `size()` of the container and throws an exception if you cross the boundaries.&#x20;

#### Accessing using pointer semantics&#x20;

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

```cpp
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.&#x20;

#### Removing elements  from the back&#x20;

* Removal of elements from the back of a vector is done with `.pop_back()`, which takes constant time.&#x20;

```cpp
numbers.pop_back();
```

## Size and Capacity&#x20;

* 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.&#x20;

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.&#x20;

## Deque&#x20;

* `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.&#x20;

### Operations&#x20;

#### Instantiation&#x20;

```cpp
std::deque<int> intDeque;
```

#### Insertion and Deletion&#x20;

* 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&#x20;

* Access can be done with array semantics with the subscript operator (`[]`) or the `.at()` member variable&#x20;
* Access can be done with pointer-like semantics with iterators.&#x20;
