迭代器擦除 C++ 的自定义实现
custom implementation of iterator erase c++
我正在尝试实现自定义 Vector class，但在实现擦除方法时卡住了。该方法采用指向要删除的元素的迭代器，并且应该 return 一个迭代器跟在被删除的元素之后。这是我尝试实现的擦除方法：
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;
}
Vector class 定义如下，我已经实现了所有其他基本方法和功能。
#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;
}
};
当我运行 运行擦除方法如下：
// a2 = {2,3,25,42} currently
Vector<int>::iterator it = a2.begin();
a2.erase(it+1);
print(a2);
我得到以下信息：
-842150451
-842150451
25
-842150451
我不知道为什么会这样，真的需要帮助。
谢谢。
在 newElems[*iter] = elems[*iter]; 中，*iter 是 value，而不是 index。
您的 erase() 代码创建了一个新数组。但是，返回的迭代器仍然指向旧数组。如果您真的想分配一个新数组，则需要将结果指向该数组，例如，使用
pos = newElems + (pos - elems);
就在 delete[] 旧数组之前。
由于您的 Vector 有一个容量，您实际上只需要将尾部元素向前移动一个位置并调整 end()。这避免了一些复制元素的工作，并避免完全分配新内存。在这种情况下，返回的 pos 保持不变：只有 end() 发生变化。
移动元素的明显方法是使用 std::copy():
std::copy(pos + 1, end(), pos);
相应的循环也很容易写：
for (++pos; pos != end(); ++pos) {
pos[-1] = pos;
}
我正在尝试实现自定义 Vector class，但在实现擦除方法时卡住了。该方法采用指向要删除的元素的迭代器，并且应该 return 一个迭代器跟在被删除的元素之后。这是我尝试实现的擦除方法：
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;
}
Vector class 定义如下，我已经实现了所有其他基本方法和功能。
#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;
}
};
当我运行 运行擦除方法如下：
// a2 = {2,3,25,42} currently
Vector<int>::iterator it = a2.begin();
a2.erase(it+1);
print(a2);
我得到以下信息：
-842150451
-842150451
25
-842150451
我不知道为什么会这样，真的需要帮助。 谢谢。
在 newElems[*iter] = elems[*iter]; 中，*iter 是 value，而不是 index。
您的 erase() 代码创建了一个新数组。但是，返回的迭代器仍然指向旧数组。如果您真的想分配一个新数组，则需要将结果指向该数组，例如，使用
pos = newElems + (pos - elems);
就在 delete[] 旧数组之前。
由于您的 Vector 有一个容量，您实际上只需要将尾部元素向前移动一个位置并调整 end()。这避免了一些复制元素的工作，并避免完全分配新内存。在这种情况下，返回的 pos 保持不变：只有 end() 发生变化。
移动元素的明显方法是使用 std::copy():
std::copy(pos + 1, end(), pos);
相应的循环也很容易写：
for (++pos; pos != end(); ++pos) {
pos[-1] = pos;
}