STL 和大多数其他容器在常见的操作中,例如 vector::resize(size_type n)
或 explicit vector::vector(size_type n)
,都会对新元素进行值初始化。
在一些对性能敏感的环境中,例如将 vector 用作文件或网络操作的可变大小缓冲区替代品时,值初始化的开销是不可忽略的,因为新元素添加到容器后不久就会被外部源覆盖。
Boost.Container 为 vector
、static_vector
和 stable_vector
提供了两个新成员:explicit container::container(size_type n, default_init_t)
和 container::resize(size_type n, default_init_t)
,其中新元素使用 默认初始化进行构造。
当填充关联容器时,如果用户保证要插入的输入范围根据谓词是有序的,则可以获得巨大的性能提升。这可能发生在将值从 set
插入到 multiset
时,或者在不同的关联容器族之间插入时([multi]set/map
与 flat_[multi]set/map
)。
Boost.Container 提供了一些构造函数和插入函数的重载,它们将 ordered_unique_range_t
或 ordered_range_t
标签参数作为第一个参数。当使用 ordered_unique_range_t
重载时,用户会通知容器输入范围根据容器谓词是有序的且没有重复项。当使用 ordered_range_t
重载时,用户会通知容器输入范围根据容器谓词是有序的,但可能包含重复项。借助这些信息,容器可以避免多次谓词调用并提高插入时间。
在第一个 C++ 标准中,list::size()
不要求是常数时间操作,这在 C++ 社区引起了一些争议。引用 Howard Hinnant 的 On List Size 文章:
关于
std::list<T>::size()
应该是 O(1) 还是 O(N) 存在相当大的争论。通常的论点是,这是以...为代价的:
splice(iterator position, list& x, iterator first, iterator last);
如果 size() 是 O(1),并且 this != &x,那么此方法必须执行线性操作,以便它可以调整每个 list 的 size 成员。
C++11 明确要求 size()
为 O(1),因此范围拼接变成了 O(N)。然而,Howard Hinnant 的文章提出了一个新的 splice
重载,以便即使是 O(1) 的 list:size()
实现,当调用者知道范围大小时,也能实现 O(1) 的范围拼接。
void splice(iterator position, list& x, iterator first, iterator last, size_type n);
效果:在 position 前插入范围
[first, last)
中的元素,并从 x 中移除这些元素。要求:
[first, last)
是 x 中的有效范围。如果 position 是范围[first, last)
中的一个迭代器,则结果是未定义的。仅使被拼接的元素相关的迭代器和引用失效。n == distance(first, last)
。抛出:无。
复杂度:常量时间。
这个新的 splice 签名允许客户端传入输入范围的距离。这些信息通常在调用处可用。如果传入,则操作是常数时间的,即使 size 是 O(1)。
Boost.Container 为 list
实现此重载,并为 slist
实现了一个修改版本(因为 slist::size()
也是 O(1)
)。