5
\$\begingroup\$

I'm implementing a STL-like vector with the essential functionalities.

I would like to know what is good in this code and what is bad. In terms of everything (memory usage, functions implementations, naming conventions, etc,...).

The header:

#ifndef BVECTOR_H
#define BVECTOR_H

#include <memory>

static const int MIN_CAPACITY = 16;
static const int GROWTH_FACTOR = 2;
static const int SHRINK_FACTOR = 4;

class BVector
{
public:
    BVector() = delete;
    BVector(int);
    BVector(int, int);
    //BVector(const BVector&); //Copy Constructor
    //BVector(const BVector&&); //Move Constructor

    //BVector& operator=(BVector&); //Copy assignment operator.
    //BVector& operator=(BVector&&); //Move assignment operator.

    ~BVector() = default;

    int const& operator[] (int) const;
    int& operator[](int);
    int at(int);

    void push(int);
    int pop();
    void insert(int, int);
    void prepend(int);
    bool find(int);
    void Delete(int idx);

    int size() const;
    int capacity() const;
    void resize(int);
    bool isEmpty();


private:
    int m_size{0};
    int m_capacity{MIN_CAPACITY};

    std::unique_ptr<int[]> m_data;

    int DetermineCapacity(int);
    void IncreaseCapacity();
    void DecreaseCapacity();
};



#endif // BVECTOR_H

The implementation:

#include "bvector.h"
#include <iostream>

BVector::BVector(int capacity): m_size(0)
{
    int new_capacity = DetermineCapacity(capacity);
    m_data = std::unique_ptr<int[]>(new int[new_capacity]);
}

BVector::BVector(int capacity, int init_val)
{
    int new_capacity = DetermineCapacity(capacity);
    m_data = std::unique_ptr<int[]>(new int[new_capacity]);

    for(int i = 0; i < new_capacity; i++)
    {
        m_data[i] = init_val;
    }
}

int const& BVector::operator[](int idx) const
{
    return m_data[idx];
}

int& BVector::operator[](int idx)
{
    return m_data[idx];
}

int BVector::at(int idx)
{
    return m_data[idx];
}

void BVector::resize(int requiredSize)
{
    if(m_size < requiredSize)
    {
        if(m_size == m_capacity)
            IncreaseCapacity();
    }else if(m_size > requiredSize)
    {
        if(m_size < (m_capacity/SHRINK_FACTOR))
           DecreaseCapacity();
    }

}

int BVector::DetermineCapacity(int capacity)
{
    int actual_capacity = MIN_CAPACITY;

    while(capacity > (actual_capacity/GROWTH_FACTOR))
    {
        actual_capacity *= GROWTH_FACTOR;
    }

    return actual_capacity;
}

void BVector::IncreaseCapacity()
{
    int old_capacity = m_capacity;
    int new_capacity = DetermineCapacity(old_capacity);

    if(new_capacity != old_capacity)
    {
        std::unique_ptr<int[]> new_data = std::unique_ptr<int[]>(new int[new_capacity]);

        for(int i = 0; i < m_size; i++)
        {
            new_data[i] = m_data[i];
        }

        m_capacity = new_capacity;

        m_data = std::move(new_data);
    }
}

void BVector::DecreaseCapacity()
{
    int old_capacity = m_capacity;
    int new_capacity = old_capacity / 2;

    if(new_capacity < MIN_CAPACITY)
        new_capacity = MIN_CAPACITY;

    if(new_capacity != old_capacity)
    {
        std::unique_ptr<int[]> new_data = std::unique_ptr<int[]>(new int[new_capacity]);

        for(int i = 0; i < m_size; i++)
        {
            new_data[i] = m_data[i];
        }

        m_capacity = new_capacity;

        m_data = std::move(new_data);
    }
}

int BVector::capacity() const
{
    return this->m_capacity;
}

int BVector::size() const
{
    return this->m_size;
}

void BVector::push(int val)
{
    resize(m_size + 1);
    m_data[m_size] = val;
    ++m_size;
}

bool BVector::isEmpty()
{
    return (m_size == 0);
}

int BVector::pop()
{
    if(!this->isEmpty())
    {
        resize(m_size-1);
        int value = m_data[m_size];
        --m_size;
        return value;
    }else
    {
        std::cout << "Nothing to pop." << std::endl;
        exit(EXIT_FAILURE);
    }
}

void BVector::insert(int value, int idx)
{
    resize(m_size + 1);

    std::unique_ptr<int[]> newData  = std::unique_ptr<int[]>(new int[m_capacity]);

    for (int i = 0; i < m_size+1; i++)
    {
        if(i == idx)
        {
            newData[i] = value;
            newData[i+1] = m_data[i];
        }
        else if(i > idx)
        {
            newData[i+1] = m_data[i];
        }
        else
        {
            newData[i] = m_data[i];
        }
    }

    m_data = std::move(newData);

    ++m_size;
}

