// 双向线性链表容器
#include <cstring>
#include <iostream>
#include <stdexcept>
using namespace std;
// 链表模板
template<typename T>
class List {
public:
// 构造、析构、拷贝构造、拷贝赋值
List (void) : m_head (NULL),
m_tail (NULL) {}
~List (void) {
clear ();
}
List (List const& that) : m_head (NULL),
m_tail (NULL) {
for (Node* node = that.m_head; node;
node = node->m_next)
push_back (node->m_data);
}
List& operator= (List const& that) {
if (&that != this) {
List list (that);
swap (m_head, list.m_head);
swap (m_tail, list.m_tail);
}
return *this;
}
// 获取首元素
T& front (void) {
if (empty ())
throw underflow_error ("链表下溢！");
return m_head->m_data;
}
T const& front (void) const {
return const_cast<List*> (
this)->front ();
}
// 向首部压入
void push_front (T const& data) {
m_head = new Node (data, NULL, m_head);
if (m_head->m_next)
m_head->m_next->m_prev = m_head;
else
m_tail = m_head;
}
// 从首部弹出
void pop_front (void) {
if (empty ())
throw underflow_error ("链表下溢！");
Node* next = m_head->m_next;
delete m_head;
m_head = next;
if (m_head)
m_head->m_prev = NULL;
else
m_tail = NULL;
}
// 获取尾元素
T& back (void) {
if (empty ())
throw underflow_error ("链表下溢！");
return m_tail->m_data;
}
T const& back (void) const {
return const_cast<List*> (
this)->back ();
}
// 向尾部压入
void push_back (T const& data) {
m_tail = new Node (data, m_tail);
if (m_tail->m_prev)
m_tail->m_prev->m_next = m_tail;
else
m_head = m_tail;
}
// 从尾部弹出
void pop_back (void) {
if (empty ())
throw underflow_error ("链表下溢！");
Node* prev = m_tail->m_prev;
delete m_tail;
m_tail = prev;
if (m_tail)
m_tail->m_next = NULL;
else
m_head = NULL;
}
// 删除所有匹配元素
void remove (T const& data) {
for (Node* node = m_head, *next; node;
node = next) {
next = node->m_next;
if (equal (node->m_data, data)) {
if (node->m_prev)
node->m_prev->m_next =
node->m_next;
else
m_head = node->m_next;
if (node->m_next)
node->m_next->m_prev =
node->m_prev;
else
m_tail = node->m_prev;
delete node;
}
}
}
// 清空
void clear (void) {
for (Node* next; m_head; m_head=next) {
next = m_head->m_next;
delete m_head;
}
m_tail = NULL;
}
// 判空
bool empty (void) const {
return ! m_head && ! m_tail;
}
// 大小
size_t size (void) const {
size_t cn = 0;
for (Node* node = m_head; node;
node = node->m_next)
++cn;
return cn;
}
// 输出
friend ostream& operator<< (ostream& os,
List const& list) {
for (Node* node = list.m_head; node;
node = node->m_next)
os << *node;
return os;
}
private:
// 节点模板
class Node {
public:
Node (T const& data, Node* prev = NULL,
Node* next = NULL) : m_data (data),
m_prev (prev), m_next (next) {}
friend ostream& operator<< (
ostream& os, Node const& node) {
return os << '(' << node.m_data
<< ')';
}
T m_data; // 数据
Node* m_prev; // 前指针
Node* m_next; // 后指针
};
// 判断相等函数的通用版本
bool equal (T const& a,
T const& b) const {
return a == b;
}
Node* m_head; // 头指针
Node* m_tail; // 尾指针
public:
// 正向迭代器
class Iterator {
public:
Iterator (Node* head = NULL,
Node* tail = NULL,
Node* node = NULL) : m_head (head),
m_tail (tail), m_node (node) {}
bool operator== (
Iterator const& rhs) const {
return m_node == rhs.m_node;
}
bool operator!= (
Iterator const& rhs) const {
return ! (*this == rhs);
}
Iterator& operator++ (void) {
if (m_node)
m_node = m_node->m_next;
else
m_node = m_head;
return *this;
}
Iterator const operator++ (int) {
Iterator old = *this;
++*this;
return old;
}
Iterator& operator-- (void) {
if (m_node)
m_node = m_node->m_prev;
else
m_node = m_tail;
return *this;
}
Iterator const operator-- (int) {
Iterator old = *this;
--*this;
return old;
}
T& operator* (void) const {
return m_node->m_data;
}
T* operator-> (void) const {
return &**this;
}
private:
Node* m_head;
Node* m_tail;
Node* m_node;
friend class List;
};
// 获取起始正向迭代器
Iterator begin (void) {
return Iterator (m_head, m_tail,
m_head);
}
// 获取终止正向迭代器
Iterator end (void) {
return Iterator (m_head, m_tail);
}
// 在正向迭代器之前插入
Iterator insert (Iterator loc,
T const& data) {
if (loc == end ()) {
push_back (data);
return Iterator (m_head, m_tail,
m_tail);
}
else {
Node* node = new Node (data,
loc.m_node->m_prev, loc.m_node);
if (node->m_prev)
node->m_prev->m_next = node;
else
m_head = node;
node->m_next->m_prev = node;
return Iterator (m_head, m_tail,
node);
}
}
// 删除正向迭代器的目标元素
Iterator erase (Iterator loc) {
if (loc == end ())
throw invalid_argument (
"无效参数！");
if (loc.m_node->m_prev)
loc.m_node->m_prev->m_next =
loc.m_node->m_next;
else
m_head = loc.m_node->m_next;
if (loc.m_node->m_next)
loc.m_node->m_next->m_prev =
loc.m_node->m_prev;
else
m_tail = loc.m_node->m_prev;
Node* next = loc.m_node->m_next;
delete loc.m_node;
return Iterator (m_head, m_tail, next);
}
// 常正向迭代器
// 反向迭代器
// 常反向迭代器
};
// 判断相等函数的特化版本
template<>
bool List<char const*>::equal (
char const* const& a,
char const* const& b) const {
return strcmp (a, b) == 0;
}
/*
int find (int* data, int size, int key) {
for (int i = 0; i < size; ++i)
if (data[i] == key)
return i;
return -1;
}
template<typename T>
int find (T* data, int size, T key) {
for (int i = 0; i < size; ++i)
if (data[i] == key)
return i;
return -1;
}
*/
template<typename IT, typename T>
IT find (IT begin, IT end, T key) {
for (IT it = begin; it != end; ++it)
if (*it == key)
return it;
return end;
}
// 测试用例
void test1 (void) {
List<int> list;
list.push_front (50);
list.push_front (40);
list.push_front (30);
list.push_front (20);
list.push_front (10);
cout << list << endl; // 10 20 30 40 50
list.pop_front ();
cout << list << endl; // 20 30 40 50
++list.front ();
cout << list << endl; // 21 30 40 50
//List<int> const& cr = list;
//cr.front () = 100;
list.push_back (60);
list.push_back (70);
list.push_back (80);
list.push_back (90);
cout << list << endl;
// 21 30 40 50 60 70 80 90
list.pop_back ();
cout << list << endl;
// 21 30 40 50 60 70 80
list.back () += 2;
cout << list << endl;
// 21 30 40 50 60 70 82
//List<int> const* cp = &list;
//cp->back ()--;
list.push_back (40);
list.push_back (40);
list.push_front (40);
list.push_front (40);
cout << list << endl; // 5个40
list.remove (40);
cout << list << endl; // 没有40
List<int> list2 = list; // 拷贝构造
cout << list2 << endl;
list2.pop_back ();
++list2.front ();
cout << list2 << endl;
cout << list << endl;
list2 = list; // 拷贝赋值
cout << list2 << endl;
list.pop_front ();
list.back ()--;
cout << list2 << endl;
cout << list << endl;
cout << list.size () << endl; // 5
cout << boolalpha << list.empty ()
<< endl; // false
list.clear ();
cout << list.empty () << endl; // true
cout << list.size () << endl; // 0
}
void test2 (void) {
char sa[][256] = {"beijing", "shanghai",
"tianjin", "shanghai", "chongqing"};
List<string> list;
for (size_t i = 0; i < sizeof (sa) /
sizeof (sa[0]); ++i)
list.push_back (sa[i]);
cout << list << endl;
list.remove ("shanghai");
cout << list << endl;
List<char const*> list2;
for (size_t i = 0; i < sizeof (sa) /
sizeof (sa[0]); ++i)
list2.push_back (sa[i]);
cout << list2 << endl;
list2.remove ("shanghai");
cout << list2 << endl;
}
void test3 (void) {
List<string> list;
list.push_ba
