CT 301 Homework 2

1. Overview

You will implement ct::Vector<T>, a class template that behaves like std::vector. The entire class lives in one header file, ctvector.h. About 90 percent of its interface matches std::vector, so the public reference for behavior is cppreference: en.cppreference.com/w/cpp/container/vector.

Homework 1 was about ownership with smart pointers, where you never wrote new or delete. Homework 2 is the other side of that coin. Here you manage raw memory yourself: you allocate uninitialized storage, construct objects into it with placement new, destroy them with explicit destructor calls, and grow the buffer as it fills. This is exactly what std::vector does under the hood, and building it is how you learn how it works.

You may not use std::vector and you may not use smart pointers. Storage is managed with raw pointers and ::operator new / ::operator delete. You may use the rest of the standard library freely, including <algorithm> and the uninitialized-memory helpers in <memory>.

2. What We Provide, What You Implement

3. Learning Objectives

• Manual memory management. Allocate raw storage with ::operator new, construct in place with placement new, destroy with explicit ~T() calls, and free with ::operator delete. Allocation and construction are separate steps.
• A growth policy. Keep a size and a larger capacity. When the buffer is full, allocate a bigger one (doubling), move the existing elements into it, destroy the old ones, and free the old buffer.
• Move construction into uninitialized memory. Growing the buffer means moving live objects into raw space, not copying them.
• Class templates. The whole class is parameterized on the element type T.
• Function and variadic templates. The iterator-pair constructor, assign, and range insert are function templates; emplace and emplace_back are variadic templates that perfectly forward their arguments.

4. The Vector Interface

All members are declared in the provided ctvector.h. The class is in namespace ct, uses the header guard CT_VECTOR_H, and is compiled as C++26. Below are the groups; cppreference gives the exact semantics for each, since they match std::vector.

4.1 Member typedefs

value_type, size_type, difference_type, pointer, const_pointer,
reference, const_reference, iterator, const_iterator,
reverse_iterator, const_reverse_iterator

iterator is T* and const_iterator is const T*. Because these are raw pointers, they are random-access iterators, so the standard algorithms work on your vector directly (Section 4.7).

These are written with using NAME = TYPE;, the modern spelling of a type alias, and the starter gives you all of them. In older code you will see the same idea written the other way around as typedef TYPE NAME; (for example typedef std::size_t size_type;). They mean exactly the same thing; using is preferred now because it reads left to right like an assignment and also works for templates, which typedef cannot do.

4.2 Constructors, assignment, assign

Vector() noexcept;
explicit Vector(size_type count);
Vector(size_type count, const T& value);
Vector(std::initializer_list<T> list);
Vector(const_iterator first, const_iterator last);
Vector(const Vector& other);
Vector(Vector&& other) noexcept;
~Vector();

Vector& operator=(const Vector&);
Vector& operator=(Vector&&) noexcept;
Vector& operator=(std::initializer_list<T>);

void assign(const_iterator first, const_iterator last);
void assign(size_type count, const T& value);
void assign(std::initializer_list<T> ilist);

4.3 Element access

at(pos)        // bounds-checked: throws std::out_of_range
operator[](pos)// not bounds-checked
front()  back()  data()    // const and non-const overloads of each

4.4 Iterators

begin()  end()  cbegin()  cend()
rbegin() rend() crbegin() crend()    // use std::reverse_iterator

4.5 Capacity

empty()  size()  max_size()  capacity()
reserve(new_cap)      // grow the buffer if needed; never shrinks
shrink_to_fit()       // reduce capacity to size

4.6 Modifiers

clear();
insert(pos, value);                 insert(pos, T&& value);
insert(pos, count, value);          insert(pos, first, last);
insert(pos, initializer_list);
emplace(pos, args...);
erase(pos);                         erase(first, last);
push_back(value);                   push_back(T&& value);
emplace_back(args...);              pop_back();
resize(count);                      resize(count, value);
swap(other);

