# Week 1: Array; Sorting; C++ Specifics

[ToC]

## Declare large arrays globally instead of locally

- This is **bad**:

  
    void some_func() {
	    ...
	    int b[200000]; // array local to `some_func`, may fail allocation due to large size
	    ...
	}

	int main() {
	    ...
	    int a[100000]; // array local to `main`, may fail allocation due to large size
	    ...
	    some_func();
	    ...
	}

- This is **good**:

	int a[100000], b[200000]; // global now; allocation won't fail
	
    void some_func() {
        ...
    }
	
    int main() {
        ...
        some_func();
        ...
    }

- The reason is not important for us, but *if you're curious*: A local data uses the stack allocation strategy which allows for a limited amount of data to be allocated. On the other hand, a global data is allocated statically on a separate data segment where the only limit is the available size of the RAM.

## `vector`: Dynamic array in C++ STL

- An array that can grow/shrink at the back efficiently at runtime.
- Will be your most often used data sructure.

### How to use

- Declare:

    // type of the contained element goes inside `<` and `>`
    vector<int> a;
    vector<double> b;
    vector<string> c;

- Declare with pre-allocated size and fill-value:

    vector<int> a1(1000); // 1000 ints, all set to 0 (the default int value)
    vector<string> b1(1000); // 1000 strings, all set to "" (the default string value)
    vector<int> a2(1000, -1); // 1000 ints, all set to -1
    vector<string> b2(1000, "xyz"); // 1000 strings, all set to "xyz"

- Query size/length in $O(1)$ time:

    a.size();
    a.empty(); // returns `a.size() == 0`

- Index-based access to elements in $O(1)$ time, like in arrays:

    cout << "first element: " << a[0] << "\n";
    cout << "last element: " << a[a.size() - 1] << "\n"; 
    
    ...
    
    cout << "all elements: ";
    for (int i = 0; i < a.size(); i++) {
        cout << a[i] << " ";
    }
    cout << "\n";

    a.front(); // convenience function to access first element without index
    a.back(); // convenience function to access last element without index

- **[Most important]** Add/remove elements **at the back** in $O(1)+$ (i.e. amortized constant) time:

    vector<int> a;
    for (int i = 0; i < 10; i++) {
        a.push_back(i + 1);
        cout << "added: " << a.back() << "\n";
    }
    for (int i = 0; i < 10; i++) {
        cout << "removing: " << a.back() << "\n";
        a.pop_back();
    }

### When and why to use

- You don't know the number of elements beforehand

## `deque`: Dynamic array, but for both ends

- Exactly like `vector`, but can also add/remove **at the front**:

    deque<int> a;
    for (int i = 0; i < 10; i++) {
        if (i % 2 == 0) {
            a.push_front(i);
        } else {
            a.push_back(i);
        }
    }
    for (int i = 0; i < 10; i++) {
        cout << a[i] << " ";
    }
    cout << "\n";