I am trying to implement a custom Vector class and got stuck on implementing the erase method. The method takes an iterator pointing to the element to be removed, and should return an iterator following the removed element. Here is my attempted implementation of the erase method:
iterator erase(iterator pos) {
// TODO: Implement this function.
if (pos == end()) {
return end();
}
T* newElems = new T[cap];
for (iterator iter = begin(); iter != pos; iter++ ) {
newElems[*iter] = elems[*iter];
}
for (iterator iter = pos + 1; iter != end()-1; iter++) {
newElems[*iter] = elems[*iter+1];
}
delete[] elems;
elems = newElems;
return pos;
}
The Vector class is defined as following and I have implemented all other basic methods and functions.
#include <cstdio>
#include <iostream>
#include <stdexcept>
/**
* @brief A templated sequence container that encapsulates dynamic size arrays.
*/
template<typename T>
class Vector {
private:
T *elems; // an array of the elements stored in the Vector
std::size_t cap; // the current capacity of the array
std::size_t length; // the number of elements inside the Vector
static const std::size_t initialCapacity = 2;
/* If you want to add methods, add them below this line */
/* If you want to add methods, add them above this line */
public:
/**
* @brief Default Constructor.
*/
Vector() {
// TODO: Implement this function.
length = 0;
cap = initialCapacity;
elems = new T[cap];
}
/**
* @brief Copy Constructor.
* @param other The vector from which we should copy from.
*/
Vector(const Vector &other) {
// TODO: Implement this function.
elems = new T[other.cap];
cap = other.cap;
length = other.length;
for (int i = 0; i < other.length; i++) {
elems[i] = other.elems[i];
}
}
/**
* @brief Copy Assignment Operator.
* @param other The vector on the RHS of the assignment.
* @return A reference to the vector on the LHS.
*/
Vector &operator=(const Vector &other) {
// TODO: Implement this function.
this->elems = &other.elems;
this->cap =other.cap;
this->length = other.length;
}
/**
* @brief Destructor.
*/
~Vector() {
// TODO: Implement this function.
delete [] elems;
}
typedef T* iterator;
typedef const T* constIterator;
/**
* @brief Begin iterator.
* @return An iterator to the first element.
*/
iterator begin() {
// TODO: Implement this function.
return elems;
}
/**
* @brief End iterator.
* @return An iterator to one past the last element.
*/
iterator end() {
// TODO: Implement this function.
return elems + length;
}
/**
* @brief Const begin iterator. This is a const overloaded function.
* @return A const iterator to the first element.
*/
constIterator begin() const {
// TODO: Implement this function.
return constIterator(elems);
}
/**
* @brief Const end iterator. This is a const overloaded function.
* @return A const iterator to one past the last element.
*/
constIterator end() const {
// TODO: Implement this function.
return constIterator(elems+size());
}
/**
* @brief Gets the number of elements that the container has currently allocated space for.
* @return The number of elements that can be held in currently allocated storage.
*/
std::size_t capacity() const {
// TODO: Implement this function.
return this->cap;
}
/**
* @brief Gets the number of elements.
* @return The number of elements in the container.
*/
std::size_t size() const {
// TODO: Implement this function.
return this->length;
}
/**
* @brief Adds an element to the end.
* If there is no space to add an element, then the capacity of the vector is doubled..
* @param elem The element to be added.
*/
void pushBack(T elem) {
// TODO: Implement this function.
if (size() >= capacity()) {
reserve(2*capacity());
}
elems[size()] = elem;
length++;
}
/**
* @brief Removes the last element of the container.
* The capacity of the vector is unchanged.
* If there are no elements in the container, then do nothing.
*/
void popBack() {
// TODO: Implement this function.
if (size()!=0) {
--length;
}
}
/**
* @brief Increases the capacity of the container to a value greater or equal to new_cap.
* If new_cap is greater than the current capacity(), new storage is allocated,
* otherwise the method does nothing.
* @param new_cap new capacity of the container.
*/
void reserve(std::size_t new_cap) {
// TODO: Implement this function.
T* newElems = new T[new_cap];
int newSize = new_cap < length ? new_cap : length;
for (int i = 0; i < newSize; i++ ) {
newElems[i] = elems[i];
}
cap = new_cap;
delete[] elems;
elems = newElems;
}
/**
* @brief Overloaded array subscripting operator.
* @param pos The position of the element to access.
* @return A reference to the element at specified location pos.
* No bounds checking is performed.
*/
T &operator[](std::size_t pos) {
// TODO: Implement this function.
return elems[pos];
}
/**
* @brief Const overload of the overloaded array subscripting operator.
* @param pos The position of the element to access.
* @return A const reference to the element at specified location pos.
* No bounds checking is performed.
*/
const T &operator[](std::size_t pos) const {
// TODO: Implement this function.
return elems[pos];
}
/**
* @brief Access specified element with bounds checking.
* @param pos The position of the element to access.
* @return A reference to the element at specified location pos, with bounds checking.
* @throw std::out_of_range if pos >= the size of the vector.
*/
T &at(std::size_t pos) {
// TODO: Implement this function.
if (pos >= size()) {
throw std::out_of_range;
}
return elems[pos];
}
/**
* @brief Const overload to access specified element with bounds checking.
* @param pos The position of the element to access.
* @return A const reference to the element at specified location pos, with bounds checking.
* @throw std::out_of_range if pos >= the size of the vector.
*/
const T &at(std::size_t pos) const {
// TODO: Implement this function.
if (pos>=size()) {
throw std::out_of_range;
}
return const elems[pos];
}
/**
* @brief Checks whether the container is empty.
* @return true if the container is empty, false otherwise.
*/
bool empty() const {
// TODO: Implement this function.
if (size()==0) {
return true;
}
return false;
}
/**
* @brief Removes all elements from the container.
* Leaves the capacity of the vector unchanged.
*/
void clear() {
// TODO: Implement this function.
while (!empty()) {
this->popBack();
}
}
/**
* @brief Erases an element at pos.
* @param pos Iterator to the element to remove.
* @return Iterator following the last removed element.
* If the iterator pos refers to the last element, the end() iterator is returned.
*/
iterator erase(iterator pos) {
// TODO: Implement this function.
if (pos == end()) {
return end();
}
T* newElems = new T[cap];
for (iterator iter = begin(); iter != pos; iter++ ) {
newElems[*iter] = elems[*iter];
}
for (iterator iter = pos + 1; iter != end()-1; iter++) {
newElems[*iter] = elems[*iter+1];
}
delete[] elems;
elems = newElems;
return pos;
}
};
When I run the run the erase method in the following way:
// a2 = {2,3,25,42} currently
Vector<int>::iterator it = a2.begin();
a2.erase(it+1);
print(a2);
I get the following:
-842150451
-842150451
25
-842150451
I have no idea why this is happening and could really use a help. Thanks.
Your erase() code creates a new array. However, the returned iterator still points into the old array. If you really mean to allocate a new array you'll need to make the result point into that, e.g., using
pos = newElems + (pos - elems);
right before delete[]ing the old array.
Since your Vector has a capacity you really only need to move the trailing elements forward one position and adjust the end(). That avoids some work of copying elements and avoids allocating new memory entirely. The returned pos remains unchanged in that case: only the end() changes.
The obvious way to move the elements is to use std::copy():
std::copy(pos + 1, end(), pos);
The corresponding loop is easy to write, too:
for (++pos; pos != end(); ++pos) {
pos[-1] = pos;
}