Non-member functions: operator==, operator!=, and swap(a, b).

There is no sort() member, because std::vector does not have one. To sort, use std::sort(v.begin(), v.end()).

4.7 The standard algorithms work on your vector

Because your iterators are real random-access iterators, you do not write a sort, a find, or a max. You build the iterators, and the library does the rest:

ct::Vector<int> v{5, 3, 1, 4, 2};
std::sort(v.begin(), v.end());                 // 1 2 3 4 5
auto it = std::find(v.begin(), v.end(), 4);    // points at the 4
int  hi = *std::max_element(v.begin(), v.end());

4.8 Two keywords in the signatures: noexcept and explicit

Keep these exactly as given; they are part of the interface, and they change behavior.

• noexcept is a promise that a function will not throw. The move constructor, the move assignment, and swap are marked noexcept, and they must truly never throw (they only shuffle a pointer and two integers). This is not decoration: when a vector grows, it will move your elements into the new buffer only if their move is noexcept; otherwise it must fall back to copying to stay safe. The reason is that a throw in the middle of moving elements into a fresh buffer would leave you with some elements moved and some not and no clean way to recover, so the library refuses to move unless it is told the move cannot throw. A move that is not noexcept therefore quietly costs you copies. The plain getters (size, begin, and so on) are noexcept because they cannot fail.
• explicit controls implicit conversion. An implicit conversion is one the compiler does for you, without being asked, to make two types line up: when you write double d = 5; the int 5 is turned into a double on its own, and you never wrote a cast. A one-argument constructor can act as a conversion the same way, so without explicit the compiler would happily turn a bare number into a Vector by itself. Marking Vector(size_type count) as explicit blocks that: you must ask for it on purpose by writing Vector<int> v(5). Without explicit, an int would quietly become a 5-element vector wherever a Vector is expected (for example Vector<int> v = 5;, or passing 5 to a function that takes a Vector), which is a classic source of surprising bugs. Single-argument constructors are marked explicit for exactly this reason.

4.9 A few standard tools you will use

These are general C++ tools, shown on their own so you recognize them when they turn up in your code.

• static_cast<Type>(x) converts x to Type deliberately. You need it whenever you turn the difference of two iterators into an index: pos - begin() is a signed ptrdiff_t, but you index with the unsigned size_type, so you write static_cast<size_type>(pos - begin()). Without the cast the compiler warns about a signed-to-unsigned conversion, and warnings cost points. Rule of thumb: when you make an index out of a pointer subtraction, cast it.
• std::move(x) does not move anything by itself. It is a cast that says "you may treat x as something to move from," which lets a move constructor or move assignment run instead of a copy. Example: std::string a = "hello"; std::string b = std::move(a); hands a's buffer to b instead of copying it (afterward a is valid but unspecified).
• std::rotate(first, middle, last) rearranges a range so the element at middle becomes first and the rest wrap around. Example: on 1 2 3 4 5 with middle pointing at the 4, you get 4 5 1 2 3. It only moves existing elements around; it constructs and destroys nothing.
• std::destroy_n and the uninitialized_* family are the raw-memory tools, explained in Section 5.

5. How the Memory Works

This is the heart of the assignment. A vector keeps three things: a pointer to a raw buffer, a size (how many elements are constructed), and a capacity (how many the buffer can hold). The buffer is bigger than the number of live elements, and the extra space is raw, uninitialized memory.

• Allocate, do not construct. ::operator new(bytes) gives you raw bytes with no objects in them. No constructors run.
• Construct in place. Placement new (ptr) T(args...) builds one object in a slot you already own. push_back constructs into the next free slot and increments size.
• Destroy, do not free. Calling ptr->~T() runs the destructor of one element without freeing the buffer. pop_back destroys the last element and decrements size.
• Grow when full. When size == capacity and you need more room, allocate a larger buffer (double it), move-construct the existing elements into the new buffer, destroy the old elements, free the old buffer, and switch over.

