标签：STL

共 13 篇相关文章

IT 累计浏览 4,664

C++之stl::string写时拷贝导致的问题

这篇讲的是作者在实现数据结构序列化时，因滥用 `std::string` 作为缓冲区而踩到的一个隐蔽陷阱。具体来说，作者直接通过 `(char*)s.c_str()` 获取内部指针并使用 `fread` 写入数据，这在多数情况下看似高效且可行。然而，当代码中发生类似 `string s2 = s;` 的拷贝操作后，再对 `s2` 进行同样的 `fread` 操作，原本期望保持不变的 `s` 内容却意外被篡改了。问题的根源在于部分 STL 实现（如旧版 GCC）采用了“写时拷贝”（copy-on-write）机制来优化 `string` 的拷贝性能。此时，拷贝操作仅共享底层指针，而非进行深拷贝。这就导致通过强制类型转换修改共享内存区的数据时，所有持有该指针的 `string` 对象都会受到影响。文章清晰对比了“写时拷贝”与“立即拷贝”（eager-copy）两种策略的差异与适用场景，并指出该 bug 因其延迟显现的特性而极难定位。作者最终总结道，尽管将 `string` 作为临时缓冲区的写法在网络上屡见不鲜，但在“写时拷贝”的实现下，这种用法存在严重隐患。对于需要直接操作内存的场景，开发者应意识到 STL 容器的这些实现细节，或考虑使用更明确的缓冲区类型，以避免类似的陷阱。

IT 累计浏览 3,500

STL笔记之hashtable

这篇讲的是SGI STL中经典hashtable容器的源码实现。作者从自己动手实现一个简单hashtable的经历切入，发现与STL源码的思路惊人相似，由此展开对底层机制的剖析。文章深入讲解了SGI版本hashtable的核心设计：它采用开链法解决冲突，节点通过链表串联在bucket中。关键实现的巧妙之处体现在两处：一是迭代器逻辑，当前bucket遍历完毕后，能自动跳转到下一个非空bucket，保证了前向遍历的连贯性；二是容器容量的管理，预置了一张精心计算的素数表来动态选择桶的数量，这能有效降低哈希冲突概率，提升查找效率。通过拆解节点定义、迭代器操作符和容器初始化等关键源码，文章清晰地展现了hashtable从数据结构到算法选择的完整实现脉络，有助于读者真正理解这个高效容器背后的工程权衡与精巧构思。

IT 累计浏览 4,136

STL笔记之二叉查找树

这篇讲的是STL关联容器（如map和set）背后的核心数据结构——二叉查找树及其变体。作者从SGI STL的实现出发，系统梳理了三种关键树结构的区别与联系。文章首先剖析了基础的二叉查找树（BST），说明了它通过键值左小右大的规则实现对数时间操作，但也指出了其退化为链表导致效率骤降至O(N)的风险。为了解决平衡问题，文章对比了AVL树和红黑树：AVL树是严格的平衡树，任何节点的左右子树高度差不超过1，通过旋转保持平衡，保证了稳定的O(log n)性能；而红黑树通过着色规则和局部调整，在不过分追求严格平衡的前提下，同样实现了高效的查找与动态操作。最后，文章将理论落地，解释了为何红黑树凭借其在插入和删除场景下更少的旋转次数，成为SGI STL中map、set等容器的底层选择，而不只是理想中“更平衡”的AVL树。这种从原理到工程实现的脉络，对于理解标准库的设计哲学很有帮助。

IT 累计浏览 2,434

C++ 传参时传内置类型时用传值(pass by value)方式效率较高

这篇文章从《Effective C++》的经典条款出发，深入探讨了一个C++开发者常感困惑的问题：函数传参时，应该用传值（pass by value）还是传引用（pass by reference）？作者指出，这个选择并非一概而论，而是取决于参数的类型——文章特别对比了内置类型（如int、指针）与自定义类型之间的行为差异。为了验证这一结论，文章提供了清晰的代码示例和关键的汇编代码对比。核心发现在于：对于int这类内置类型，传值（`int f(int i)`）编译生成的x86汇编指令更简洁，参数直接通过寄存器传递，效率最高；而传常量引用（`int g(const int &i)`）则多了一次内存间接访问的步骤，尽管微小但在极热路径上可能产生影响。文章也点明了反向情况：当面对存在构造与析构开销的自定义类型时，传引用才能避免不必要的复制成本。此外，STL中的迭代器与函数对象本质上是指针，因此遵循内置类型的规则。作者通过这次代码级的验证，不仅重申了一个有效的实践准则，更通过底层视角加深了理解：效率的考量必须结合类型特性。这提醒我们，在追求代码“优雅”的同时，也不应忽视特定场景下符合硬件行为的朴素写法所带来的切实性能收益。

IT 累计浏览 6,527

