I see many questions about the pile overflow from students looking for help with their homework questions. Some of these homework questions use manual memory management. Many bare pointers to the allocated heap memory are passed around. No object has these pointers. Most questions about manual storage management have the following in the comments section:
Why don't you just use it std::vector? –totally_rad_programmer_guy
We haven't learned that yet. The professor said we cannot use vector –OP student
I find that very frustrating. Manual memory management is worth a lesson, but if someone is new to a language, let them use the cool toys first! Teach them in C ++ 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 that way. Have fun."
i created dumb::vector as a class that the student can add to their homework to do storage management. You still have to read and understand it. At least you have to change it. But now they can focus on programming, not juggling pointers.
I also offer a stripped down one dumbestvector Class that is super minimal.
This code is about using a minimum of new concepts when introducing memory management. I want to reduce the student's cognitive load so it is more likely to be adopted dumb::vector. So there are none explicit. None of the functions is const. I use unsigned int instead of std::size_t.
dumbvector.h, dumbestvector.h, and test.cpp are the three main files. Below you will find information on your rating pleasure. The Github link is here: https://github.com/jfilleau/dumbvector
dummvector.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
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 from the top of this file.
// dumb::vector v = {1, 1, 2, 3, 5, 8, 13};
vector(const std::initializer_list& 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
dummestvector.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
#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;
}
}
```
