C++ 列表实现
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5136433/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C++ List Implementation
提问by UndefinedReference
So, I'm building an implementation of List for a programming exercise. So far I have this:
因此，我正在为编程练习构建 List 的实现。到目前为止，我有这个：
#include <iostream>
#include <algorithm>
using namespace std;
template <class T> class Link;
template <class T> class List_iterator;
template <class T>
class List
{
public:
typedef List_iterator<T> iterator;
List();
List(const List<T> & l);
~List();
bool empty() const;
unsigned int size() const;
T & back() const;
T & front() const;
void push_front(const T & x);
void push_back(const T & x);
void pop_front();
void pop_back();
iterator begin() const;
iterator end() const;
void insert(iterator pos, const T & x);
void erase(iterator & pos);
List<T> & operator=(const List<T> & l);
protected:
Link<T> * first_link;
Link<T> * last_link;
unsigned int my_size;
};
template <class T>
List<T>::List()
{
first_link = 0;
last_link = 0;
my_size = 0;
}
template <class T>
List<T>::List(const List & l)
{
first_link = 0;
last_link = 0;
my_size = 0;
for (Link<T> * current = l.first_link; current != 0; current = current -> next_link)
push_back(current -> value);
}
template <class T>
typename List<T>::iterator List<T>::begin() const
{
return iterator(first_link);
}
template <class T>
class Link
{
private:
Link(const T & x): value(x), next_link(0), prev_link(0) {}//pg. 204
T value;
Link<T> * next_link;
Link<T> * prev_link;
friend class List<T>;
friend class List_iterator<T>;
};
template <class T> class List_iterator
{
public:
typedef List_iterator<T> iterator;
List_iterator(Link<T> * source_link): current_link(source_link) { }
List_iterator(): current_link(0) { }
List_iterator(List_iterator<T> * source_iterator): current_link(source_iterator.current_link) { }
T & operator*(); // dereferencing operator
iterator & operator=(const iterator & rhs);
bool operator==(const iterator & rhs) const;
bool operator!=(const iterator & rhs) const;
iterator & operator++();
iterator operator++(int);
iterator & operator--();
iterator operator--(int);
protected:
Link<T> * current_link;
friend class List<T>;
};
template <class T>
T & List_iterator<T>::operator*()
{
return current_link -> value;
}
template <class T>
List_iterator<T> & List_iterator<T>::operator++()
{
current_link = current_link -> next_link;
return *this;
}
template <class T>
void List<T>::push_back(const T & x)
{
link<T> * last_link = new link<T> (x);
if (empty())
first_link = last_link;
else
{
last_link->prev_link = last_link;
last_link->prev_link = last_link;
last_link = last_link;
}
}
template <class T>
typename List<T>::iterator List<T>::end() const
{
return iterator(last_link);
}
int main()
{
List<int> l;
l.push_back(44); // list = 44
l.push_back(33); // list = 44, 33
l.push_back(11); // list = 44, 33, 11
l.push_back(22); // list = 44, 33, 11, 22
List<int> m(l);
List<int>::iterator itr(m.begin());
while (itr != m.end()) {
cout << *itr << endl;
itr++;
}
}`
I'm having a lot of trouble with my push_back() function and I'm not quite sure what's wrong. Can anyone point out my errors?
我的 push_back() 函数遇到了很多麻烦，我不太确定出了什么问题。谁能指出我的错误？
Updated Code In Progress:
更新中的代码：
#include <iostream>
#include <algorithm>
using namespace std;
template <class T> class Link;
template <class T> class List_iterator;
template <class T>
class List
{
public:
typedef List_iterator<T> iterator;
List();
List(const List<T> & l);
~List();
bool empty() const;
unsigned int size() const;
T & back() const;
T & front() const;
void push_front(const T & x);
void push_back(const T & x);
void pop_front();
void pop_back();
iterator begin() const;
iterator end() const;
void insert(iterator pos, const T & x);
void erase(iterator & pos);
List<T> & operator=(const List<T> & l);
protected:
Link<T> * first_link;
Link<T> * last_link;
unsigned int my_size;
};
template <class T>
List<T>::List()
{
first_link = 0;
last_link = 0;
my_size = 0;
}
template <class T>
List<T>::List(const List & l)
{
first_link = 0;
last_link = 0;
my_size = 0;
for (Link<T> * current = l.first_link; current != 0; current = current -> next_link)
push_back(current -> value);
}
template <class T>
typename List<T>::iterator List<T>::begin() const
{
return iterator(first_link);
}
template <class T>
class Link
{
private:
Link(const T & x): value(x), next_link(0), prev_link(0) {}//pg. 204
T value;
Link<T> * next_link;
Link<T> * prev_link;
friend class List<T>;
friend class List_iterator<T>;
};
template <class T> class List_iterator//pg.207
{
public:
typedef List_iterator<T> iterator;
List_iterator(Link<T> * source_link): current_link(source_link) { }
List_iterator(): current_link(0) { }
List_iterator(List_iterator<T> * source_iterator): current_link(source_iterator.current_link) { }
T & operator*(); // dereferencing operator
iterator & operator=(const iterator & rhs);
bool operator==(const iterator & rhs) const;
bool operator!=(const iterator & rhs) const;
iterator & operator++();
iterator operator++(int);
iterator & operator--();
iterator operator--(int);
protected:
Link<T> * current_link;
friend class List<T>;
};
template <class T>
T & List_iterator<T>::operator*()
{
return current_link -> value;
}
template <class T>
List_iterator<T> & List_iterator<T>::operator++()
{
current_link = current_link -> next_link;
return *this;
}
template <class T>
void List<T>::push_back(const T & x)
{
Link<T> * new_link = new Link<T> (x);
if (first_link = 0)
first_link = last_link = new_link;
else
{
new_link->prev_link = last_link;
last_link->next_link = new_link;
last_link = new_link;
}
my_size++;
}
template <class T>
typename List<T>::iterator List<T>::end() const
{
return iterator(last_link);
}
template <class T>
List <T>::~List()
{
Link <T> * first = first_link;
while (first != 0)
{
Link <T> * next = first->next_link;
delete first;
first = next;
}
}
template<class T>
bool List_iterator<T>::operator==(const iterator & rhs) const
{
return ( this->current_link == rhs.current_link );
}
template <class T>
bool List_iterator<T>::operator!=(const iterator & rhs) const
{
return !( *this == rhs );
}
int main()
{
List<int> l;
l.push_back(44); // list = 44
l.push_back(33); // list = 44, 33
l.push_back(11); // list = 44, 33, 11
l.push_back(22); // list = 44, 33, 11, 22
List<int> m(l);
List<int>::iterator itr(m.begin());
while (itr != m.end()) {
cout << *itr << endl;
++itr;
}
}
采纳答案by Carlos
Mario's and Joe's answers are both valid (I would vote them up if I could).
马里奥和乔的答案都是有效的（如果可以的话，我会投票给他们）。
Issue 1
第 1 期
Assuming that what you posted is your ACTUAL code for push_back()then Link<T>has the wrong case.
假设您发布的是您的 ACTUAL 代码，push_back()然后Link<T>有错误的情况。
link<T> * last_link = new link<T> (x);
...should be:
...应该：
Link<T> * last_link = new Link<T> (x);
Doing this gets rid of error: expected primary-expression before ‘>' token(when compiled with g++)
这样做可以摆脱error: expected primary-expression before ‘>' token（当用 g++ 编译时）
Issue 2
第二期
An alternative to what Mario and Joe suggested, is to NOT hide your List<T>'s last_link. Use a temporary variable that does NOT have the same name as your class's data member. Change:
马里奥和乔建议的另一种选择是不要隐藏你List<T>的last_link. 使用与您的类的数据成员名称不同的临时变量。改变：
Link<T> * last_link = new Link<T> (x);
...to...
...到...
Link<T> * new_link = new Link<T> (x);
This will make your code clearer and you will be referencing the right node.
这将使您的代码更清晰，并且您将引用正确的节点。
Issue 3
第 3 期
Following the above steps should make two logic errors in push_back()evident. I'm willing to assist, but I'm sure you will see it.
按照以上步骤应该可以push_back()明显看出两个逻辑错误。我愿意提供帮助，但我相信你会看到的。
回答by Mario
The following line creates a local variable named last_linkinside push_back().
下面这行创建了一个名为last_linkinside的局部变量push_back()。
link<T> * last_link = new link<T> (x);
Referencing last_linkafter this will point to this local variable instead of the class member. You'll have to add this->in front of the class ones, e.g. this->last_link = last_link;.
last_link在此之后引用将指向这个局部变量而不是类成员。您必须this->在类前面添加，例如this->last_link = last_link;.
回答by Joe
You have a local variable that is the same as a member variable name. When you're using last_link you're using the one that you just created in the push_back function. You're also assigning last_link->prev_link twice. Then also assigning last_link = last_link. I'd either change the name of the local variable, or add this->in front of it.
您有一个与成员变量名称相同的局部变量。当您使用 last_link 时，您正在使用您刚刚在 push_back 函数中创建的那个。您还分配了 last_link->prev_link 两次。然后还分配last_link = last_link。我要么更改局部变量的名称，要么this->在它前面添加。