萃取(traits)编程技术的介绍和应用

这篇讲的是C++中一项优雅而实用的泛型编程技巧——萃取（traits）技术。作者从STL中迭代器与算法解耦的需求出发，首先展示了一个核心矛盾：为了让统一的算法（如find）既能作用于自定义容器迭代器，又能兼容原生指针（如int*），我们需要一种机制来统一获取迭代器所指对象的类型信息。文章清晰地介绍了如何通过`iterator_traits`这个中间层，结合模版偏特化来解决这一问题，使`int*`这样的原生指针也能被正确萃取出`value_type`。接着，文章将这一思想从迭代器扩展到了更广阔的“类型萃取”领域。作者以SGI STL的`__type_traits`为例，说明了如何利用萃取技术探测类型特性（如是否有平凡的构造函数、析构函数）。通过为内置类型（如int）提供特化版本，算法（如copy）就能在运行时选择最高效的实现路径——比如直接进行内存拷贝而非调用复杂的构造函数，从而显著提升性能。文章从具体问题切入，逐步抽象出“特性萃取”的通用编程模式，最后落脚于其对C++泛型库性能优化的实际价值，展示了如何通过编译期的类型信息提取来弥补语言本身的局限。

IT 累计浏览 2,253

不得不留意的STL string重载函数和隐式类型转换

这篇讲的是STL `std::string` 构造函数的性能差异，作者从360云引擎团队的一篇深入剖析文章出发，通过实测数据揭示了几个容易忽视的关键点。文章在Linux GCC 4.1.2环境下，对多种`string`构造方式进行了万次循环计时。结果发现，利用拷贝构造函数`string(const string&)`最快，这得益于写时复制（COW）机制。而令人意外的是，最常用的`string(const char*)`构造方式耗时竟然最长，比其他需要分配内存的构造方式慢数倍。原因在于，若不预先提供字符串长度，构造函数内部必须先调用`strlen`遍历一次整个字符串以确定内存大小，而像`string(const char*, size_t)`这样直接给出长度的版本则省去了这步开销。这提醒开发者，在已知字符串长度的情况下，显式传递`size_t`参数能带来显著的性能提升。同样，需要复制`string`时，直接使用拷贝构造函数也是更高效的选择。

IT 累计浏览 2,910

STL可能的误用-find_first_of和erase

这篇技术文章聚焦于C++ STL中`string`的`find_first_of`函数常见的误用场景。作者从开发者容易混淆`find_first_of`与`find`的区别出发，点明了问题的根源：仅从名称相似性推断函数行为会导致逻辑错误。文章的核心在于澄清这两个函数的关键差异。`find_first_of`并非查找整个子串，而是在目标字符串中搜索参数字符串中任意一个字符首次出现的位置。相比之下，`find`用于查找整个子串。这种细微的语义差别，正是代码中隐蔽bug的来源。接着，文章深入讲解了与`erase`配合使用时可能出现的陷阱。例如，当意图删除找到的子串时，若误用`find_first_of`定位，后续计算起始索引和长度时就极易出错，导致非预期的删除范围。作者通过具体的代码示例，展示了这种误用可能引发的运行时错误或逻辑漏洞。通过剖析这些日常编码中可能忽略的细节，文章不仅指出了“病症”，更提供了明确的“解药”——准确理解每个STL函数的行为规范。对于经常处理字符串操作的C++开发者来说，这能帮助其写出更健壮、可维护的代码。

IT 累计浏览 9,497

在C++中实现foreach循环，比for_each更简洁！

这篇讲的是作者如何为C++实现一个更顺手的foreach循环。作者的出发点很直接：Python、C#、Java都有的简洁循环语法，C++虽然有STL的`std::for_each`，但用起来总觉得不够直观，于是动手自己写了一个。文章首先回顾了`std::for_each`这个“前辈”，它面向算法，是函数式的写法。而作者自己实现的目标，是追求像其他语言那样直接用`for(auto x : container)`一样的简洁感，让代码在遍历时一目了然。为了实现这一点，作者利用了C++的模板和自动类型推导（auto）特性，核心思路是让自定义的结构能够接收一个范围（比如容器），并正确地将元素类型传递给循环体。实现过程中的一个巧妙点在于对迭代器的抽象和封装，作者让这个自定义结构既支持数组，也支持各类STL容器，达到了通用的效果。最终得到的语法，确实比嵌套使用算法和lambda要清爽很多，更符合现代C++追求的清晰表达意图的风格。

IT 累计浏览 4,378

一个简单的stl中string的split函数

