2
\$\begingroup\$

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_guy

We 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;
    }
}
```
\$\endgroup\$
2
  • 1
    \$\begingroup\$ It's a bit hard to give a review on this - many good practices may be rejected as "too advanced" since they require, well, advanced features. Would it be fine if you receive a review that includes some advanced features (for the benefit of future readers)? You can selectively ignore the suggestions that you find unsuitable for beginners. \$\endgroup\$
    – L. F.
    Apr 14, 2020 at 10:31
  • \$\begingroup\$ Sure, why not? Go ham. \$\endgroup\$ Apr 14, 2020 at 12:32

1 Answer 1

6
\$\begingroup\$

Concept review

Bad teachers are, in my opinion, one of the biggest problems plaguing C++. It blows my mind that there are still people teaching C++ in 2021 using techniques used to teach C in the 1970s. The problem is so pervasive the standards committee even put together a working group specifically for the purpose of guiding people on how to properly teach C++.

So I think you have correctly identified a very real, very serious, and very pervasive problem. What I think you have incorrectly identified is where to go about fixing it. If the problem is shitty teachers, you’re not going to fix it by targeting the students.

But okay, maybe your goal isn’t to fix the problem, it’s just to help the students in a shitty situation. Unfortunately, on that count I think this kind of idea fails completely, for several reasons:

  1. It doesn’t actually help the student learn C++.

    Handing the student a ready-made class to use is hardly going to help them learn whatever it is they’re supposed to be learning in the assignment they’re struggling with. You may argue that it does, because (like the actual std::vector) it takes away the burden of worrying about all the manual memory management cruft so they can focus on the real thing being taught. That MAY be true… if the point of the teaching exercise wasn’t explicitly to understand what’s going on in memory in the solution. Which, frankly, it often is.

    But the point stands regardless, because if the point of these classes is to provide a vector-lite that the student can understand the inner workings of, then you’re doing them a disservice by writing those inner workings for them, and more so by “dumbing them down”. Let me put that point in point form, to see if that makes it clearer:

    • If they should understand C++ well enough to write dumb::vector… then why can’t they write dumb::vector themselves?
    • If they’re not supposed to understand C++ well enough to write dumb::vector… then why dumb it down so much? It’s over their head anyway, so why not just do it properly? Why not just re-implement std::vector? Or at least, implement a vector-lite that is still correct (that is, with explicit, const, and the works)?
  2. The teacher expects the student to do the manual memory management.

    Putting aside how terrible the teacher’s technique is, they are trying to teach the student something with the assignment. You assume that whatever they’re trying to teach is not manual memory management. That’s a rather specious assumption.

    The teacher has either taught the student everything they need to do the assignment—manual memory management and all—or provided them with the resources they need to figure out it. You are not helping the student by aiding in an end-run around the teacher’s lesson plan. Whatever the student was supposed to learn from the exercise… now they won’t. That’s not helping the student with their course; that’s literally the opposite of that.

  3. “Dumbing down” a language is a spectacularly bad way to teach it.

    Have you ever seen a book that teaches, say, French, by teaching the students pidgin “Frenglish” first? No, of course not. Because that would be both ridiculous and actively counter-productive.

    The proper way to teach a language is not to “dumb down” parts of the language that are too complicated to swallow at first. It’s to avoid those complicated parts until the student is ready. When the complexity is unavoidable, you still don’t “dumb it down”, you just present it as is as a matter of fact, and then work with that. For example, in theory just to get the student to introduce themselves in the simplest way, the teacher has to introduce the conjugations of the verb “être”—which is irregular. But of course, that’s not what they actually do; they just tell students that “je suis” is basically “I am”, and that’s that, and from there the student can tack on their name and voilà! They’re actually speaking real, honest-to-goodness French. Granted, all they can say is “I am John/Jane”… but that ain’t nothin’, and from there, the teacher will take the same construct (“je suis ___”) and expand the vocabulary with numbers (that is, age), the idea of linguistic gender (via giving one’s nationality or something else), and so on. Then next, maybe, you show how you can replace “I am/je suis” with “he/she/it is”, while using all the already introduced stuff (age, nationality), and so on, building up from there until eventually the student is ready to be shown the big picture (the full conjugation table).

    To use a C++ example, you wouldn’t just… hide const from students when teaching them about member functions. You would teach them basic member functions that don’t need const first… and then teach them when to use const. For example, you could introduce classes/structs as simple aggregate types (like “struct point { int x; int y; };”), then add a mutating member function (auto mirror_in_y_axis() { x = -x; }), then a non-mutating member function (auto distance_from_origin() const { return std::sqrt((x * x) + (y * y)); }), explaining everything at each step.

  4. Playing cute and trying to outsmart the teacher is most likely to backfire.

    I have to wonder exactly what you think will happen if a student turns an assignment with dumb::vector bundled in.

    • Teacher: I thought I said you couldn’t use the standard library.
    • Student: Ah, but that’s not the standard library vector. It’s a dumbed-down variant!
    • Teacher: But you didn’t write it yourself. That’s plagiarism.
    • Student: Ah, but, you see, I understand it because it’s dumbed down! Also, I did sorta type it myself! (Insofar as Ctrl+C && Ctrl+V counts as “typing”.)
    • Teacher: Well, you’ve completely outwitted me, so I guess I have no option but to give you an A!

    (… and that student’s name… was Albert Einstein!)

    Yeah, no. This is not going to end well for the student stupid enough to actually use dumb::vector in their assignment.

Let me say again that I completely understand your frustration at seeing C++ newbies struggling with bullshit that they really don’t need to be struggling with… both because it’s not necessary to learn the language well (at least not until very advanced stages), and because it’s functionally useless information in practice because who actually does low-level manual memory management like that anymore.

But….

To anyone who comes across a newbie struggling with a C++ problem that they HAVE to solve (because it’s an assignment, for example, rather than just personal amusement)… if you, for whatever reason, don’t want to help them solve THAT PROBLEM (you’d rather show them the “better” way to do it, using modern/advanced techniques or whatever)… then I say, with no personal rancour intended…: STFU.†

If you lack the patience to get into the weeds and walk the student through their malloc()/free() spaghetti soup, then DO NOT try to offer them a sly trick to get out of it all, and instead just…: STFU.

You are NOT helping the newbie by distracting them with all the lovely things they cannot have. You are only frustrating and confusing them. It’s fine to offer a glimpse of what lies beyond their shitty C++ course while also helping them in the way they need. But if you’re not willing to really get into the muck and walk WITH the learner through that grody, tedious, poorly conceived and formatted code—NOT simply giving them the answers, but rather guiding them to figure the answers out on their own—then, please…: STFU.

Let someone who actually wants to help do so, and don’t become distracting noise while they do.

† (And for those who don’t know that acronym, here’s a link that should clear it up: STFU.)

(Note that if you’re dealing with a situation where a learner does not HAVE to eschew the standard library—for example, someone just doing some self-directed learning, or “challenging” themselves for some reason—then that’s a very different situation. By all means, with those types, show them the correct way to do it. And if you feel disinclined to help them do it the way they want to do it… meh, then don’t bother; it’s not worth your time.)

Helping students is not about showing off your mad l33t C++ skillz. Or about showing them how to get away with not doing the work their C++ teacher expects them to do. Helping students is about working WITH the student to understand what THEY need… not what you think they need… and then figuring out how they can achieve that. It is NOT easy to do; not everyone is cut out for it, and even those of us who’ve done it for years do have moments when we look at a teacher’s instructions and go, “WTF is up with this bozo?!” But it’s always about the student, and their needs.

And I don’t think a student needs a dumb vector replacement.

Code review

Okay, if you’ve read my view on the concept, you know I think this whole project is fundamentally misguided. That being said, that’s my opinion, and you may disagree. That’s fine. In that case, I’ll review this code under the assumption that you think my philosophy of teaching is wrong, and a dumb vector-lite is a good idea; so I’ll be reviewing the code as-if it’s going to be used for the stated purpose, taking into account all the stated reasoning for it.

namespace dumb {

Cool, so far. I strongly approve of the use of a namespace, even though that’s something that so many shitty teachers try to avoid talking about (usually by telling students to use using namespace std;, natch). Even if someone wants to try claiming it’s an “advanced” feature, it’s something that can be glossed over trivially by saying “just use dumb::vector instead of vector”.

class vector

Alright, so I made my position clear in the concept review section, but this isn’t related to that: even assuming that the whole “dumb vector” thing is a good idea, I think you should basically throw dumb::vector out entirely, and just keep dumbestvector (but put that in the namespace and call it dumb::vector).

Why?

Well, dumbestvector may be “dumb”… but at least it isn’t wrong.

This…:

// 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;
}

… is not how you do capacity.

The comment is a lie—there is no UB accessing the elements beyond the size but still within the capacity.

The entire technique is misleading, because you might trick a newbie into thinking that if the size is 10 but the capacity is 20, that there are only 10 elements in the vector. You might confuse a newbie into thinking that new value_type[new_cap] just allocates space, but doesn’t actually initialize the elements in that space… you might deceive them into thinking that initialization doesn’t happen until the new_data[i] = data_[i]; line.

All-in-all, everything about this is just wrong.

And the worst part is, it’s entirely unnecessary. I mean, if someone isn’t even allowed to use std::vector… if they’re forced to do manual memory management… then they’re hardly in a situation where they’re really in need of extra capacity in their container. So their program will reallocate on every push_back()… so the fuck what? It’ll be slow? 🤷🏼

Hell, most experienced C++ coders don’t even use reserve() as often as they should. I think it’s something a newbie could do without.

typedef int value_type;

Okay, two things here. First, this should be public, not private.

Second, you should use the more modern form of type aliasing:

using value_type = int;

Why? Because it reads more naturally when considered with the rest of the language. One of the first things new C++ programmers have to internalize is that when you see a = b, that means you’re taking what’s on the right, and “assigning it into” what’s on the left. using a = b; fits that pattern beautifully.

It also works out much more clearly and logically when things start to get more complex. For example, what does typedef a * b; mean? Is a b a pointer to an a, or is a pointer to a b an a? On the other hand: using b = a*; is crystal clear.

You could include a comment explaining that using value_type = int; is exactly the same thing as typedef int value_type; just in case the shitty teacher introduced typedef but not using. If the teacher introduced just using, or neither typedef or using, this incidental comment shouldn’t do much harm.

value_type* data_;
unsigned int size_;
unsigned int capacity_;

There doesn’t seem to be a good reason not to use member initializers here. Member initializers are one of those things that are really obvious. I mean, if you see:

struct foo
{
    int baz = 42;
    int qux = 69;
};

Even if you don’t know C++ all that well, it’s kinda obvious what those initializers mean.

unsigned int size_;
unsigned int capacity_;

You mentioned that you deliberately chose to use unsigned int rather than std::size_t, but never explained why. I assume because you think unsigned int is “dumber” than std::size_t… but I beg to disagree. The moment you do unsigned int, you are going to be peppered with questions like “why unsigned; why not just int? (why not unsigned long, etc. etc.)” which opens a whole can of worms.

By contrast, std::size_t is just… the type for sizes. Period. It’s what you get when you do sizeof. That doesn’t leave any further questions hanging. It’s a size? Then it’s a std::size_t.

vector()
{
    data_ = nullptr;
    size_ = 0;
    capacity_ = 0;
}

If you use member initializers, this is a good opportunity to do something like this:

constexpr vector() noexcept = default;

Now, I get that you have an aversion to decorators, but you don’t need to explain them in any great detail:

  • Q: “Why does it say constexpr?”
  • A: “Because you should always use constexpr, unless it won’t compile if you do. It should have been the default, but unfortunately they didn’t think of it until too late.”
  • Q: “What does it do? Do I need it?”
  • A: “It can speed up your program. It’s usually optional, so if you don’t want to use it, that’s fine.”

And for noexcept:

  • A: “When your function cannot possibly fail, you should mark it noexcept. It’s optional, but it helps both other programmers and the compiler understand that the function is safe to call; it can never fail. Note the constructor that allocates is not marked noexcept, because allocation can fail if you run out of memory.”

The point I’m getting at is that rather than avoiding complexity, you should use it as a teaching opportunity. Unless the only purpose of dumb::vector is avoiding work, it seems like a good idea to leverage it as an additional teaching tool.

But even if you don’t want to use the constexpr and the noexcept, the default is still a good idea.

// 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;
    }
}

I think you should throw these constructors out. This is getting a bit too clever for a dumb vector.

Also, you’re opening the door for some MASSIVE confusion when the student discovers that dumb::vector(1, 2) is not the same as dumb::vector{1, 2}.

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 shouldn’t take std::initializer_list by const&. It’s a view type; it’s meant to be trivial to copy.

Now, the way you copy the data is a bit of a mess, mixing up iterators and indices, incrementing within the loop and without, using pointers and array-like access. Pick a track and stick to it:

vector(std::initializer_list<value_type> il)
{
    // get the size
    size_ = il.size();

    // allocate the data
    data_ = new value_type[size_];

    // copy the data from the initializer list
    auto p_src = il.begin();
    auto p_end = il.end();

    auto p_dest = data_; // p_dest now points to the start of the allocated data space

    while (p_src != p_end)
    {
        *p_dest = *p_src;

        ++p_src;
        ++p_dest;
    }
}

The copy constructor is fine, but:

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;
}

You don’t check for self-assignment… and it matters here.

You also don’t illustrate good programming practices. A better solution would be to offer the strong exception guarantee… though of course, you don’t need to explicitly say that’s what you’re doing. Just explain that allocation can fail, so to be safe, you’re not deleting the old data until the new data is ready.

vector& operator=(const vector& other)
{
    // allocation can fail, so we allocate to a temporary variable, and make
    // sure everything succeeds before touching this's data members
    auto new_data = new value_type[other.size_];

    for (std::size_t i = 0; i < other.size_; ++i)
        new_data[i] = other.data_[i];

    // okay, we copied all the data from other into the temporary, so now
    // it's safe to delete the old data from this
    delete[] data_;

    // and now we put the new data into this's data members
    data_ = new_data;
    size_ = other.size_;

    return *this;
}

And, for free, you no longer need a self-assignment check.

// 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{};
}

You’re gonna need a resize function to make these work, but that’s handy in any case, because it’s an easily-understood pattern to resize a vector to a certain size, then fill it with a loop and operator[].

auto resize(std::size_t new_size)
{
    // allocation can fail, so we allocate to a temporary variable, and make
    // sure everything succeeds before touching this's data members
    auto new_data = new value_type[new_size];

    // blah blah explain here that we need to handle the case where the new
    // size is larger *and* the case where the new size is smaller
    //
    // if std::min() is verbotten, using a ternary expression is probably too
    // advanced, so you should use an if-else, with one branch for when the
    // new size is smaller - that's repetitive, but, meh, this is a dumb
    // class, after all
    auto num_to_copy = std::min(new_size, size_); // can we use std::min?

    for (std::size_t i = 0; i < num_to_copy; ++i)
        new_data[i] = data_[i];

    // okay, we copied all the data from this into the temporary, so now
    // it's safe to delete the old data from this
    delete[] data_;

    // and now we put the new data into this's data members
    data_ = new_data;
    size_ = new_size;
}

auto push_back(value_type const& v)
{
    resize(size_ + 1);
    data_[size_ - 1] = v;
}

auto pop_back()
{
    resize(size_ - 1);
}

You can decide whether it’s worth it to add the complexity of an if to test whether new_size == size_. I wouldn’t bother, considering what this is for.

// 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;
}

These functions aren’t in std::vector’s interface. And they’re not worth the complexity. Dump ’em.

// 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;
}

Dump this with prejudice.

// 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_;
}

If you’re going to do this, lean into it. Define aliases for iterator and const_iterator, and define both versions of both functions. Seriously, the amount of complexity that adds is so minimal, and the benefits of the learner making the mental connection between pointers and iterators is so worth it.

(I also think you should add const versions of data() and operator[].)

I would suggest adding three more functions to this interface:

  • at()
  • clear()
  • operator==

at() is useful for bounds-checking… something a newbie is very likely to want to do.

clear() is generally useful because some algorithms require occasionally discarding all data. Plus it allows reusing vectors easily.

operator<=> seems a bit much—it’s generally unnecessary (I don’t often see people wanting to order vectors), and it opens up WAY too many questions. But operator== is a neat demo function:

constexpr auto operator==(vector const& other) const noexcept -> bool
{
    // if the sizes are different, the vectors can't possibly be equal
    if (size_ != other.size_)
        return false;

    // go through both vectors' data arrays, and if there are any mismatches,
    // then the vectors aren't equal
    for (std::size_t i = 0; i < _size ++i)
    {
        if (data_[i] != other.data_[i])
            return false;
    }

    // the sizes are the same, and all the elements match, so these vectors
    // are equal
    return true;
}

And that’s about it. Everything that applies to dumb::vector also applies to dumbestvector.

\$\endgroup\$
2
  • \$\begingroup\$ Appreciate the review. Very long, so it must be good. I'm just curious how this answer got several upvotes in only two days. Did this question show up on hot network or did you post it to your blog or something? \$\endgroup\$ Jan 24, 2021 at 14:44
  • \$\begingroup\$ 🤷🏼 I don’t think I did anything special. I don’t really pay much attention to votes anyway. \$\endgroup\$
    – indi
    Jan 24, 2021 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.