C++的STL库提供了链表的基础类std::list，以前做程序设计竞赛的时候比较抵制使用std::list，最近做项目需要优化，不得不考虑使用list来提升效率。这里先简单的看看list的特性。 对于提升效率最终要的一点是list的元素在内存中地址是固定的，一旦申请了就不会再改变。下面进行简单的实验。 ~~~ #include<list> #include<iostream> using namespace std; int main() { list<int> objs; list<int>::iterator it; int i; long long a, b; for (i = 0; i < 10; i++) { objs.push_back(i); } for (it = objs.begin(); it != objs.end(); it++) { cout << *it << "'s address is " << &(*it) << "\n"; } for (it = objs.begin(), i = 0; it != objs.end();i++) { if (i % 2 == 0) { it = objs.erase(it); } else { it++; } } cout << endl; for (it = objs.begin(); it != objs.end(); it++) { cout << *it << "'s address is " << &(*it) << "\n"; } return 0; } ~~~ 上面的创建了一个有10个元素的链表，并打印出每个元素的地址，然后删除掉了其中为偶数的元素（此时list肯定有变化），但是重新遍历链表发现生于元素的地址和原来的地址是相同的，运行结果如下： ~~~txt 0's address is 0118FA70 1's address is 0118F9C8 2's address is 0118FB88 3's address is 0118FBC0 4's address is 0118FF08 5's address is 0118FC30 6's address is 0118FCD8 7's address is 0118FFE8 8's address is 0118F990 9's address is 0118FD10 1's address is 0118F9C8 3's address is 0118FBC0 5's address is 0118FC30 7's address is 0118FFE8 9's address is 0118FD10 ~~~ 我们都知道可随机访问的STL容器在预分配的内存满了之后，会重新整个对象移动到一个更大的内存区域，那么list会发生这种情况吗？下面用一个含有1000000个元素的程序进行测试，为了避免输出过多，我们稍微改变一下程序的行为，新的程序如下所示： ~~~ #include<list> #include<iostream> #include<vector> using namespace std; int main() { list<int> objs; list<int>::iterator it; int i; vector<long long> before, after; for (i = 0; i < 1000000; i++) { objs.push_back(i); } for (it = objs.begin(),i=0; it != objs.end(); it++,i++) { if (i % 2 == 1) { before.push_back(long long(&(*it))); } } for (it = objs.begin(), i = 0; it != objs.end();i++) { if (i % 2 == 0) { it = objs.erase(it); } else { it++; } } for (it = objs.begin(); it != objs.end(); it++) { after.push_back(long long(&(*it))); } if (before.size() != after.size()) { cout << "inconsistent" << endl; return 0; } for (i = 0; i < before.size(); i++) { if (before[i] != after[i]) { cout << "inconsistent" << endl; return 0; } } cout << "consistent" << endl; return 0; } ~~~ 输出结果是： ~~~txt consistent ~~~ 这说明我们的猜想是正确的。 * * * * * 用同样的代码对vector容器进行测试，代码如下： ~~~ #include<iostream> #include<vector> using namespace std; int main() { vector<int> objs; vector<int>::iterator it; int i; vector<long long> before, after; for (i = 0; i < 10; i++) { objs.push_back(i); } for (it = objs.begin(),i=0; it != objs.end(); it++,i++) { if (i % 2 == 1) { before.push_back(long long(&(*it))); } } for (it = objs.begin(), i = 0; it != objs.end();i++) { if (i % 2 == 0) { it = objs.erase(it); } else { it++; } } for (it = objs.begin(); it != objs.end(); it++) { after.push_back(long long(&(*it))); } if (before.size() != after.size()) { cout << "inconsistent" << endl; return 0; } for (i = 0; i < before.size(); i++) { if (before[i] != after[i]) { cout << "inconsistent" << endl; return 0; } } cout << "consistent" << endl; return 0; } ~~~ 得到的输出是： ~~~txt consistent ~~~