A push that triggers a grow:

// when size_ == capacity_, make room first:
size_type new_cap = (capacity_ == 0) ? 8 : capacity_ * 2;
T* new_data = static_cast<T*>(::operator new(sizeof(T) * new_cap));   // raw bytes
std::uninitialized_move_n(elements_, size_, new_data);                // move live ones in
std::destroy_n(elements_, size_);                                     // destroy old ones
::operator delete(elements_);                                        // free old buffer
elements_ = new_data; capacity_ = new_cap;

// now construct the new element into the free slot:
new (elements_ + size_) T(value);                                    // placement new
++size_;

The dangerous part is mixing these up: constructing over a slot that still holds a live object leaks it, and destroying a slot that was never constructed is undefined behavior. The sanitizers (Section 6) catch both. The provided sample test compares your vector against std::vector, which is the easiest way to see when behavior diverges.

The raw-memory algorithms (your toolbox)

All of these live in <memory> and act on a pointer into raw, uninitialized storage (the bytes you got from ::operator new). The uninitialized_* family runs constructors to bring objects to life in that storage; the destroy_* family runs destructors to end them. Neither one allocates or frees: you do that yourself. You reach for these instead of a plain loop or assignment because you cannot assign into raw memory (assignment needs a living object on the left), and because if a constructor throws partway through, the uninitialized_* functions clean up whatever they already built.

Constructing into raw storage:

// value-initialize n objects (scalars become 0; classes get their default ctor)
std::uninitialized_value_construct_n(buf, 3);          // buf[0..2] alive; ints are 0

// copy one value into n slots
std::uninitialized_fill_n(buf, 3, 7);                  // buf[0..2] = 7, 7, 7

// copy a range [first,last) into raw storage at buf
std::uninitialized_copy(src, src + 3, buf);            // copy-constructs src[0..2] into buf

// move n objects from src into raw storage at buf
std::uninitialized_move_n(src, 3, buf);                // move-constructs src[0..2] into buf

Destroying (without freeing):

std::destroy_at(buf + 2);                              // run ~T() on the one object at buf[2]
std::destroy_n(buf, 3);                                // run ~T() on buf[0..2]

Connecting the points: a constructor uses one of the four builders to fill a fresh buffer (value-construct for "n empty", fill for "n copies of x", copy or move to bring elements from somewhere else); a destructor or clear uses destroy_n; pop_back and a single erase use destroy_at; and a grow does both, uninitialized_move_n into the new buffer then destroy_n on the old. Pair every one of these with the matching raw allocation: ::operator new to get the bytes, ::operator delete to release them.

6. Constraints, Tooling, and Build

• Language: C++26, built with GCC 15.2. Use #include, not import std;.
• Build with the provided makefile, which compiles with -std=c++26 -Wall -Wextra -Wpedantic -fsanitize=address,undefined -g. Your code must compile with no warnings.
• No std::vector and no smart pointers (unique_ptr, shared_ptr). Manage storage with raw pointers. Unlike Homework 1, new and delete are expected here.
• Do not change the given signatures.
• You may use any platform (your machine, a VM, the lab or school servers, WSL) as long as you build with GCC 15 and these flags.

Building with make

From the folder with your files, the provided makefile builds and runs everything. The binaries are written into that folder; there is no separate build or debug directory.

make          # build both programs (same as make all)
make main     # build the sandbox   -> ./main
make tests    # build the tester    -> ./student_tests
make relax    # build without the sanitizers (faster; see below)
make clean    # remove the built programs

The default build uses the same flags the autograder uses: -std=c++26 -Wall -Wextra -Wpedantic -g -fsanitize=address,undefined. That is a debug build on purpose, with no optimization and the sanitizers on, so it runs slower but catches memory mistakes and points you at the exact file and line.

7. Testing

