ADT vector in C++

Question

I have created a vector ADT, and this is a brief code for all of you. I will further add some more methods in it.

Kindly review my below code:

#include <iostream> using namespace std; template <typename T> class Vector { T* data; int capacity; int size; public: Vector(int cap) { if (cap <= 0) { cout << "capacity is invalid\n"; } else { capacity = cap; size = 0; data = new T[capacity]; } } Vector(const Vector& ref) { capacity = ref.capacity; size = ref.size; data = new T[capacity]; for (int i = 0; i < size; i++) { data[i] = ref.data[i]; } } void resize(int newCap) { T* temp = new T[newCap]; int smallerCap = (capacity < newCap)?capacity : newCap; for (int i = 0; i < smallerCap; i++) { temp[i] = data[i]; } delete[]data; data = temp; capacity = newCap; temp = nullptr; } void insert(int index, const T& value) { if (index > size) { cout << "out of bounds\n"; return; } if (size == capacity) { cout << "resized\n"; resize(2 * capacity); } for (int i = size; i > index; i--) { data[i] = data[i - 1]; } data[index] = value; size++; } void pushBack(const T& value) { if (size == capacity) { resize(2 * capacity); } data[size++] = value; } void print()const { for (int i = 0; i < size; i++) { cout << data[i] << " "; } cout << '\n'; } ~Vector() { delete[]data; } }; int main() { Vector<int>vec{ 3 }; vec.insert(0, 1); vec.insert(1, 2); vec.insert(2, 3); vec.print(); } 

This code will explain how to dynamically use the vectors, and I have used visual studio as a compiler to test this code.

Answer 1

If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.

Since templates are generally defined in header files, the use of using namespace std; is really a poor choice since anyone who include the header will have it in their code without knowing it.

Report errors to std::cerr rather than std::cout.

Use std::size_t rather than int for the size and capacity. This is what all the standard library container classes use.

In C++, std::size_t is an unsigned integer type used to represent the size of objects in bytes.

std::size_t can store the maximum size of a theoretically possible object of any type (including array). A type whose size cannot be represented by std::size_t is ill-formed. On many platforms (an exception is systems with segmented addressing) std::size_t can safely store the value of any non-member pointer, in which case it is synonymous with std::uintptr_t.

Use iterators rather than indexes.

In C++, an iterator is an object that points to an element inside a container (like a vector, list, or set) and allows you to traverse the elements of that container. You can think of them as a generalization of pointers.

Answer 2

Global Scope

using namespace std; 

Do not use using-directives (or using-declaratives) at the global scope in header files. See Why is 'using namespace std;` considered bad practice?

Vector<T>::Vector(...)

 Vector(int cap) { if (cap <= 0) { cout << "capacity is invalid\n"; } else { capacity = cap; size = 0; data = new T[capacity]; } } 

Constructors should create a fully initialized object. If the object cannot be fully initialized, throw an exception. Simply printing to the user that the "capacity is invalid" doesn't prevent use of the Vector. If a zero or negative integer is provided as cap, none of Vectors data members are initialized but the Vector is still usable. When another method attempts to use these data members, you have a classic case of undefined behavior (use-before-initialization).

Prefer initialization to assignment in constructors.

Prefer in-class default member initializers over constructor member initializers when initializing with constant values.

Every constructor should initialize every data member, preferrably using default member initializers for constants or constructor member initializers for runtime values.

Declare single-argument constructors explicit. The explicit keyword blocks implicit conversion that could happen through conversion constructors (all constructors are converting constructors since C++11) and conversion operators. There are situations where you may want implicit conversions, but be careful with them.

Vector<T>::resize(int)

 void resize(int newCap) { T* temp = new T[newCap]; int smallerCap = (capacity < newCap)?capacity : newCap; for (int i = 0; i < smallerCap; i++) { temp[i] = data[i]; } delete[]data; data = temp; capacity = newCap; temp = nullptr; } 

Always uphold the invariants of your class. Your constructor establishes that negative and zero sized capacities were invalid. newCap is never validated, so resize(int) allows both.

If newCap is negative, there in an int-to-std::size_t implicit sign conversion. If the converted expression can result in a valid size, then you get a very large allocation. See the C++ standard for the exact conversion rules (Final C++14 Draft, Final C++23 Draft). Nothing from data is copied to temp because smallerCap is smaller than 0. data ends up just being a large chunk of memory. capacity gets set to newCap (a negative integer), with no conversion.

If newCap is zero, new T[0] will happily return a pointer to an allocated array with no elements. It's undefined behavior if you try to dereference whatever new T[0] returns. The copying of data to temp correctly does nothing. capacity is correctly set to 0.

If newCap is positive but less than capacity, the copy from data to temp correctly copies all of the initialized elements, but also pointlessly copies all of the elements from size to newCap.

If newCap is the same size as capacity, you do a bunch of unnecessary copying.