void BVector::prepend(int value)
{
    resize(m_size + 1);

    for(int i = m_size; i > 0; i--)
    {
        m_data[i] = m_data[i - 1];
    }

    m_data[0] = value;

    ++m_size;
}

bool BVector::find(int reqVal)
{
    for(auto i = 0; i < m_size; i++)
    {
        if(m_data[i] == reqVal)
            return true;
    }
    return false;
}

void BVector::Delete(int idx)
{
    resize(m_size - 1);

    for(int i = idx; i < m_size - 1; i++)
    {
        m_data[i] = m_data[i+1];
    }

    --m_size;
}

The usage:

#include <iostream>
#include "bvector.h"

int main()
{
    BVector vec(10);

    std::cout << vec[3] << std::endl;

    vec.push(10);
    vec.push(20);
    vec.push(30);
    vec.push(40);
    vec.push(50);
    vec.push(60);
    vec.push(70);
    vec.push(80);
    vec.push(90);
    vec.push(100);
    vec.push(110);
    vec.push(120);
    vec.push(130);
    vec.push(140);
    vec.push(150);
    vec.push(160);
    vec.push(170);
    vec.push(180);

    vec.insert(333, 8);

    vec.Delete(8);

    std::cout << vec[vec.size()-1] << std::endl;

    vec[vec.size()-1] = 555;

    std::cout << vec.at(vec.size()-1) << std::endl;

    vec.prepend(987);

    std::cout << vec.at(0) << std::endl;

    std::cout << vec.at(1) << std::endl;

    int x = vec.pop();

    std::cout << "Popped Value: " << x << std::endl;

    bool flg = vec.find(150);
    std::cout << flg << std::endl;


    return 0;
}

Any detailed notes is so much appreciated.

\$\endgroup\$
11
\$\begingroup\$

Your two constructors don't store a value into m_capacity, so if the initial capacity requested (passed in as a parameter) is larger than the default capacity you'll have things in an inconsistent state and likely run into problems later.

Is there a reason you're not using std::make_unique<int[]>, instead of allocating memory with new and constructing a unique_ptr from it?

at member functions in the standard containers will perform bounds checking. Your at does not.

Is there a particular reason you're exiting the program if you detect a problem, rather than throwing an exception?

DetermineCapacity can enter an infinite loop if the actual_capacity *= GROWTH_FACTOR calculation overflows.

IncreaseCapacity and DecreaseCapacity are almost identical. Their functionality can be placed into a common function to avoid the code duplication.

You don't need to use this-> in member functions like capacity and size.

In pop, you need to read the value to return before you shrink the array. Since your resizing can reallocate memory and copy the vector contents, this can result in your reading an invalid value.

Why is insert always doing a reallocation?

Delete does not validate its argument, which can lead to Undefined Behavior.

\$\endgroup\$
8
\$\begingroup\$

Several of the public member names differ needlessly from those of the standard containers. That can prevent use of this class in generic code.

For instance,

void push(int);
int pop();
void prepend(int);
bool isEmpty();

I would have expected:

void push_back(int);
void pop_back();
void push_front(int);
bool empty() const;

These ones, dealing with size and capacity, should normally use std::size_t rather than int:

int size() const;
int capacity() const;
void resize(int);

It's also worth providing the standard type definitions that generic code expects of a container (value_type, size_type, etc).

We really, really need iterators for the collection. Then we wouldn't need find() to be a member, because std::find() does that job. insert() and erase() also normally accept iterators rather than indices.

There's lots of unnecessary loops where standard algorithms could and should be used (std::fill() and std::move() in particular).

I don't see why capacity calculation needs a loop. Just add the headroom to the required capacity rather than iterating over a fixed sequence of sizes.

Libraries shouldn't write, especially to standard output (std::cerr is the appropriate place for error messages), and certainly shouldn't terminate the process (except perhaps if specifically built for debugging, with NDEBUG undefined).

\$\endgroup\$
3
\$\begingroup\$
static const int MIN_CAPACITY = 16;
static const int GROWTH_FACTOR = 2;
static const int SHRINK_FACTOR = 4;

Global const variables automatically get internal linkage, thus making the statics redundant.

Since you tagged your question , the preferred way is to use constexpr variables:

constexpr int MIN_CAPACITY = 16;
constexpr int GROWTH_FACTOR = 2;
constexpr int SHRINK_FACTOR = 4;

Also, all-capital words are usually for macros.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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