You must test your own code, and testing is part of the grade because your code is run against cases you will not have seen. The easiest method: build the same sequence of operations in a ct::Vector and a std::vector in your own main, then compare sizes and elements. The provided main.cpp is a starting point; add your own cases. Test with several element types, not just int: a type with a destructor (such as std::string) and a move-only type (such as a unique pointer to int) reveal bugs that int hides.

g++ -std=c++26 -Wall -Wextra -Wpedantic -fsanitize=address,undefined -g \
    main.cpp -o ctvector_test
./ctvector_test

Or build the provided tester with make tests and run ./student_tests. It gives you a set of named test functions: a couple are written for you as worked examples, and the rest are marked [TODO] for you to finish. Each one builds a small vector, does something, and uses the check() helper to confirm the result. It is not the grader, and the real grading uses cases you will not see, so use it to build confidence and catch your own mistakes early.

A reasonable order to implement

1. The foundation: the raw storage helpers and reserve, then begin / end, then size / empty / capacity.
2. Add and remove: push_back, pop_back, the destructor, clear.
3. Build them up: the remaining constructors, copy and move, both assignment operators.
4. The rest: the insert / erase / resize family, the reverse iterators, operator==, and the remaining access and iterator members.

Some members of the starter are written for you as worked examples, but they call helpers you implement (the growth path, begin / end, push_back), so they do not work until those helpers are done. That is why the foundation comes first. Test small before you go big: check a three or four element vector by hand, then use the larger generators in fixtures.h and watch the buffer grow through many reallocations.

Reading a failure

Two kinds of failure mean different things:

• A wrong value (a failed check, or output that does not match std::vector) means the logic is off. Compare what you expected against what your function produced.
• A sanitizer report or a segmentation fault means a memory bug: a pointer used before it was allocated, after it was freed, or past size(). The report names the file and line; read the top frame of the stack trace first.

A segfault or an out-of-bounds write is not a C++ exception, so wrapping your code in try / catch will not catch it. The sanitizer stopping at the exact line is the most precise bug report you will get; treat it as the place to look, not as something to suppress.

8. The Driver

Put your vector to work. In driver.cpp, implement the five functions declared in driver.h (namespace ctlab). This is part of the assignment: you submit driver.cpp alongside ctvector.h, and it is graded (Section 9). Our grading program supplies its own main and calls these functions on its own vectors, so match the signatures exactly.

int       largest(const ct::Vector<int>& v);     // max element; write it yourself
long long total(const ct::Vector<int>& v);       // sum of elements
bool      contains(const ct::Vector<int>& v, int value);
std::size_t count_even(const ct::Vector<int>& v);
ct::Vector<int> sorted_copy(const ct::Vector<int>& v); // a sorted copy; std::sort allowed

9. Grading (100 points, fully automated)

Graded automatically. You may resubmit as many times as you like before the deadline. The autograder reports which checks failed so you can iterate.

Component	Points
Compiles cleanly and runs sanitizer-clean (no warnings, no leaks)	13
Memory core: allocate, deallocate, reserve, the growth policy, shrink_to_fit	47
Construction, destruction, copy, move, and assignment	9
assign, member swap, and operator==	4
Element access (at, operator[], front, data)	4
Iterators (forward and reverse)	4
Capacity (empty, size, capacity)	3
Modifiers (push_back, emplace_back, insert, erase, resize, pop_back, clear)	10
Driver functions (Section 8)	6
Penalty: std::vector or smart pointers in your source	up to -20
The professor reserves the right to award or deduct points for any aspect not explicitly listed above.

Points go only to functions you implement; the worked-example functions already written in the starter are not graded. The memory core carries the most weight, and reserve the most within it. Every function is tested on more than one element type, including a move-only type, so a function that works only for int will lose points.

10. Design Document

Along with your code you submit a short design document, as a separate PDF on Canvas (Section 13). It is described in full here.

About

Along with your code, you submit a short design document describing how you approached this assignment. The document carries no points on its own. I am not grading it for grammar, style, or writing quality. I want to read, in your own words, how you worked through the problem and what you took away from it.

