C++

带你深入理解STL之Set和Map

在上一篇博客中,讲到了STL中关于红黑树的实现,理解起来比较复杂,正所谓前人种树,后人乘凉,RBTree把树都种好了,接下来就该set和map这类关联式容器来“乘凉”了。

STL的set和map都是基于红黑树实现的,和stack和queue都是基于deque一样,它们仅仅是调用了RBTree提供的接口函数,然后进行外层封装即可。本篇博客理解起来比较轻松,set和map的源代码也不多,大家可以慢慢“品味”。另外,还会介绍multiset和multimap这两个容器,并给出它们的区别和应用等。还等什么呢?走吧,带你理解理解set和map吧!

带你深入理解STL之RBTree

最近一直忙于校招的笔试,STL的深入理解系列也耽搁了好几天,再加上!红黑树真的是超级超级难理解,超级超级复杂,参考了好多博客上的大神的理解才稍微明白一点,勉强入个门,下面请以一个菜鸟的角度跟着我一起学习STL的红黑树吧。

带你深入理解STL之Stack和Queue

上一篇博客,带你深入理解STL之Deque容器中详细介绍了deque容器的源码实现方式。结合前面介绍的两个容器vector和list,在使用的过程中,我们确实要知道在什么情况下需要选择恰当的容器来满足需求和提升效率。一般选择的准则有如下几条:

  • 如果需要随机访问一个容器,vector比list要好
  • 如果需要经常插入和删除操作的话,list比vector要好
  • 如果既要随机存取,又要关心两端数据的插入和删除,则选择deque

好了,复习完前面的知识后,开始介绍今天的两个容器stack和queue。由于stack和queue都是基于deque来实现的,所以相应的代码会比较简单,也是比较轻松易实现的,下面一起去看看吧。

带你深入理解STL之Deque容器

在介绍STL的deque的容器之前,我们先来总结一下vector和list的优缺点。vector在内存中是分配一段连续的内存空间进行存储,其迭代器采用原生指针即可,因此其支持随机访问和存储,支持下标操作符,节省空间。但是其在分配的内存不够的情况下,需要对容器整体进行重新分配、拷贝和释放等操作,而且在vector中间插入或删除元素效率很低。

而list是以节点形式来存放数据,使用的是非连续的内存空间来存放数据,因此,在其内部插入和删除元素的时间复杂度都是O(1),但是其不支持随机访问和存取,不支持下标,而且比vector占用的内存要多。

综合上述的优缺点,我们貌似需要一个支持随机访问和存取,支持下标访问,而且插入和删除的效率高的容器。于是,STL的deque诞生了,下面就跟着我一起去看看deque的设计和源码实现吧!

带你深入理解STL之List容器

上一篇博客中介绍的vector和数组类似,它拥有一段连续的内存空间,并且起始地址不变,很好的支持了随机存取,但由于是连续空间,所以在中间进行插入、删除等操作时都造成了内存块的拷贝和移动,另外在内存空间不足时还需要重新申请一块大内存来进行内存的拷贝。为了克服这些缺陷,STL定义了另一种容器List,它对于数据插入和删除的时间复杂度均为O(1),而且再内存方面不用频繁的拷贝转移。下面,就一起来看看List的源码实现吧!

带你深入理解STL之Vector容器

C++内置了数组的类型,在使用数组的时候,必须指定数组的长度,一旦配置了就不能改变了,通常我们的做法是:尽量配置一个大的空间,以免不够用,这样做的缺点是比较浪费空间,预估空间不当会引起很多不便。

STL实现了一个Vector容器,该容器就是来改善数组的缺点。vector是一个动态空间,随着元素的加入,它的内部机制会自行扩充以容纳新元素。因此,vector的运用对于内存的合理利用与运用的灵活性有很大的帮助,再也不必因为害怕空间不足而一开始就配置一个大容量数组了,vector是用多少就分配多少。

要想实现动态分配数组,Vector内部就需要对空间控制做到有效率的掌控,这些机制要如何运作才能高效地实现动态分配呢?本篇博客就从源代码的角度带你领略一下Vector容器内部的构造艺术。

C/C++的mem函数和strcpy函数的区别和应用

mem系列函数是面试的时候常考的知识点,我们需要熟练掌握这三个函数的原理和代码实现,要能准确无误的写出代码。

memcpy、memset和memset三个函数在使用过程中,均需包含以下头文件:

//在C中
#include <string.h>
//在C++中
#include <cstring>

C++对象模型的那些事儿之六:成员函数调用方式

前言

C++的成员函数分为静态函数、非静态函数和虚函数三种,在本系列文章中,多处提到static和non-static不影响对象占用的内存,而虚函数需要引入虚指针,所以需要调整对象的内存布局。既然已经解决了数据,函数等在内存中的布局问题,下一个需要考虑的就是如何调用,上述提到的三种函数的调用机制都不一样,其间的差异正是本篇博客需要讨论的。

C++对象模型的那些事儿之四:拷贝构造函数

前言

对于一个没有实例化的空类,编译器不会给它默认生成任何函数,当实例化一个空类后,编译器会根据需要生成相应的函数。这类函数包括一下几个:

  • 构造函数
  • 拷贝构造函数
  • 析构函数
  • 赋值运算符

在上一篇博文C++对象模型的那些事儿之三:默认构造函数中讲到,编译器在需要的时候会合成一个空构造函数。本篇博文中就重点来介绍一下第二主角:拷贝构造函数。

C++对象模型的那些事儿之三:默认构造函数

前言

继前两篇总结了C++对象模型及其内存布局后,我们继续来探索一下C++对象的默认构造函数。对于C++的初学者来说,有如下两个误解:

  • 任何class如果没有定义default constructor,就会被合成出来
  • 编译器合成出来的default constructor会显示设定“class内每一个data member的默认值“

如果读者对这两句话理解颇深,了解里面的陷阱,那么可以不必阅读下去;倘若你有一点点疑惑,那非常好,跟着我一起继续下去!

C++对象模型的那些事儿之一:对象模型(上)

前言

很早以前就听人推荐了《深入理解C++对象模型》这本书,从年初买来到现在也只是偶尔翻了翻,总觉得晦涩难懂,放在实验室上吃灰吃了好久。近期由于找工作对C++的知识做了一个全面系统的学习,基础相对扎实了不少,于是,又重新拿起这本书,突然觉得里面的知识也不那么难懂,而且越看越有意思,不愧是C++高阶教程啊!耐着性子,抓着头皮花了两个多月,总算对其中的知识有了一些理解,部分章节反反复复的看,每次都有新的收获。所谓好记性不如烂笔头,本系列博文就对我所学到的知识和我所遇到的困惑做一个整理。