1. Vectors

• template <typename T>
• Change int to T
• Make functions template functions parameterized by T ```cpp template std::ostream& operator<<(std::ostream& os, const vec& ia);

Vec CreateIntVec() { Vec tmp; // need to explicitly specify the type // ... }

```cpp
void push_back(int x) {
	if (sz == cap) {
		int* a2 = new int[cap * 2];
		cap *= 2;
		std::copy(a, a+sz, a2);   // uses copy assignment
		delete[] a;
		a = a2;
	}
	a[sz++] = x;
}

int main() {
    Vec<MyString> v;    // (1)
    v.push_back("abc"); // (2)
    v.push_back("def"); // (3)
    MyString s{"xyz"};  // (4)
    v.push_back(s);     // (5)
}

1. Constructs v on the stack {size_t size, size_t cap, MyString a[1]}
   • sz = 0; cap = 1;
   • a is an allocated 1-element array
     • Calls MyString()
       • Makes a default MyString object on the heap, with
2. const T& requires a promoted temporary object
   • Temp (rvalue) MyString("abc") object constructed on stack
     • len = 3
     • data = "abc\0"
   • Temp comes into push_back() as const T& x (reference)
     • Must have const, else won’t accept rvalue
   • a[sz++] = x
     • Copy assignment
   • x destroyed after push_back() return, and temp
3. push_back("def")
   1. Same temp creation
   2. Allocation needed! (two levels)
      1. new MyString[2] allocated on heap
         • Both members are default constructed MyString()
      2. std::copy()
         • Copy assignment
           • delete old data
           • Data pointer updated
      3. delete[] a
         • delete[] all string allocations
   3. x (and its members) gets copy assigned to its a[1], and destroyed
4. MyString s{"xyz"}
   • s created on stack
     • "xyz\0" on heap
5. v.push_back(s)
   1. s passed by reference
   2. Need to reallocate again
      • Every MyString gets default constructed
      • Copy assign the MyStrings over
      • The vector entry v.a[3].data has a different copy with s.data - Last slot left "empty", but a MyString` object

STL containers hold its own copy of the data (by value)

[!info] This is NOT how vector works. Default construction is wasteful std::vector will not initialize the memory (no default constructor new, just malloc())

• But how would a[sz++] = x work?
  • This is an assignment. The LHS object must be constructed
• Solution: Placement new

  Placement new

char s_buf[sizeof(MyString)];
MyString* sp = new (s_buf) MyString{"hello"};

Casting decouples memory allocation and constructor call!

• No memory allocation
• Only calls constructor Can’t directly invoke delete, need to manually invoke the destructor

  sp->~MyString();
  

Strong Exception Guarantee

For push_back(Int), exception can only happen in new. std::copy() of integers is trivial

• Need to guarantee that IntArray won’t be changed

For push_back(MyString),

1. If new throws, nothing created
2. If copy() throws,
   • operator=(MyString) uses new, may throw
3. Assignment a[sz++] = x may throw

void push_back(const T& x) {
    if (sz == cap) {
        T* a2 = new T[cap * 2];       // no issue
        try {
            std::copy(a, a+sz, a2);
        } catch (...) {               // catch any exception
            delete[] a2;              // cleanup before throw
            throw;
        }
        cap *= 2;
        delete[] a;
        a = a2;
    }
    a[sz] = x;          // if throw here, all did was increasing cap
    sz++;               // separate sz++
}

[!warning] Still issues! On a[sz] = x, operator=(MyString) may leave the default constructor in a bad state - Assume if copy assignment fails, it still leaves a valid object there

[!info] Might be more efficient if the elements are moved, rather than copy std::vector tries to move elements during reallocation, but

• Move may not easy to roll back on exception

std::vector uses the criteria:

1. Moved if move constructor marked noexcept
2. Copy else
3. If copy constructor deleted, the fall back to move (forgo strong exception guarantee)