Write it yourself. The point is to hear your own thinking, not a generated summary of it.

AI is not allowed for this document. Do not generate it, in whole or in part, with an AI tool.

What to cover

Cover these four things. You do not need headings for each, but they should all be there.

1. How you navigated the process. Where you started, the order you built things in, how you tested as you went, what you changed along the way.
2. What you learned. Ideas or techniques that are clearer to you now than when you started. For this assignment, that often includes the split between allocating memory and constructing objects, what placement new really does, or why growing the buffer is a move and not a copy.
3. What you found difficult. List at least five things and no more than ten. For each, say briefly what made it hard and how you got past it (or that you did not).
4. Your design choices. Decisions you made in your own code, why you made them, and any tradeoffs you saw.

Including code snippets

When you talk about a design choice, it helps to show a few lines of your own code and then explain them. Keep snippets short (a few lines, not whole functions). Put the code in a monospace block, then explain what it does and why you wrote it that way. For example:

T* new_data = static_cast<T*>(::operator new(sizeof(T) * new_cap));
std::uninitialized_move_n(elements_, size_, new_data);
std::destroy_n(elements_, size_);
::operator delete(elements_);

Here I grow the buffer: I allocate raw bytes with ::operator new, move the live elements into them, destroy the old elements, then free the old buffer. I used ::operator new rather than new T[new_cap] because I do not want to construct anything in the new space yet. The extra slots stay raw until an element is actually pushed. That is the snippet-then-explanation pattern: show the code, then say what it does and why.

Length and format

• One to two pages is recommended; keep it short. Appendices and references do not count toward the length. Include references only if you cite something.
• Font: Arial 11 point or Times New Roman 12 point. Pick one.
• Spacing: single spaced, with 1 inch margins on all sides (the usual default in Word).
• Alignment: justified (see below).

Keep it organized and succinct. Short, clear paragraphs are better than long ones.

How to submit

• Submit the document as a PDF.
• Upload it to the same Canvas assignment as your code, as a separate file. Canvas accepts more than one file per submission.
• Do not put the PDF inside your code zip. A PDF inside the zip will be ignored.

Grading

The document carries no points by itself. However, a missing document or one that shows no serious effort will cost at least 10 points, and possibly more. I reserve the right to deduct beyond that, and I also reserve the right to award positive points for a document that is genuinely thoughtful.

11. Extra Credit

• Bug Hunt. If you find a real defect in the code we provided, report it in the Homework 2 channel for extra credit. The amount depends on the severity. First come, first served, so it must be reported in the channel.

There is also a separate, optional assignment, the Homework 1 Swap, which reuses your ct::Vector inside Homework 1. It has its own handout and its own submission; see that document.

12. Use of AI

You may use AI tools. The exams are weighted heavily and will test whether you actually understand this material, so using AI to produce code you cannot explain will hurt you on the exams. Use AI the way you would use a knowledgeable tutor or documentation: to ask questions, clarify concepts, and check your reasoning, not to generate a solution you do not understand. The design document (Section 10) must be your own writing and may not be generated by AI.

13. What to Submit

Submit a single .zip whose files sit directly in the archive, not inside a folder.

File	Required?
ctvector.h	Yes
driver.cpp	Yes

• Do not include a makefile or your main.cpp; the grader supplies its own.
• Filenames are case sensitive. ctvector.h is not the same as Ctvector.h or ctvector.H. If names do not match exactly, your code will not be graded.
• A short design document as a separate PDF (uploaded alongside the zip on Canvas, not inside it). See Section 10. It must be your own writing, not generated by AI.

On Linux, from the folder with your files:

zip hw2.zip ctvector.h driver.cpp

If the folder contains only the files you intend to submit, zip hw2.zip * also works. Do not use zip -r with a folder name, because that puts the folder inside the archive. On Windows, select the files, right click one of them, and choose Send to, then Compressed (zipped) folder.