这个双链表，是我模仿stl的list制作的，只实现了一些基本功能，像merge，transfer这些就没有实现，用户可以用基本操作来自己做外部实现。
我没有选用stl的[begin,end)迭代器模式，而是使用传统的[head,tail]。不过，为了配合stl算法，我还是加了两个begin()，end()方法，模拟了一下stl容器。模拟的还算及格，至少我可以做类似for (; begin != end; ++begin)这样的事，也可以让我的容器搭配一些stl算法，这在之后的demo里可以看到。不过，我的iterator很朴素，所以不能用于std::sort。
至于模拟的实现，我的方法是让所有越界的迭代器都指向一个预先设定好的内存地址。然后用户调用end()方法的时候，就返回指向这个内存地址的迭代器。这样，当我的迭代器越界的时候，就和end()指向的内存地址一样了。
代码采用C++11实现，在Win7 Mingw32 Gcc4.7的环境下，demo运行正常。如果发现写的不对的地方，还请回复一下。
以下是类的实现：
1 #pragma once 2 3 #include <cstddef> 4 #include <stdexcept> 5 6 namespace jt { 7 8 template <class value_t> 9 class list { 10 friend class list<value_t>; 11 12 private: 13 struct node { 14 value_t val; 15 node *next, *prev; 16 } *_head = nullptr, 17 *_tail = nullptr; 18 19 size_t _siz; 20 21 enum { endpointer = 1 }; 22 23 public: 24 class iterator { 25 friend class iterator; 26 friend class list<value_t>; 27 28 public: 29 iterator(node *nn = nullptr) { _init(nn); } 30 iterator(const iterator &i) { _init(i.n); } 31 32 value_t& operator*() const { return n->val; } 33 value_t* operator->() const { return &(operator*()); } 34 iterator operator++() { _inc(); return *this; } 35 iterator operator++(int) { iterator tmp = *this; _inc(); return tmp; } 36 iterator operator--() { _dec(); return *this; } 37 iterator operator--(int) { iterator tmp = *this; _dec(); return tmp; } 38 bool operator==(iterator& i) const { return i.n == n; } 39 bool operator!=(iterator& i) const { return i.n != n; } 40 41 private: 42 node *n; 43 44 void _init(node *nn) { 45 if (nn) { 46 n = nn; 47 } else { 48 n = (node*)endpointer; 49 } 50 } 51 52 void _inc() { n = (n->next) ? n->next : (node*)endpointer; } // increment 53 void _dec() { n = (n->prev) ? n->prev : (node*)endpointer; } // decrement 54 }; 55 56 list() { clear(); } 57 list(const list<value_t> &l) { if (&l != this) _init(l.begin(), l.end()); } 58 ~list() { clear(); } 59 60 bool empty() const { return !_head; } 61 62 void clear() { 63 if (!empty()) { 64 node *tmp; 65 for (node *n = _head; n; n = tmp) { 66 tmp = n->next; 67 delete n; 68 } 69 70 _head = nullptr; 71 _tail = nullptr; 72 _siz = 0; 73 } 74 } 75 76 void insert(const iterator &pos, const value_t &val) { 77 if (pos.n == _head) { 78 push_front(val); 79 } else { 80 node *n = new node; 81 n->val = val; 82 n->next = pos.n; 83 n->prev = pos.n->prev; 84 85 pos.n->prev->next = pos.n->prev = n; 86 ++_siz; 87 } 88 } 89 90 void erase(const iterator &pos) { 91 if (pos.n == _head) { 92 pop_front(); 93 } else if (pos.n == _tail) { 94 pop_back(); 95 } else { 96 pos.n->prev->next = pos.n->next; 97 pos.n->next->prev = pos.n->prev; 98 delete pos.n; 99 --_siz; 100 } 101 } 102 103 iterator head() const { return iterator(_head); } 104 iterator tail() const { return iterator(_tail); } 105 106 iterator begin() const { return iterator(_head); } 107 iterator end() const { return iterator((node*)endpointer); } 108 109 void push_front(const value_t &val) { 110 node *n = new node; 111 n->val = val; 112 n->next = _head; 113 n->prev = nullptr; 114 115 if (empty()) _tail = n; 116 else _head->prev = n; 117 _head = n; 118 119 ++_siz; 120 } 121 122 void push_back(const value_t &val) { 123 node *n = new node; 124 n->val = val; 125 n->next = nullptr; 126 n->prev = _tail; 127 128 if (empty()) _head = n; 129 else _tail->next = n; 130 _tail = n; 131 132 ++_siz; 133 } 134 135 void pop_front() { 136 if (_siz == 0) { 137 throw std::logic_error("Empty List"); 138 } else if (_siz == 1) { 139 clear(); 140 } else { 141 node *tmp = _head->next; 142 delete _head; 143 _head = tmp; 144 _head->prev = nullptr; 145 } 146 147 --_siz; 148 } 149 150 void pop_back() { 151 if (_siz == 0) { 152 throw std::logic_error("Empty List"); 153 } else if (_siz == 1) { 154 clear(); 155 } else { 156 node *tmp = _tail->prev; 157 delete _tail; 158 _tail = tmp; 159 _tail->next = nullptr; 160 } 161 162 --_siz; 163 } 164 165 value_t front() const { return *head(); } 166 value_t back() const { return *tail(); } 167 168 size_t size() const { return _siz; } 169 170 private: 171 template <class iter> 172 void _init(iter head, iter tail) { 173 clear(); 174 175 // copy 176 if (head && tail) { 177 for (; head != tail; ++head) { 178 push_back(*head); 179 } 180 push_back(*tail); 181 } 182 } 183 }; 184 185 }
我没有做测试，而是直接做了一个demo。
这个demo是一个正整数的统计计算器。可以插入，删除，求和，求平均数，等等。
以下是demo的代码，同样是C++11：
1 #include "list.h" 2 #include <iostream> 3 #include <string> 4 #include <cstring> 5 #include <cstdio> 6 #include <numeric> 7 #include <algorithm> 8 #include <map> 9 #include <functional> 10 11 int main() { 12 jt::list<unsigned> cont; 13 std::string buf; 14 std::string helpmsg = 15 "h for HELP\n" 16 "s for SUM\n" 17 "a for AVERAGE\n" 18 "z for SIZE\n" 19 "i,n,p for INSERT n AT p\n" 20 "e,n for ERASE AT p\n" 21 "p,n for PUSH_BACK n\n" 22 "q for QUIT"; 23 24 int n = -1; 25 int p = -1; 26 27 // create func 28 std::map<char, std::function<void()>> func; 29 func['h'] = [&]() { std::cout << helpmsg << std::endl; }; 30 func['s'] = [&]() { std::cout << "sum: " << std::accumulate(cont.begin(), cont.end(), 0) << std::endl; }; 31 func['a'] = [&]() { std::cout << "average: " << double(std::accumulate(cont.begin(), cont.end(), 0)) / cont.size() << std::endl; }; 32 func['z'] = [&]() { std::cout << "size: " << cont.size() << std::endl; }; 33 func['i'] = [&]() { 34 auto i = cont.begin(); 35 while (--p) ++i; 36 cont.insert(i, n); 37 }; 38 func['e'] = [&]() { 39 auto i = cont.begin(); 40 while (--n) { ++i; } 41 cont.erase(i); 42 }; 43 func['p'] = [&]() { cont.push_back(n); }; 44 func['q'] = [](){}; 45 46 char *optargs = "hsaziepq"; 47 48 while (buf != "q") { 49 // display 50 std::cout << "\n[ "; 51 std::for_each(cont.head(), cont.end(), [&](const unsigned &n) { std::cout << n << " "; }); 52 std::cout << "]" << std::endl; 53 54 // read in args 55 std::cout << optargs << "> "; 56 std::cin >> buf; 57 58 if (!strchr(optargs, buf[0])) { 59 std::cout << "Wrong Argument" << std::endl; 60 } else { 61 sscanf(buf.c_str(), "%*c,%d,%d", &n, &p); 62 func[buf[0]](); 63 } 64 } 65 66 return 0; 67 }
下面我使用demo的记录，看了可能会比较好理解代码一点：
[ ] hsaziepq> h h for HELP s for SUM a for AVERAGE z for SIZE i,n,p for INSERT n AT p e,n for ERASE AT p p,n for PUSH_BACK n q for QUIT [ ] hsaziepq> s sum: 0 [ ] hsaziepq> z size: 0 [ ] hsaziepq> p,1 [ 1 ] hsaziepq> p,5 [ 1 5 ] hsaziepq> p,9 [ 1 5 9 ] hsaziepq> a average: 5 [ 1 5 9 ] hsaziepq> s sum: 15 [ 1 5 9 ] hsaziepq> z size: 3 [ 1 5 9 ] hsaziepq> i,2,3 [ 1 5 2 9 ] hsaziepq> e,3 [ 1 5 9 ] hsaziepq> i,3,2 [ 1 3 5 9 ] hsaziepq> i,2,2 [ 1 2 3 5 9 ] hsaziepq> i,4,4 [ 1 2 3 4 5 9 ] hsaziepq> e,6 [ 1 2 3 4 5 ] hsaziepq> s sum: 15 [ 1 2 3 4 5 ] hsaziepq> a average: 3 [ 1 2 3 4 5 ] hsaziepq> z size: 5 [ 1 2 3 4 5 ] hsaziepq> q