Read the reference first. This assignment rebuilds the interface of std::vector. You are responsible for reading what each function is supposed to do, what it returns, what it throws, and what it guarantees, before you implement it, on cppreference: en.cppreference.com/w/cpp/container/vector. Reading the reference for a function before you write it is part of the work, not optional. Your ct::Vector mirrors that behavior, with the two differences this document spells out: the range members take a const_iterator instead of a template, and you manage the memory by hand.
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>.
Provided:
ctvector.h starter, with every signature you must implement (and nothing else). Do not change the signatures.driver.h, the fixed contract for the driver functions (Section 8).fixtures.h, a small set of interesting vectors to experiment with.main.cpp, a sandbox you can extend while developing. You do not submit it.student_tests.cpp, a tester with named test functions: a couple are written for you as examples and the rest are marked TODO for you to finish. You do not submit it.makefile, which builds main and the tester. You do not submit it.You implement:
ctvector.h.driver.cpp (Section 8). You submit this file too.::operator new, construct in place with placement new, destroy with explicit ~T() calls, and free with ::operator delete. Allocation and construction are separate steps.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.T.assign, and range insert are function templates; emplace and emplace_back are variadic templates that perfectly forward their arguments.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.
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.
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);
at(pos) // bounds-checked: throws std::out_of_range operator[](pos)// not bounds-checked front() back() data() // const and non-const overloads of each
begin() end() cbegin() cend() rbegin() rend() crbegin() crend() // use std::reverse_iterator
empty() size() max_size() capacity() reserve(new_cap) // grow the buffer if needed; never shrinks shrink_to_fit() // reduce capacity to size
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()).
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());
noexcept and explicitKeep 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.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.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.
::operator new(bytes) gives you raw bytes with no objects in them. No constructors run.new (ptr) T(args...) builds one object in a slot you already own. push_back constructs into the next free slot and increments size.ptr->~T() runs the destructor of one element without freeing the buffer. pop_back destroys the last element and decrements size.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.Use the raw forms, not new / delete. ::operator new and ::operator delete move only bytes: no constructor runs on the way in, no destructor on the way out. That is exactly what you want, because you construct and destroy the elements yourself (placement new and explicit ~T()). Plain new T / delete p would construct and destruct one object and assume the block is a single T, so using them here would double-destroy an element and corrupt your buffer. Pair them: ::operator new goes with explicit ~T(), placement new goes with ::operator delete.
Placement new is not the regular new. The everyday T* p = new T(args); does two things at once: it allocates memory for one object and then constructs into it. Placement new, written new (address) T(args), does only the second half: it constructs a T at an address you already own and allocates nothing. That is what a vector needs, because you allocate the whole buffer once and then bring elements to life one slot at a time, so new (elements_ + size_) T(value); builds an element in the next free slot. Do not mix them up: regular new grabs fresh memory for every object; placement new reuses the buffer you already have, and you free that buffer yourself with ::operator delete.
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.
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.
#include, not import std;.-std=c++26 -Wall -Wextra -Wpedantic -fsanitize=address,undefined -g. Your code must compile with no warnings.std::vector and no smart pointers (unique_ptr, shared_ptr). Manage storage with raw pointers. Unlike Homework 1, new and delete are expected here.About the sanitizers. -fsanitize=address,undefined turns on two runtime checkers:
Your vector must run with zero sanitizer reports. For this assignment that mostly means: every element you construct is destroyed exactly once, and you never touch a slot you have not constructed.
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.
A faster build while you iterate: make relax. make relax builds the same two programs but with the sanitizers turned off, so they compile and run faster while you are still working things out. It keeps the warnings on, because those are cheap and worth seeing. Use it to move quickly, but grading uses the strict build, so run make clean and then make all with no warnings and no sanitizer reports before you submit. The relaxed build will not catch the memory mistakes the sanitizer build catches, which is exactly why it is the quick option and not the one to trust.
If you see "Clock skew detected." A message like make: warning: Clock skew detected. Your build may be incomplete. is harmless. It means a file looks newer than the machine's clock, which is common right after you unzip or on a networked home directory. Reset the timestamps and rebuild: run make clean, then touch *, then make all. Confirm the programs exist with ls -l main student_tests and run them.
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.
reserve, then begin / end, then size / empty / capacity.push_back, pop_back, the destructor, clear.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.
Two kinds of failure mean different things:
std::vector) means the logic is off. Compare what you expected against what your function produced.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.
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
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.
Along with your code you submit a short design document, as a separate PDF on Canvas (Section 13). It is described in full here.
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.
Cover these four things. You do not need headings for each, but they should all be there.
new really does, or why growing the buffer is a move and not a copy.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.
What "justified" means. Text alignment controls how lines line up at the edges of the page.
In Microsoft Word, select your text and press Ctrl+J (Windows) or Cmd+J (Mac), or use the justify button in the paragraph toolbar. Google Docs and LibreOffice have the same option in the alignment controls.
Keep it organized and succinct. Short, clear paragraphs are better than long ones.
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.
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.
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.
Submit a single .zip whose files sit directly in the archive, not inside a folder.
| File | Required? |
|---|---|
ctvector.h | Yes |
driver.cpp | Yes |
main.cpp; the grader supplies its own.ctvector.h is not the same as Ctvector.h or ctvector.H. If names do not match exactly, your code will not be graded.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.