好吧,所以我一直在研究一些書籍的例子和東西,並發現這個練習來實現STL列表的外觀。我以某種方式做了它,它有點作用,但我在實現中有一些主要缺陷。
最大的問題是我完全不知道如何讓我的List.end()迭代器按其應有的工作。
我想我會先展示代碼,然後試着告訴我的一些想法。
自定義STL列表實現問題
#ifndef TESTS_LST_H
#define TESTS_LST_H
#include <memory>
#include <cstddef>
template<class T> class Node;
template<class T> class ListIter;
template<class T>
class List {
public:
typedef ListIter<T> iterator;
typedef const ListIter<T> const_iterator;
typedef std::size_t size_type;
List(): first(0), last(0), sz(0) {}
List(const List<T>& lst);
~List() { clear(); }
iterator begin() { return iterator(first); }
iterator end() { return iterator(last); }
iterator insert() {}
iterator erase() {}
const_iterator begin() const { return iterator(first); }
const_iterator end() const { return iterator(last); }
void push_back(const T& val);
void push_front(const T& val);
void clear();
void pop_front();
void pop_back();
size_type size() { return sz; }
bool empty() { return sz == 0; }
List& operator=(const List& l);
private:
Node<T>* first;
Node<T>* last;
size_type sz;
std::allocator<Node<T>>* alloc;
};
template<class T>
class Node {
public:
Node(): next(0), prev(0), value(0) {}
Node(const T& val): next(0), prev(0), value(val) {}
private:
Node<T>* next;
Node<T>* prev;
T value;
friend class List<T>;
friend class ListIter<T>;
};
template<class T>
class ListIter {
public:
typedef ListIter<T> iterator;
ListIter(Node<T>* iter): current_node(iter) {}
ListIter(): current_node(0) {}
ListIter(ListIter<T>* iter): current_node(iter->current_node) {}
inline T& operator*() { return current_node->value; }
iterator& operator=(const iterator& rhs) { *this->current_node = rhs.current_node; }
bool operator==(const iterator& rhs) { return current_node->value == rhs.current_node->value; }
bool operator!=(const iterator& rhs) { return current_node->value != rhs.current_node->value; }
iterator& operator++();
iterator operator++(int);
iterator& operator--();
iterator operator--(int);
private:
Node<T>* current_node;
friend class List<T>;
};
template<class T>
void List<T>::push_back(const T& val)
{
Node<T>* temp = alloc->allocate(1);
alloc->construct(temp, val);
if (first == 0) {
first = last = temp;
} else {
temp->prev = last;
last->next = temp;
last = temp;
}
sz++;
}
template<class T>
void List<T>::push_front(const T &val)
{
Node<T>* temp = alloc->allocate(1);
alloc->construct(temp, val);
if (first == 0) {
first = last = temp;
} else {
temp->prev = 0;
temp->next = first;
first->prev = temp;
first = temp;
}
sz++;
}
template<class T>
void List<T>::clear()
{
Node<T>* current = first;
while (current != 0) {
Node<T>* next = current->next;
//delete current
alloc->deallocate(current, 1);
alloc->destroy(current);
current = next;
}
first = last = 0;
sz = 0;
}
template<class T>
List<T>::List(const List &lst)
{
first = last = 0;
sz = 0;
for (auto it = lst.begin(); it != lst.end(); it++) {
push_back(it.current_node->value);
}
push_back(lst.last->value);
}
template<class T>
List<T>& List<T>::operator=(const List &lst)
{
first = last = 0;
sz = 0;
for (auto it = lst.begin(); it != lst.end(); ++it) {
push_back(it.current_node->value);
}
push_back(lst.last->value);
return *this;
}
template<class T>
void List<T>::pop_front()
{
first = first->next;
alloc->deallocate(first->prev, 1);
alloc->destroy(first->prev);
first->prev = 0;
sz--;
}
template<class T>
void List<T>::pop_back()
{
last = last->prev;
alloc->deallocate(last->next, 1);
alloc->destroy(last->next);
last->next = 0;
sz--;
}
template<class T>
ListIter<T>& ListIter<T>::operator++()
{
current_node = current_node->next;
return *this;
}
template<class T>
ListIter<T>& ListIter<T>::operator--()
{
current_node = current_node->prev;
return *this;
}
template<class T>
ListIter<T> ListIter<T>::operator++(int)
{
iterator tmp(*this);
++*this;
return tmp;
}
template<class T>
ListIter<T> ListIter<T>::operator--(int)
{
iterator tmp(*this);
--*this;
return tmp;
}
#endif //TESTS_LST_H
正如你可以看到.END()函數返回列表的常規最後一個元素,而不是一個過去的結束,因爲它應該。
我是否應該嘗試重寫此部分,以便可能將* last保留爲末尾迭代器的末尾,並使用operator +遍歷列表以省略指向實際列表末尾的指針? 像這樣的東西(不知道下面的代碼的corectness):
iterator& operator+(std::size_type n)
{
for (auto i = 0; i < n; ++i) {
++*this;
}
return *this;
}
但我不知道這是東西在實際執行中是如何工作的,循環可畢竟非常苛刻。
我知道這個東西已經在那裏工作,所有這一切。這只是爲了教育目的,所以我希望聽到一些想法。提前致謝。