If newCap is greater than capacity, you don't grow the capacity at all. Instead, you just do a bunch of unnecessary copying to end up in its previous state.

In all of these scenarios, size is not updated. Anytime newCap is less than size and you allocate a new buffer, the size changes and needs to be updated.

Note - None of the warning levels below /Wall (MSVC defaults to /W3) will show an implicit signed conversion warning. You must explicitly enable warning C4365 (/w34365). This is similarly true for -Wall -Wextra for Clang and GCC. Clang will warn for signed-conversion with either -Weverything, -Wconversion or -Wsign-conversion. GCC does not have a -Weverything and its -Wconversion doesn't include sign-conversion. The only way to see the warning is to explicitly use -Wsign-conversion.

Use std::unique_ptr to transfer ownership when a pointer is needed.new T[newCap] returns a pointer to some chunk of unmanaged allocated memory. If something were to throw before ownership is transferred to data, who is responsible for cleaning up temp? If you take ownership of temp with a std::unique_ptr, the pointer to the array will be deleted when the std::unique_ptr goes out of scope if it isn't explicitly released before then. This is known as "Resource Acquisition Is Initialization" (RAII) or "Scope-Bound Resource Management" (SBRM).

 T* temp = new T[newCap]; // code that could potentially throw throws... // nothing owns temp, so all paths must manually clean up or temp leaks. delete[]data; data = temp; // transfers ownership if nothing throws auto temp = std::make_unique<T[]>(newCap) // code that could potentially throw throws... // unique_ptr owns temp and cleans up after itself when destructor is called delete[] data; data = temp.release(); // transfers ownership if nothing throws 

Consider the Principle of Least Astonishment. With a name like resize(), an expectation is that I can remove elements or add specific/defaulted elements depending on the size provided. After all, size is in the name. This is how std::vector<T>::resize() works. If I want to change the capacity of a std::vector<T>, I can call std::vector<T>::reserve(). Changing the capacity doesn't change the size, meaning the only allocation that happens is if the new capacity is larger. Shrinking the size and capacity is two operations (std::vector<T>::resize() + std::vector<T>::shrink_to_fit()). If you want to make it a single operation, that's fine. Just give it another name (reshape(int)?).

Vector<T>::insert(int)

 void insert(int index, T const& value) { if (index > size) { cout << "out of bounds\n"; return; } if (size == capacity) { cout << "resized\n"; resize(2 * capacity); } for (int i = size; i > index; i--) { data[i] = data[i - 1]; } data[index] = value; size++; } 

Don't do more work than you have to. An insert on the front would result in the existing elements being copied twice. Once on resize and once for the insertion. You should copy data[0..index], insert value, then copy data[index..size].

If you are going to bounds check, you should inform the caller when such bounds checks fail. You correctly check for index > size but you ignore that index can be negative, which is also out of range.

Vector<T>

Vector(const Vector& ref) {...} ~Vector() {...} 

If you define or delete any of the "Rule of Five" special member functions, then define, =default, or =delete them all.. You've provided a destructor and copy constructor, two of the special member functions covered by the rule of five. You should provide the remaining three (copy assignment operator, move constructor, move assignment operator).

Prefer allocating without initialization. Initializing T may be expensive and you only want to initialize each object T when necessary. Your implementation T must be default constructible.

• T* buffer = new T[N]; - Allocates a buffer anddefault initializes each element.
• T* buffer = new T[N](); - Allocates a buffer anddirect initializes each element.
• void* buffer = ::operator new(sizeof(T) * N) - Allocates a buffer with the requested size (in bytes) only. The buffer has the size to hold an array elements, but the buffer is completely uninitialized for T. Returns a void* pointing to the buffer. Use static_cast<T*> to cast from void* to T*.
• new (ptr) T(args...) - Constructs a value at a specific location in the buffer.

Objects created by new expressions persist until the pointer returned by the new expression is used in a matching delete expression.

Allocate - Deallocate

• new - delete
• new[] - delete[]
• ::operator new - ::operator delete

Construct - Destruct

• new (ptr) T(args...) - ptr->~T()

Edit - As indi mentions in the comments, once you are manually managing allocation and object lifetimes, you may as well support allocators. The default std::allocator wraps this specific functionality for you through allocate(), deallocate(), construct(), and destroy(). The latter two were deprecated in C++17 and removed in C++20 because std::allocator_traits provides the same functionality. std::allocator_traits is the suggested way to use allocators and provides the same functionality as above. With C++17, std::allocator_traits<Allocator>::destroy instead calls std::destroy_at which does the destruction. With C++20, std::allocator_traits<Allocator>::construct calls std::construct_at, which does the construction. Supporting allocators also comes with its own challenges, like resolving operations between containers that have different allocators.

Abstract Data Type

I have created a vector ADT

You've actually created a Concrete Data Type. Abstract data types define the operations that can be performed without specifying how they are implemented. Examples of ADTs in C++ include concepts (C++20) or a C++ class with only pure virtual methods.