Boost C++ 库

这是世界上最受推崇、设计最精湛的 C++ 库项目之一。 Herb SutterAndrei Alexandrescu, C++ Coding Standards

扩展功能:基本扩展 - Boost C++ 函数库
PrevUpHomeNext

STL 和大多数其他容器在常见的操作中,例如 vector::resize(size_type n)explicit vector::vector(size_type n),都会对新元素进行值初始化。

在一些对性能敏感的环境中,例如将 vector 用作文件或网络操作的可变大小缓冲区替代品时,值初始化的开销是不可忽略的,因为新元素添加到容器后不久就会被外部源覆盖。

Boost.Containervectorstatic_vectorstable_vector 提供了两个新成员:explicit container::container(size_type n, default_init_t)container::resize(size_type n, default_init_t),其中新元素使用 默认初始化进行构造。

当填充关联容器时,如果用户保证要插入的输入范围根据谓词是有序的,则可以获得巨大的性能提升。这可能发生在将值从 set 插入到 multiset 时,或者在不同的关联容器族之间插入时([multi]set/mapflat_[multi]set/map)。

Boost.Container 提供了一些构造函数和插入函数的重载,它们将 ordered_unique_range_tordered_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.Containerlist 实现此重载,并为 slist 实现了一个修改版本(因为 slist::size() 也是 O(1))。


PrevUpHomeNext