I have created a small library for use by beginner C++ students who are forbidden from using std::vector
in their projects. Because of this, I would like you to review my code from the viewpoint of:
Is this code readable, usable, and accessible by beginners in C++?
I see a lot of questions on stackoverflow by students looking for help on their homework questions. Some of these homework questions use manual memory management. Lots of naked pointers to heap allocated memory being passed around. No object owns these pointers. Most of the questions with manual memory management have something like this in the comment section:
Why don't you just use
std::vector
? --totally_rad_programmer_guyWe haven't learned that yet. The professor said we can't use
vector
--OP Student
I find these very frustrating. Manual memory management is worth teaching, but if someone is new to a language, let them use the cool toys first! For C++, teach them about encapsulation and RAII and the Rules of 0/3/5. Let them use std::vector
out of the gate. "This is a vector. You access it like this. Enjoy."
I created dumb::vector
as a class that the student can add to their homework to handle memory management. They still have to read and understand it. They at least have to modify it. But now they can focus on programming and not juggling pointers.
I also provide a stripped down dumbestvector
class that is super minimal.
The point of this code is to use the bare minimum new concepts while introducing memory management. I want to reduce the cognitive load on the student so they're more likely to adopt dumb::vector
. So there's no explicit
. None of the functions are const
. I use unsigned int
instead of std::size_t
.
dumbvector.h
, dumbestvector.h
, and test.cpp
are the three main files. Provided below for your reviewing pleasure. The github link is here: https://github.com/jfilleau/dumbvector
dumbvector.h:
#ifndef DUMB_VECTOR_H
#define DUMB_VECTOR_H
/* dumb::vector
"I'm not allowed to use std::vector!" the student lamented on stackoverflow.
The commenters rolled their collective eyes.
*/
#include <initializer_list>
namespace dumb {
class vector
{
private:
// using something different than int? Change it here!
typedef int value_type;
value_type* data_;
unsigned int size_;
unsigned int capacity_;
public:
/* YOU MUST KEEP AT LEAST ONE OF THE FOLLOWING FOUR CONSTRUCTORS */
// This one lets you make an empty vector:
// dumb::vector v;
vector()
{
data_ = nullptr;
size_ = 0;
capacity_ = 0;
}
// This one lets you make a vector of a certain size.
// All elements are default constructed:
// dumb::vector v(10);
vector(unsigned int count)
{
data_ = new value_type[count];
size_ = count;
capacity_ = count;
}
// This one lets you make a vector of a certain size.
// All elements are default constructed, but then assigned value
// dumb::vector v(10, 1000); // 10 ints all set to value 1000
vector(unsigned int count, const value_type& value)
{
data_ = new value_type[count];
size_ = count;
capacity_ = count;
for (unsigned int i = 0; i < size_; ++i)
{
data_[i] = value;
}
}
// This one lets you use an initializer_list for creation.
// I know this might be confusing. If you don't want to use this one,
// remove #include <initializer_list> from the top of this file.
// dumb::vector v = {1, 1, 2, 3, 5, 8, 13};
vector(const std::initializer_list<value_type>& init_list)
{
size_ = init_list.size();
capacity_ = init_list.size();
data_ = new value_type[size_];
auto it = init_list.begin();
for (unsigned int i = 0; i < size_; ++i)
{
data_[i] = *it;
++it;
}
}
/* YOU MUST KEEP THE FOLLOWING THREE FUNCTIONS OR RULE OF 3 IS VIOLATED */
// copy constructor. Type MUST BE const reference
vector(const vector& other)
{
data_ = new value_type[other.size_];
size_ = other.size_;
capacity_ = other.size_;
for (unsigned int i = 0; i < size_; ++i)
{
data_[i] = other.data_[i];
}
}
// assignment operator. Other doesn't need to be const reference but it is good practice
vector& operator=(const vector& other)
{
delete[] data_;
data_ = new value_type[other.size_];
size_ = other.size_;
capacity_ = other.size_;
for (unsigned int i = 0; i < size_; ++i)
{
data_[i] = other.data_[i];
}
return *this;
}
// destructor
~vector()
{
delete[] data_;
}
/* THE FOLLOWING FUNCTIONS ARE OPTIONAL BUT RECOMMENDED DEPENDING ON YOUR NEEDS */
// allows index operations
// dumb::vector v(10, 5); // vector of size 10, all set to 5
// v[0] = 20; // set the first element to 20 instead
value_type& operator[](unsigned int pos)
{
return data_[pos];
}
unsigned int size()
{
return size_;
}
/* THE FOLLOWING FUNCTIONS ARE OPTIONAL DEPENDING ON YOUR NEEDS */
bool empty()
{
return size_ == 0;
}
// increase capacity if required, and copy the element to the end
void push_back(const value_type& value)
{
if (size_ == capacity_)
{
reserve(size_ + 1);
}
data_[size_] = value;
++size_;
}
// removes the last element from the vector. Does not return it.
void pop_back()
{
--size_;
// this overwrites what used to be the last element
// with a default constructed object of your type
// essentially deleting what used to be there
data_[size_] = value_type{};
}
// increases capacity if required, inserts a copy of the element at the chosen index
value_type* insert(unsigned int pos, const value_type& value)
{
if (size_ == capacity_)
{
reserve(size_ + 1);
}
for (unsigned int i = size_; i > pos; --i)
{
data_[i] = data_[i - 1];
}
data_[pos] = value;
++size_;
return data_ + pos;
}
// copies every element above pos down a slot
value_type* erase(unsigned int pos)
{
--size_;
unsigned int i;
for (i = pos; i < size_; ++i)
{
data_[i] = data_[i + 1];
}
// this overwrites what used to be the last element
// with a default constructed object of your type
// essentially deleting what used to be there
data_[i] = value_type{};
return data_ + pos;
}
// Copies all the elements in the vector to a larger data allocation.
// Accessing that extra space is undefined behavior.
// dumb::vector v;
// v.reserve(10); // increases capacity to 10
// for (unsigned int i = 0; i < 10; i++)
// v.push_back(i); // doesn't keep copying the entire vector on every push_back()
void reserve(unsigned int new_cap)
{
if (new_cap <= capacity_)
return;
value_type* new_data = new value_type[new_cap];
for (unsigned int i = 0; i < size_; ++i)
{
new_data[i] = data_[i];
}
delete[] data_;
data_ = new_data;
capacity_ = new_cap;
}
// returns a raw pointer to the data. Really useful for
// functions that take a value_type[] as a parameter
value_type* data()
{
return data_;
}
// acts as an iterator so you can use iterator loops
// and range-based for loops
// for (auto i = v.begin(); i != v.end(); i++)
// func(*i);
// for (auto i : v)
// func(i);
value_type* begin()
{
return data_;
}
// same as above
value_type* end()
{
return data_ + size_;
}
};
}
#endif // DUMB_VECTOR_H
dumbestvector.h:
#ifndef DUMBEST_VECTOR_H
#define DUMBEST_VECTOR_H
/* dumbestvector
For when dumb::vector isn't dumb enough.
*/
class dumbestvector
{
private:
// using something different than int? Change it here!
typedef int value_type;
value_type* data_;
unsigned int size_;
public:
/* ONLY ONE CONSTRUCTOR IS AVAILABLE */
// This one lets you make a vector of a certain size.
// All elements are default constructed, but then assigned value
// dumbestvector v(10, 1000); // 10 ints all set to value 1000
dumbestvector(unsigned int count, const value_type& value)
{
data_ = new value_type[count];
size_ = count;
for (unsigned int i = 0; i < size_; ++i)
{
data_[i] = value;
}
}
/* YOU MUST KEEP THE FOLLOWING THREE FUNCTIONS OR RULE OF 3 IS VIOLATED */
// copy constructor. Type MUST BE const reference
dumbestvector(const dumbestvector& other)
{
data_ = new value_type[other.size_];
size_ = other.size_;
for (unsigned int i = 0; i < size_; ++i)
{
data_[i] = other.data_[i];
}
}
// assignment operator. Other doesn't need to be const reference but it is good practice
dumbestvector& operator=(const dumbestvector& other)
{
delete[] data_;
data_ = new value_type[other.size_];
size_ = other.size_;
for (unsigned int i = 0; i < size_; ++i)
{
data_[i] = other.data_[i];
}
return *this;
}
// destructor
~dumbestvector()
{
delete[] data_;
}
/* THE FOLLOWING FUNCTIONS ARE OPTIONAL BUT RECOMMENDED DEPENDING ON YOUR NEEDS */
value_type& operator[](unsigned int pos)
{
return data_[pos];
}
unsigned int size()
{
return size_;
}
// returns a raw pointer to the data. Really useful for
// functions that take a value_type[] as a parameter
value_type* data()
{
return data_;
}
};
#endif // DUMBEST_VECTOR_H
test.cpp:
#include <iostream>
#include "dumbvector.h"
#include "dumbestvector.h"
void print_vec_it(dumb::vector vec);
void print_vec_loop(dumb::vector vec);
void print_dumbest(dumbestvector vec);
void insertion_sort(dumb::vector& vec);
void insertion_sort(dumbestvector& vec);
int main(int argc, char** argv)
{
// create an empty dumb::vector and push_back elements into it
dumb::vector v1;
v1.push_back(0);
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
// we can either use iterators or loops to access the contents
std::cout << "Testing iterator printing:\n";
print_vec_it(v1);
std::cout << "Testing loop printing:\n";
print_vec_loop(v1);
// pop pop!
v1.pop_back();
std::cout << "Testing pop_back(). Should be one fewer item then before:\n";
print_vec_it(v1);
// testing that insert works
v1.insert(0, 10);
std::cout << "Testing insert(0, 10). First element should be 10:\n";
print_vec_it(v1);
v1.insert(2, 20);
std::cout << "Testing insert(2, 20). Third element should be 20:\n";
print_vec_it(v1);
// testing that operator[] works
v1[0] = 6;
v1[4] = 12;
std::cout << "Testing operator[]. v[0] = 6; v[4] = 12;\n";
print_vec_it(v1);
// testing that copy construction works
dumb::vector v2 = v1;
std::cout << "Testing copy construction. Should be same as above:\n";
print_vec_it(v2);
// testing that erase works
std::cout << "Testing erase. Fourth element should be erased:\n";
v2.erase(3);
print_vec_it(v2);
// testing that assignment operator works
v1 = v2;
std::cout << "Testing operator=. Should be same as above:\n";
print_vec_it(v1);
// testing that initializer lists work
dumb::vector v3{ 1, 1, 2, 3, 5, 8, 13 };
dumb::vector v4 = { 21, 34, 55, 89 };
std::cout << "Testing initializer_list construction. Should be { 1, 1, 2, 3, 5, 8, 13 }:\n";
print_vec_it(v3);
std::cout << "Testing initializer_list construction. Should be { 21, 34, 55, 89 }:\n";
print_vec_it(v4);
dumb::vector v5 = { 7, 0, -8, 100, 12345, 2, 22 };
std::cout << "Testing a common use case, insertion sort. Unsorted dumb::vector:\n";
print_vec_it(v5);
insertion_sort(v5);
std::cout << "After sorting:\n";
print_vec_it(v5);
// test dumbest vector
dumbestvector v6(10, 100);
std::cout << "Testing dumbest vector. Should be 10 elements of value 100:\n";
print_dumbest(v6);
v6[5] = 0;
std::cout << "Testing operator[]. v[5] = 0:\n";
print_dumbest(v6);
for (unsigned int i = 0; i < v6.size(); i++)
{
v6[i] = i * -10;
}
std::cout << "Testing dumbestvector insertion sort. Unsorted:\n";
print_dumbest(v6);
insertion_sort(v6);
std::cout << "After sorting:\n";
print_dumbest(v6);
}
void print_vec_it(dumb::vector vec)
{
std::cout << "[ ";
for (const auto& i : vec)
{
std::cout << i << " ";
}
std::cout << "]\n";
}
void print_vec_loop(dumb::vector vec)
{
std::cout << "[ ";
for (unsigned int i = 0; i < vec.size(); ++i)
{
std::cout << vec[i] << " ";
}
std::cout << "]\n";
}
void print_dumbest(dumbestvector vec)
{
std::cout << "[ ";
for (unsigned int i = 0; i < vec.size(); ++i)
{
std::cout << vec[i] << " ";
}
std::cout << "]\n";
}
void insertion_sort(dumb::vector& vec)
{
unsigned int i = 1;
while (i < vec.size())
{
unsigned int j = i;
while (j > 0 && vec[j - 1] > vec[j])
{
std::swap(vec[j], vec[j - 1]);
j -= 1;
}
i += 1;
}
}
void insertion_sort(dumbestvector& vec)
{
unsigned int i = 1;
while (i < vec.size())
{
unsigned int j = i;
while (j > 0 && vec[j - 1] > vec[j])
{
std::swap(vec[j], vec[j - 1]);
j -= 1;
}
i += 1;
}
}
```