根据 SGI、cplusplus.com 和我得到的所有其他来源,std::list 的 sort() 成员函数不应使迭代器无效。但是,当我运行这段代码 (c++11) 时,情况似乎并非如此:
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include "print.hpp"
unsigned int seed = std::chrono::system_clock::now().time_since_epoch().count();
std::default_random_engine generator(seed);
std::uniform_int_distribution<unsigned int> distribution(1, 1000000000);
auto rng = std::bind(distribution, generator);
// C++11 RNG stuff. Basically, rng() now gives some unsigned int [1, 1000000000]
int main() {
unsigned int values(0);
std::cin >> values; // Determine the size of the list
std::list<unsigned int> c;
for (unsigned int n(0); n < values; ++n) {
c.push_front(rng());
}
auto c0(c);
auto it(c.begin()), it0(c0.begin());
for (unsigned int n(0); n < 7; ++n) {
++it; // Offset these iterators so I can print 7 values
++it0;
}
std::cout << "With seed: " << seed << "\n";
std::cout << "Unsorted list: \n";
print(c.begin(), c.end()) << "\n";
print(c.begin(), it) << "\n\n";
auto t0 = std::chrono::steady_clock::now();
c0.sort();
auto d0 = std::chrono::steady_clock::now() - t0;
std::cout << "Sorted list: \n";
print(c0.begin(), c0.end()) << "\n";
print(c0.begin(), it0) << "\n"; // My own print function, given further below
std::cout << "Seconds: " << std::chrono::duration<double>(d0).count() << std::endl;
return 0;
}
在 print.hpp 中:
#include <iostream>
template<class InputIterator>
std::ostream& print(InputIterator begin, const InputIterator& end,
std::ostream& out = std::cout) {
bool first(true);
out << "{";
for (; begin != end; ++begin) {
if (first) {
out << (*begin);
first = false;
} else {
out << ", " << (*begin);
}
}
out << "}";
return out;
}
示例输入/输出:
11
With seed: 3454921017
Unsorted list:
{625860546, 672762972, 319409064, 8707580, 317964049, 762505303, 756270868, 249266563, 224065083, 843444019, 523600743}
{625860546, 672762972, 319409064, 8707580, 317964049, 762505303, 756270868}
Sorted list:
{8707580, 224065083, 249266563, 317964049, 319409064, 523600743, 625860546, 672762972, 756270868, 762505303, 843444019}
{8707580, 224065083}
Seconds: 2.7e-05
除打印外,一切都按预期工作。它应该显示 7 个元素,但实际数字相当随意,前提是“值”设置为大于 7。有时不给出,有时给出 1,有时给出 10,有时给出 7,等等。 那么,我的代码是否有明显的错误,或者这是否表明 g++ 的 std::list(和 std::forward_list)不符合标准?
提前致谢!
最佳答案
迭代器仍然有效并且仍然引用列表中的相同元素,已重新排序。
所以我认为您的代码并没有按照您的想法行事。它从头开始打印列表,直到列表排序后第 7 个元素结束。因此,它打印的元素数量当然取决于列表中的值。
考虑以下代码:
#include <list>
#include <iostream>
int main() {
std::list<int> l;
l.push_back(1);
l.push_back(0);
std::cout << (void*)(&*l.begin()) << "\n";
l.sort();
std::cout << (void*)(&*l.begin()) << "\n";
}
打印的两个地址不同,表明(不像std::sort
),std::list::sort
通过改变元素之间的链接进行了排序,而不是通过为元素分配新值。
我一直认为这是强制性的(对于 reverse()
也是如此)。我实际上找不到明确的文字来说明这一点,但是如果您查看 merge
的描述,并认为 list::sort
存在的原因是 < em>大概是 因为归并排序可以很好地处理列表,所以我认为这是“显然”有意的。 merge
说,“指针和对 x 的移动元素的引用现在指的是那些相同的元素,但作为 *this 的成员”(23.3.5.5./23),以及包括的部分的开头merge
和 sort
表示,“由于列表允许快速插入和从列表中间删除,因此专门为它们提供了某些操作”(23.3.5.5/1)。
关于c++ - g++ 的 std::list::sort 是否使迭代器无效?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13348070/