在现代软件开发中，选择合适的数据结构对于程序的性能至关重要。在C++标准库中，有两个常用的容器：std::list和std::vector。尽管std::vector在很多情况下比std::list更快，但它们在迭代器行为上存在差异，这使得直接替换并不总是可行的。本文将探讨这两种容器的性能差异，并介绍一种新型容器mse::msevector，它结合了std::vector的高性能和std::list迭代器的稳定性。
std::vector是一个动态数组，提供了快速的随机访问能力，但在插入和删除操作时可能会因为内存重新分配而导致性能下降。相比之下，std::list是一个双向链表，提供了快速的插入和删除操作，但随机访问速度较慢。在现代硬件上，由于缓存一致性的原因，std::vector通常比std::list更快。
然而，std::vector的迭代器在插入或删除操作时可能会失效，这限制了其在某些场景下的使用。std::list的迭代器则不会因为这些操作而失效，但性能上不如std::vector。
mse::msevector是一种新型容器，它在保持std::vector高性能的同时，提供了类似于std::list迭代器的稳定性。mse::msevector的迭代器不会因为插入或删除操作而失效，这使得它在需要频繁插入和删除元素的场景下非常有用。
要使用mse::msevector，只需将mseprimitives.h和msemsevector.h两个文件复制到项目中即可。以下是使用mse::msevector的一个简单示例：
#include "msemsevector.h"
int main() {
mse::msevector v = {1, 2, 3, 4};
mse::msevector::ipointer ip1 = v.ibegin();
ip1 += 2;
assert(3 == (*ip1));
auto ip2 = v.ibegin();
v.erase(ip2);
assert(3 == (*ip1));
ip1--;
assert(2 == (*ip1));
for (mse::msevector::cipointer cip = v.cibegin(); v.ciend() != cip; cip++) {
v.insert(v.ibegin(), (*cip));
}
std::sort(v.ibegin(), v.iend());
std::sort(v.begin(), v.end());
}
mse::msevector与boost::container::stable_vector的比较非常有启发性。stable_vector通过避免在插入和删除操作中重新定位任何元素来保持迭代器的有效性。而mse::msevector则通过让迭代器主动跟随它们的目标元素来保持有效性。因此，mse::msevector通常比stable_vector更快，但在某些极端情况下，如果容器元素较少而指向它们的迭代器数量非常多，可能会影响mse::msevector的插入和删除操作性能。
以下是mse::msevector与std::vector、boost::stable_vector和std::deque的性能基准测试结果。测试环境为msvc2015/x64/Windows 7/Haswell。
| 操作 | std::vector | mse::msevector | mse::msevector (3 ipointers) | boost stable_vector | std::deque |
|---|---|---|---|---|---|
| push_back | 1.00 | 1.14 | 4.65 | 10.68 | 2.03 |
| insert | 1.00 | 1.02 | 1.01 | 13.77 | 5.19 |
| operator[] | 1.00 | 1.42 | 1.38 | 9.83 | 16.70 |