A STL-like vector implementation in C++

Question

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.

STL-like? Some parts of it are somewhat similar to a specific instantiation (std::vector<int>), but there are more differences. — Deduplicator
– Deduplicator, Commented Jun 20, 2019 at 17:52
If it's meant to be STL-like, I'd at least expect it to satisfy requirements of Container, be usable with algorithms, range-based for, etc... The interface should similar too, there are many odd names in your case. — Dan Mašek
– Dan Mašek, Commented Jun 20, 2019 at 23:44
A good read for sobody implementing the vector. I wrote four articles on how to do it. Vector - Resource Management Allocation Vector - Resource Management Copy Swap Vector - Resize Vector - Simple Optimizations — Loki Astari
– Loki Astari, Commented Jun 26, 2019 at 17:35

1201ProgramAlarm · Accepted Answer · 2019-06-20 00:57:34Z

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.

Toby Speight · Accepted Answer · 2019-06-20 08:25:55Z

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).

L. F. · Accepted Answer · 2019-06-20 09:27:40Z

3

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 c++11, 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.

answered Jun 20, 2019 at 9:27

L. F.

9,7152 gold badges27 silver badges70 bronze badges

Add a comment |

Stack Exchange Network

A STL-like vector implementation in C++

3 Answers 3

You must log in to answer this question.

Hot Network Questions

A STL-like vector implementation in C++

3 Answers 3

You must log in to answer this question.

Related

Hot Network Questions