Now you manage the memory yourself

• HW1 used unique_ptr and RAII, the library freed things for you.
• HW2 you build a container that owns a raw buffer and manages every element by hand.
• The goal: feel what the library does for you, so you understand and trust it.

Raw new/delete were banned in HW1 on purpose. HW2 is where you finally use raw memory.

Capacity is not size

capacity ≥ size, always. The slots past size_ are memory with no object in them yet.

new[] can't do what a vector needs

So the vector splits allocation from construction. The next slides are the four tools.

Raw bytes: ::operator new / delete

• ::operator new(bytes) gives raw memory, no constructors run.
• ::operator delete(p) frees it, no destructors run.

void* raw = ::operator new(sizeof(T) * capacity);
T* buf = static_cast<T*>(raw);   // bytes, not objects yet
::operator delete(buf);            // frees bytes only

Construct in place: placement new

new (elements_ + size_) T(value);   // build one element at the end
++size_;

Destroy by hand

• p->~T() runs the destructor without freeing memory.
• std::destroy_n(buf, n) and std::destroy_at(p) do a range.
• Every placement-new you do, you owe one destroy, or resources leak.

Allocate, construct, destroy, free

The uninitialized-memory helpers

• std::uninitialized_copy, uninitialized_fill_n, uninitialized_move_n, uninitialized_value_construct_n: construct a range into raw memory.
• std::destroy_n, std::destroy_at: destroy a range.

These are placement-new and destroy over a whole range, with exception safety built in. Use them.

reserve: move to a bigger buffer

Allocate bigger, move the elements over, destroy the old ones, free the old buffer.

Why move instead of copy

A move steals the internals and leaves the source empty. For a string, that is a pointer swap, not a full copy.

insert places an element by rotating

Build it at the end where it is easy, then rotate it back to where it belongs.

Two small things that matter

Type aliases and const-correctness

• Publish the names the STL expects: value_type, size_type, iterator, const_iterator, reference, and the rest.
• Provide const overloads of operator[], at, begin/end: a const vector is still readable.

The classic memory bugs

Also: leaks (freed bytes but forgot to destroy), off-by-one between size_ and capacity_.

A small std::vector, by hand

• Implement ct::Vector<T>: a single header, namespace ct, guard CT_VECTOR_H.
• It owns a raw buffer and manages every element's lifetime.
• You also write a small driver that uses it.

Everything hangs off three fields

Every function's job is to keep these three consistent.

Build the memory core first

• 1. allocate, deallocate, grow_if_needed, reserve.
• 2. default ctor, push_back, size/capacity, the destructor.
• 3. access (operator[], at), iterators (begin/end).
• 4. copy/move, then the rest of the modifiers.

Test after each step. Do not write the whole class and then compile once.

The memory core

• allocate / deallocate: the raw buffer via ::operator new / delete.
• grow_if_needed: the capacity policy. reserve: move to a bigger buffer. shrink_to_fit: trim.

T* allocate(size_type n){ return static_cast<T*>(::operator new(sizeof(T)*n)); }
void deallocate(){ ::operator delete(elements_); }   // bytes only

grow_if_needed

• If size_ + n still fits in capacity_, do nothing.
• Otherwise reserve a larger capacity, typically double (or a small start if empty).

Doubling is what makes a long run of push_backs cheap on average.

Constructors, destructor, copy, move

• Constructors: default, count, count-and-value, initializer-list, range, copy, move.
• ~Vector(): clear() then deallocate(), destroy elements, then free bytes.
• Copy = deep copy. Move = steal the buffer, leave source empty, noexcept.

Copy-and-swap

Vector& operator=(const Vector& other){
  Vector temp(other);   // deep-copy into a temporary
  swap(temp);           // take its buffer; temp frees the old one
  return *this;
}

Self-assignment just works, and you reuse the copy constructor and swap.

operator[] vs at(), and iterators

operator[] is unchecked; at() throws std::out_of_range. Iterators are just T*.

Adding and removing

• At the end: push_back/emplace_back (grow, then construct), pop_back (destroy last), clear (destroy all, capacity kept).
• In the middle: insert/emplace via std::rotate; erase moves the tail down; resize grows or shrinks.

emplace_back forwards its arguments and builds the element in place.

driver.cpp is required

• A small program that fills a vector and computes a total() over the data.
• It is part of the grade (6 points), not extra credit. Submit it.

It is also your own proof the vector works end to end.

What is not allowed

• No std::vector, no smart pointers. The point is to do the memory yourself.

Using the thing you are supposed to build is an automatic zero on the core.

Build with the sanitizers on

• Use the make targets; flags include -fsanitize=address,undefined.
• Test small first. A [FAIL] is a wrong value; a sanitizer abort or segfault is a memory bug.
• Don't wrap a segfault in try/catch, it is not catchable.

Where the points go, and what to submit

• Memory core 47 · cross-cutting 13 · modifiers 10 · construction 9
• Driver 6 · access 4 · iterators 4 · assign/swap/== 4 · capacity 3
• Submit ctvector.h + driver.cpp via Canvas. Build clean, 0 warnings.

Memory core plus cross-cutting is well over half. That is where to spend your time.

Dates

• HW2 due June 29, 11:59pm Colorado time. One day late = 10% (June 30).
• Exam 2: July 2.
• Optional re-upload of your lower HW1/HW2 grade as "HW3": July 6 (no late).
• Optional HW2 extra credit (posted later): July 7 (no late).
• Final: July 10, 9am to 9pm Colorado time.