双链表:迭代器/指针算法
双链表:迭代器/指针算法
提问于 2015-04-11 12:42:21
我使用了一个双链接列表容器作为工作示例。我使用的教科书是从2001年开始的，所以可以随意指出C++标准的后续版本应该在哪里使用。
备注：
List::iterator功能模仿指针算法。- 与大多数容器不同，列表开始由不包含数据的特定元素标记，以使反向迭代更容易：开始数据数据结束
- 取消引用
begin/end将遵从最近的数据元素，因此*begin= data@0 &*end= data@end-1。 List容器使用基本循环更优雅(参见main)。
list.h:
#ifndef GUARD_List_h
#define GUARD_List_h
template <class T>
struct element {
element<T> *prev = NULL;
element<T> *next = NULL;
T data = NULL;
int elem_ID = NULL;
char t_flag = NULL;
};
template <class T>
struct elem_iter {
elem_iter() { target = NULL; }
elem_iter(element<T>* e) { target = e; }
element<T>* target;
element<T>* elem_iter::operator++(void) {
if (target->next->t_flag == 'e'){
return NULL;
}
target = target->next;
return target;
}
element<T>* elem_iter::operator--(void){
if (target->prev->t_flag == 'b'){
return NULL;
}
target = target->prev;
return target;
}
T elem_iter::operator*(void){
if (target->t_flag == 'e'){
target = target->prev;
return target->data;
}
else if (target->t_flag == 'b'){
target = target->next;
return target->data;
}
return target->data;
}
bool elem_iter::operator!=(elem_iter& rhs){
return (rhs.target != this->target);
}
bool elem_iter::operator>=(elem_iter& rhs){
return (this->target->elem_ID >= rhs.target->elem_ID);
}
bool elem_iter::operator<=(elem_iter& rhs){
return (this->target->elem_ID <= rhs.target->elem_ID);
}
bool elem_iter::operator>(elem_iter& rhs){
return (this->target->elem_ID > rhs.target->elem_ID);
}
bool elem_iter::operator<(elem_iter& rhs){
return (this->target->elem_ID < rhs.target->elem_ID);
}
elem_iter elem_iter::operator+(int val){
for (int i = 0; i < val; i++){
this->target = this->target->next;
}
return *this;
}
elem_iter elem_iter::operator-(int val){
for (int i = 0; i < val; i++){
this->target = this->target->prev;
}
return *this;
}
};
template <typename T>
class List {
public:
List::List(void) {
element_count = 0;
// create begin
element<T>* b = new element <T>;
b->t_flag = 'b';
begins = b;
// create end
element<T>* e = new element <T>;
e->t_flag = 'e';
ends = e;
// double link: begins & ends
begins->next = ends;
ends->prev = begins;
element_count = 0;
}
typedef elem_iter<T> iterator;
iterator begin(void) {
iterator it(begins);
return it;
}
iterator end(void) {
iterator it(ends);
return it;
}
void push_back(T val) {
element<T>* elem = new element<T>; // create: new-elem
elem->data = val; // set data
elem->elem_ID = element_count++; // set ID
elem->prev = ends->prev; // link: new-elem to last-data-elem
ends->prev->next = elem; // link: last-data-elem to new-element
elem->next = ends; // link: new-elem to List-end
ends->prev = elem; // link: List-end to new-elem
ends->elem_ID = element_count; // update: ends-ID when List grows
}
T at(size_t pos) {
return get_element(pos)->data;
}
void del(size_t pos) {
element<T>* elem = get_element(pos); // get: element for deletion
elem->prev->next = elem->next; // rejoin: double link
elem->next->prev = elem->prev; // rejoin: double link
delete elem;
ends->elem_ID = (element_count--); // update: when List shrinks
}
void clear(void) {
element<T>* ep = begins->next;
element<T>* ep_next = ep->next;
while (ep->t_flag != 'e'){
delete ep;
ep = ep_next;
ep_next = ep->next;
}
begins->next = ends;
ends->prev = begins;
begins->data = NULL;
ends->elem_ID = NULL;
element_count = 0;
}
size_t size(void) const {
return element_count;
}
bool empty(void) const {
if (element_count == 0){ return true; }
else { return false; }
}
private:
element<T>* begins; // List begins
element<T>* ends; // List ends
size_t element_count; // List size
element<T>* get_element(size_t pos) {
if (empty()) {
std::cerr << "No Element - Empty List";
throw;
}
if (pos < 0 || pos >= element_count){
std::cerr << "No Element - Out of Range";
throw;
}
iterator it;
// Determine the more efficent iteration direction(forward or reverse) ?
if ((element_count / 2) > pos) {
it = begin();
for (size_t i = 0; i <= pos; i++){
it++;
}
}
else {
it = end();
for (size_t i = size() - pos; i > 0; i--){
it--;
}
}
return it.target;
}
};
#endif
typedef List<int> container;main.cpp:
#include <iostream>
#include <vector>
#include <list>
#include "list.h"
int main() {
container ls;
container::iterator begin = ls.begin();
container::iterator end = ls.end();
container::iterator iter = begin;
std::cout << "Attempt to retrieve data from empty list: ls.at(3)" << std::endl;
std::cout << "--------------------------------------------------" << std::endl;
//std::cout << ls.at(3) << std::endl << std::endl;
std::cout << "Test: growing list does not invalidate iter" << std::endl;
std::cout << "-------------------------------------------" << std::endl;
std::cout << "Empty list" << std::endl << std::endl;
std::cout << "begin addr: " << &begin << " " << std::endl;
std::cout << "begin t_flag: " << begin.target->t_flag << " " << std::endl;
std::cout << "end addr: " << &end << " " << std::endl;
std::cout << "end t_flag: " << end.target->t_flag << " " << std::endl;
std::cout << std::endl << "Add data to list: 33 " << std::endl << std::endl;
ls.push_back(33);
std::cout << "begin addr: " << &begin << " " << std::endl;
std::cout << "begin t_flag: " << begin.target->t_flag << " " << std::endl;
std::cout << "end addr: " << &end << " " << std::endl;
std::cout << "end t_flag: " << end.target->t_flag << " " << std::endl;
std::cout << std::endl << "Add data to list: 33 " << std::endl << std::endl;
ls.push_back(856);
std::cout << "begin addr: " << &begin << " " << std::endl;
std::cout << "begin t_flag: " << begin.target->t_flag << " " << std::endl;
std::cout << "end addr: " << &end << " " << std::endl;
std::cout << "end t_flag: " << end.target->t_flag << " " << std::endl << std::endl;
std::cout << "clear() " << std::endl << std::endl;
ls.clear();
std::cout << std::endl << std::endl;
std::cout << "Add data to list: 0 1 2 3 4 5 6 7 8 9" << std::endl;
std::cout << "-------------------------------------------------" << std::endl;
for (int i = 0; i != 10; i++){
ls.push_back(i);
}
std::cout << std::endl << std::endl;
std::cout << "data@ begin+4" << std::endl;
std::cout << "-------------" << std::endl;
std::cout << *(iter + 4) << std::endl;
std::cout << std::endl << std::endl;
std::cout << "data@ begin->end" << std::endl;
std::cout << "----------------" << std::endl;
iter = begin;
while (iter++){
std::cout << *iter << " ";
}
std::cout << std::endl << std::endl << std::endl;
std::cout << "data@ end->begin" << std::endl;
std::cout << "----------------" << std::endl;
iter = end;
while (iter--){
std::cout << *iter << " ";
}
std::cout << std::endl << std::endl << std::endl;
std::cout << "for/iter: begin->end" << std::endl;
std::cout << "----------------" << std::endl;
for (iter = begin; iter++;){
std::cout << *iter << " ";
}
std::cout << std::endl << std::endl << std::endl;
std::cout << "iter arith: +4 +1 -1" << std::endl;
std::cout << "--------------------" << std::endl;
iter = ls.begin();
iter = iter + 4;
std::cout << *iter << " ";
std::cout << *(iter + 1) << " ";
std::cout << *(iter - 1) << " ";
std::cout << std::endl << std::endl << std::endl;
std::cout << "data@: (0)(1)(2)(3)(4)(5)(6)(7)(8)(9)" << std::endl;
std::cout << "-------------------------------------" << std::endl;
for (int i = 0; i != 10; i++){
std::cout << ls.at(i) << " ";
}
ls.clear();
return 0;
}回答 1
Code Review用户
发布于 2015-04-11 18:14:01
这里有一些东西可以帮助你改进你的程序。你可以为自己做一件可以大大改善你的编程的事情，那就是买一本更新的书。自2001年以来，C++语言发生了很大变化，没有太多理由去学习过时的版本和坏习惯。
不要过度指定成员函数
在内联声明函数时，就像在elem_iter结构中一样，没有必要重复每个内联函数都是elem_iter的成员。所以，不是这样的：
T elem_iter::operator*(void){写这个：
T operator*(void){提供缺失的后缀操作符
iter++和++iter是有区别的。您的代码只定义了后一个版本，但尝试使用前者。
使用nullptr而不是NULL
现代C++使用的是nullptr而不是NULL。有关为什么和如何使用它，请参见这个答案。一旦您这样做了，您将看到您一直在滥用NULL，并将其用作整数和字符值，而不仅仅是指针。例如，在List::clear()中有以下内容：
begins->data = NULL;
ends->elem_ID = NULL;然而，data被定义为class T，elem_ID被定义为int。相反，将0分配给elem_ID，不要对data做任何事情。
改进构造函数
List类有三个数据元素：begins、ends和element_count。构造函数应该创建并初始化这三件事。构造函数的一种更现代的样式可能是：
List() : begins(new element<T>), ends(new element<T>), element_count(0) {
begins->t_flag = 'b';
ends->t_flag = 'e';
begins->next = begins->prev = ends;
ends->prev = ends->next = begins;
}使用构造函数而不是=来初始化成员数据
。
您的代码应该使用构造函数而不是=来初始化类中的数据。例如，element的构造函数可能如下：
element() : prev(nullptr), next(nullptr), data(), elem_ID(), t_flag(' ') {}这一点很重要，因为它适用于公共或私有数据，而=只适用于公共数据。
为类编写析构函数(
)
当对象被删除时，任何分配内存的类也必须释放它，但是类都缺少析构函数。为了让您开始，下面是List类的一个简单析构函数：
virtual ~List() {
while (begins->next != begins) {
begins->prev = begins->next;
begins->next = begins->next->next;
delete begins->prev;
}
delete begins;
}不需要
的#include头
这段代码包括<vector>和<list>，但实际上都没有使用。这些行应予删除。
使用一致的命名约定
选择一个命名约定并一致地使用它。在这段代码中，有些类是小写的，比如elem_iter，但List是大写的。一个常见的约定是对所有类和结构使用大写。
保存类数据和函数分离的
elem_iter类只有一个数据元素target，但是很难识别，因为它隐藏在许多函数中。最好是将所有数据项集合在一起，并将它们放在类的开头或结尾。
倾向于将数据成员保持为私有的
允许其他代码到达对象内部并获取或更改数据通常是错误的做法。因此，你所有的structs都应该是classes，只有一些成员功能应该是公开的。如果您有密切相关的类，则可以将它们声明为friend，以允许访问私有成员。例如，element的代码可能如下所示：
template <class T>
class List;
template <class T>
class elem_iter;
template <class T>
class element {
public:
element() : prev(nullptr), next(nullptr), data(), elem_ID(), t_flag(' ') {}
friend List<T>;
friend elem_iter<T>;
private:
element<T> *prev;
element<T> *next;
T data;
int elem_ID;
char t_flag;
};请注意，对于List和enum_iter有前向声明。
在实际的
中使用const
代码中的许多地方应该添加const关键字。例如，而不是这样：
bool operator!=(elem_iter& rhs){
return (rhs.target != this->target);
}写这个：
bool operator!=(const elem_iter& rhs) const {
return rhs.target != target;
}除了表示参数不被函数更改的const之外，我们在末尾还有一个const来指示操作符不改变对象。而且，this->target是多余的，return不是函数调用，因此不需要括号。
使用默认参数值，其中合理的
该代码当前有两个用于elem_iter的不同构造函数：
elem_iter() { target = NULL; }
elem_iter(element<T>* e) { target = e; }但是，可以将这些构造函数编写为一个单独的构造函数：
elem_iter(element<T>* e = nullptr) : target(e) {}考虑简化接口
我不清楚elem_ID字段是否真的有用，所以如果我正在编写这个字段，我想我会省略它和所有依赖它的函数。当然，这是您的选择，但通常情况下，一个更简单的接口可以使类更容易使用。
考虑非数值对象
现在，代码中的不同位置将类T限制为数值，或者至少可以初始化为0。通过一些明智的改写，这种人为的限制可以被消除。例如，创建一个List of std::string，您将看到我的意思。
省略return 0
当C++程序到达main的末尾时，编译器将自动生成返回0的代码，因此没有理由显式地将return 0;放在main的末尾。
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/86593
复制相关文章
相似问题
腾讯云开发者
