苏州产品网站建设,做鞋子出口需要作网站吗,建设部网站的诚信平台,如何自己设计广告图以下内容为本人的烂笔头#xff0c;如需要转载#xff0c;请声明原文链接 微信公众号「ENG八戒」https://mp.weixin.qq.com/s/QWgA97TDMGBnwR4hKA7BwA 查表的消耗
某些场景下需要用到大量的 (string, X) 键值对来存储数据#xff0c;标准库提供了关联容器 std::map 来解决键…以下内容为本人的烂笔头如需要转载请声明原文链接 微信公众号「ENG八戒」https://mp.weixin.qq.com/s/QWgA97TDMGBnwR4hKA7BwA 查表的消耗
某些场景下需要用到大量的 (string, X) 键值对来存储数据标准库提供了关联容器 std::map 来解决键值对的存储需求。
由于 std::map 负责管理插入元素键值对的存储顺序访问元素时需要比较键比如 (string, X) 中的 string。键的比较依赖操作符 操作符的执行过程直接影响查表的效率也就影响访问效率。
std::map 内部数据结构采用红黑树假设 std::mapstd::string, int 中包含 N 个元素查找一个元素的最多比较次数等于树的高度。对于一个高度均衡的树平均高度可以认为是 log2(N)其中 N 是树中的元素数量。
可见元素数量比较少而且比较操作符 运算代价较小同时无法构造出良好的哈希函数的情况下std::map 是非常合适的容器。相反元素数量比较多同时如果能提供良好的哈希函数的情况下std::unordered_map 更合适一些。
如果想要提升键的比较效率可以尝试用 (const char *, X) 替换 (string, X)。针对 C 风格的字符串指针调用比较操作符 运算不会执行字典序比较所以执行速度更快容器占用空间也相对小。麻烦的是访问元素时需要自行确保其以正确的字典序方式进行比较。当然使用指针可能带来其他副作用如访问内存地址越界、泄漏、未初始化等等。
除了键对访问效率的限制之外键值对的值 X 如果比较占空间在复制时同样会拖慢效率。处理方法可以参考之前提到的策略指针、智能指针以及写时复制等等策略。 如果你对「写时复制」的概念不是很清楚可以查阅一下笔者之前的文章《C 代码性能空间之极限拉扯「COW」 真乃神助攻》本文末尾有跳转阅读链接。 侵入式列表
在对系统效率极为苛刻的条件下有的开发者需要实现更高效的自定义侵入式列表榨干最后一滴性能。标准库提供的容器链表虽然在空间和效率上已大为改善但是对性能的极致追求决定了特定场景的自定义链表还有发挥的空间。
比如 标准库提供的链表容器需要额外的内存开销来存储指向前后节点的信息。如果容器插入大量小对象会产生内存碎片对内存的利用率不足。 即使是最保守的内存分配和释放比如基本的插入和删除节点的动作仍然会占用 CPU 资源何况是频繁为节点分配和释放内存会大为拖慢链表容器的执行效率。
Intrusive lists侵入式列表是一种特殊的数据结构实现方式不同于传统的链表。它不要求列表负责分配和释放节点的存储空间而是要求用户自己管理被插入的节点存储空间
另外节点自身必须存储其在列表中的位置信息。比如双向侵入式列表节点结构中包含了指向前后节点的指针而单向侵入式列表节点结构中包含有一个指向下一个节点的指针。
这种列表被称为“侵入式”是因为存储在列表中节点对象的内部结构包含了列表的相关信息链接信息而且节点内存必须由用户管理不能像标准库提供的链表那样为每个节点单独分配内存。
下面来看看如何定义侵入式链表容器的节点
// 链表容器的链接信息结构
template typename T
struct IntrusiveListNodeBase
{T* prev;T* next;
};// 要插入链表的用户对象
struct UserObject
{IntrusiveListNodeBaseUserObject list_node;// 其它成员比如数据...
};由于插入容器列表的用户对象类型是可变的在设计链表容器的链接信息结构时需要传入可变的类型参数所以使用模板类。在 C 里结构体其实是特殊的类。
然后实现一个简单的侵入式链表容器同样使用模板类的形式。容器应该提供基本的接口供用户使用比如插入、查询、删除等
template typename T
class IntrusiveList
{
public:// 在链表前插入节点void push_front(T* item){auto node item-list_node;node.prev nullptr;node.next head_;if (head_)head_-list_node.prev item;head_ item;}// 擦除节点void erase(T* item){auto node item-list_node;if (node.prev)node.prev-list_node.next node.next;elsehead_ node.next;if (node.next)node.next-list_node.prev node.prev;// 清理节点指针防止悬挂指针node.prev nullptr;node.next nullptr;}// 查询列表当前节点数量int num_of_list(){T* head head_;int num 0;if (head nullptr) {return num;}num 1;while (head-list_node.next ! nullptr) { num;head head-list_node.next;}return num;}// ...private:T* head_ nullptr;
};最后看看链表的使用情况对列表插入多个节点和移除部分节点后查询剩余的节点数量
int main()
{UserObject obj1, obj2;IntrusiveListUserObject list;// 将对象插入列表list.push_front(obj1);list.push_front(obj2);// 将对象移出列表list.erase(obj1);// 查询列表当前节点数量std::cout there is list.num_of_list() elements std::endl;// ...return 0;
}用户负责分配和释放插入侵入式列表的对象资源上面的演示代码里插入列表的对象资源分配在栈内所以用户无须特意手动释放。而且插入节点的过程无需任何的复制拷贝删除节点的过程也无需释放任何资源所以再频繁的插入删除操作都是极快的
但是还是要提醒一下这种侵入式的链表容器不应该是首选的工具标准库提供的容器已经可以应付绝大部分的需求理应作为开发首选。现在绝大部分的生产环境并不依赖如此苛刻的精打细算过分开发反而是高昂的成本。 全文写到这里就结束了如果各位同学朋友有什么疑问欢迎联系我交流。另外八戒有自己的技术圈交流群如果读者朋友有兴趣入群交流技术问题欢迎联系我。下拉到文章底部有我的联系方式
最后非常感激各位朋友的点 「赞」 和点击 「在看」谢谢