当Python开发者转向C++时，常常会怀念`split`这样的便捷函数——虽然STL功能强大，但并未直接提供这种常用的字符串分割操作。这篇文章正是从这个常见的“缺口”出发，展示了一个轻量级、实用的`split`函数实现。作者的思路很直接：利用`std::string`的`find`方法配合迭代器，高效地遍历字符串并定位分隔符。核心巧妙之处在于对边界情况的处理，比如连续分隔符和字符串首尾的分隔符，确保分割结果的准确性。实现代码短小精悍，没有复杂的模板元编程，却覆盖了大多数实际应用场景。这个方案避免了引入大型第三方库（如Boost），仅依赖STL标准组件，非常适合嵌入现有项目或用于教学示例。对于需要在C++中处理配置读取、日志解析或文本处理的开发者，这提供了一个即拿即用的参考实现。

IT 累计浏览 8,875

关于使用STL的红黑树map还是hashmap的问题

这篇讲的是作者在优化代理服务器URL重写功能时，面对的一个典型技术选型问题：在需要极高查询性能（约2万次/秒）的场景下，应该使用C++ STL的基于红黑树的map，还是hashmap。文章没有泛泛而谈理论，而是紧扣高并发下的实际性能需求展开。作者的核心关切点在于数据结构的性能表现。红黑树map能保证稳定的O(log n)查找，而hashmap在理想情况下能达到O(1)，但存在冲突风险和扩容时的性能波动。在URL映射这种对延迟极其敏感的场景中，两者各有需要权衡的微妙之处。文章的价值在于，它并非简单地给出“哪个更快”的结论，而是从实际的工程压力（单机高QPS）出发，引导读者思考如何结合具体场景（如URL分布特征、内存开销、查找稳定性要求）来做出最合适的选择。这种基于实战背景的对比分析，为面临类似数据结构决策的开发者提供了切实的参考。

IT 累计浏览 3,879

小趣闻:STL的三个版本

这篇讲的是C++标准模板库（STL）历史中一个有趣的小插曲：在成为C++标准之前，STL其实有三个“有名有姓”的版本。作者从STL的早期历史讲起，梳理了HP STL、SGI STL和STLport这三个在社区中流传较广、影响深远的版本。核心的差异点在于它们的出身、特性与应用场景。HP STL是最早的开源版本，由STL之父Alexander Stepanov和Meng Lee所在公司惠普发布，可以看作STL的“原始蓝图”。而SGI STL则是功能最为丰富、性能优异的版本，它不仅实现了标准，还加入了许多扩展，是许多编译器（如GCC早期版本）的底层选择。STLport则是为了跨平台兼容性而生的，旨在统一和规范不同平台上的STL实现。对于开发者而言，了解这段历史并非只是为了怀旧。这三个版本分别代表了STL发展的不同侧重点：HP STL适合研究STL的初衷与设计，SGI STL是学习其内部实现和精妙算法的宝库（其代码注释尤其详尽），而STLport则展示了如何在不同系统环境中保证一致性。如今虽然它们大多被整合进了主流编译器的标准库，但这份梳理能帮助我们理解当前所用工具背后的思想传承。

IT 累计浏览 4,303

string替换所有指定字符串（C++）

这篇讲的是如何在C++中实现字符串的全局替换功能。文章从标准库string自带的replace方法出发，点明了其局限性：它只能基于位置和长度进行替换，无法直接“找出所有指定子串并一一替换”。这其实是一个常见的编程需求缺口。作者的核心思路是手动遍历和构建新字符串。通过循环查找目标子串的位置，每次找到后将之前的部分和替换结果拼接，然后更新位置继续向后查找，直到遍历完整个字符串。这个过程中需要注意更新查找起始位置，以避免陷入死循环或跳过重叠部分。文章的价值在于它提供了一个清晰、可复用的实现模板，把看似繁琐的需求拆解成了几个关键步骤。对于经常处理文本解析或配置修改的C++开发者来说，这种手动实现的全局替换技巧，比依赖外部库更为轻便直接。

IT 累计浏览 3,304

闲谈STL容器之size()成员函数

这篇讲的是C++程序员几乎天天在用，却可能忽略其内部细节的STL容器`size()`成员函数。很多人想当然地认为这个返回元素个数的函数，时间复杂度一定是O(1)。但作者通过研读SGI STL源码发现，情况并非如此统一。文章以“知己知彼”为喻，指出在使用标准库时，了解其底层实现原理至关重要。作者逐一分析了`vector`、`list`和`deque`这三种常用容器。其中，`vector`的`size()`确实是常数时间O(1)，但`list`（双向链表）的`size()`实现却可能是线性时间O(n)，需要遍历链表来计算节点数；而`deque`的实现则依赖于其内部的分段数组结构。这种差异并非随意为之，而是源于容器不同的设计目标和数据结构特性。文章通过源码层面的对比，让读者看清：一个看似简单的接口背后，可能隐藏着完全不同的性能特征。这提醒开发者，在对性能有极致要求的场景下，选用容器时不能只看接口，还需深究其具体实现。