数据库索引

?
?

?
?
?

?
?
?

?

(二) C++容器

所谓序列式容器，其中的元素都可序（ordered），但未必有序（sorted）。数组为C++语言内置的序列容器，STL另外提供vector、list、deque（double-ended queue）。它们的差别在于访问元素的方式，以及添加或删除元素相关操作的运行代价。
标准库还提供了三种容器适配器（adapter），所谓适配器是根据原始的容器类型所提供的操作，通过定义新的操作接口，来适应基础的容器类型。顺序容器适配器包括stack、queue、priority_queue等序列式容器。其中stack和queue由于只是将deque改头换面而成，技术上被归类为一种配接器（adapter），priority_queue是有优先级管理的队列。
vector是标准C++建议替代C数组的动态数组模型，它维护的是一个连续线性空间。vector所采用的数据结构非常简单：线性连续空间。它以两个迭代器start和finish分别指向配置得到的连续空间中目前已被使用的范围，并以迭代器end_of_storage指向整块连续空间（含备用空间）的尾端。
vector的实现技术，关键在于其对大小的控制以及重新分配时的数据移动效率。一旦vector原有空间用完，如果客户端每新增一个元素，vector内部就只扩充一个元素的空间，实为不智。因为所谓扩充控件（不论多大），是“配置新空间（malloc）/拷贝移动数据（memcpy）/释放旧空间（free）”的大工程，时间成本很高，应该采用某种未雨绸缪的空间配置策略。注意，所谓动态增加大小，并不是在原空间之后接续新空间（因为无法保证之后尚有可供配置的空间），而是每次再分配原大小两倍的内存空间。因此，对vector的任何操作，一旦引起控件重新配置，指向原vector的所有迭代器就都失效了。
由于vector维护的是一个连续线性空间，因此vector迭代器具备普通指针的功能，支持随机存取，即vector提供的是Random Access Iterators。

相对于vector的连续线性空间，list就显得复杂许多，与向量(vector)相比, 它允许快速的插入和删除，且每次插入或删除一个元素，就配置或释放一个元素空间。因此，list对于空间的运用绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，list永远是常数时间。
list不再能够像vector那样以普通指针作为迭代器，因为其节点不保证在储存空间中连续存在。list迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取等操作。所谓“list迭代器正确的递增、递减、取值、成员取用”操作是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取用的是节点的成员。
list不仅是一个双向链表，而其还是一个环状双向链表。所以它只需要一个指针，便可以完整实现整个链表。由于list是一个双向链表（double linked-list），迭代器必须具备前移、后移的能力，所以list提供的是Bidirectional Iterators。
list有一个重要性质：插入操作（insert）和合并操作（splice）都不会造成原有的list迭代器失效。这在vector是不成立的，因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效。甚至list的元素删除操作（erase）也只有“指向被删除元素”的那个迭代器失效，其他迭代器不受任何影响。

vector是单向开口的连续线性空间，deque则是以中双向开口的连续线性空间。所谓双向开口，意思是可以在头尾两端分别做元素的插入和删除操作。从技术的角度而言，vector当然也可以在头尾两端进行操作，但是其头部操作效率奇差、令人无法接受。
deque和vector的最大差异，一在于deque允许于常数时间内对头端进行元素的插入或移除操作，二在于deque没有所谓容量（capacity）观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。换句话说，像vector那样“因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque中是不会发生的。也因此，deque没有必要提供所谓的空间预留（reserved）功能。
虽然deque也提供Random Access Iterator，但它的迭代器并不是普通指针，其复杂度和vector不可同日而语，这当然涉及到各个运算层面。因此，除非必要，我们应尽可能选择使用vector而非deque。对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector身上，将vector排序后（利用STL的sort算法），再复制回deque。
deque是由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量的连续空间，串接在整个deque的头端或尾端。deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置、复制、释放”的轮回，代价则是复杂的迭代器架构。

基于deque的顺序容器适配器stack、queue（priority_queue）
stack的基本概念：stack是一种后进先出（First In Last Out，FILO）的数据结构，它只有一个出口。stack允许新增元素、移除元素、取得最顶端元素。但除了最顶端外，没有任何其他方法可以存取stack的其他元素，换言之，stack不允许随机访问。
STL以deque作为stack的底层结构，对deque封闭期头端开口，稍作修改便形成了stack。将元素插入stack的操作称为push，将元素弹出stack的操作称为pop。stack所有元素的进出都必须符合“后进先出”的条件，只有stack顶端的元素，才有机会被外界取用。stack不提供走访功能，也不提供迭代器。

queue的基本概念：queue是一种先进先出（First In First Out，FIFO）的数据结构，它有两个出口。queue允许新增元素、移除元素、从最底端加入元素、取得最顶端元素。但除了最底端可以加入、最顶端可以取出，没有任何其他方法可以存取queue的其他元素。换言之，queue不支持随机访问。
STL以deque作为queue的底层结构，对deque封闭其底端的出口和前端的入口，稍作修改便形成了queue。

priority_queue的基本概念：priority_queue为优先级队列，它允许用户为队列中存储的元素设置优先级。这种队列不是直接将新元素放置在队列尾部，而是放置在比它优先级低的元素前面，即提供了一种插队策略。标准库默认使用<操作符来确定他们之间的优先级关系。即权重大的排在队首。使用priority_queue时，包含

关联式容器
所谓关联式容器，概念上类似关联式数据库（实际上则简单许多）：每项数据（元素）包含一个键值（key）和一个实值（value）。当元素被插入到关联式容器中时，容器内部数据结构（可能是RB-tree，也可能是hash-table）便依照其键值大小，以某种特定规则将这个元素放置于适当位置。关联式容器没有所谓头尾（只有最大元素和最小元素），所以不会有push_back()，push_front()，pop_back()，pop_front()，begin()，end()这样的操作。
一般而言，关联式容器的内部结构是一个balanced binary tree（平衡二叉树），以便获得良好的搜索效率。balanced binary tree有很多种类型，包括AVL-tree、RB-tree、AA-tree，其中广泛运用于STL的是RB-tree（红黑树）。
标准的STL关联式容器分为set（集合）和map（映射类）两大类，以及这两大类的衍生体multiset（多键集合）和multimap（多键映射表）。这些容器的底层机制均以RB-tree完成（红黑树）。RB-tree也是一个独立容器，但并不开放给外界使用。

此外，SGI STL还提供了一个不在标准规格之列的关联式容器：hash table(散列表，哈希表)，以及以此hash table为底层机制而完成的hash_set（散列集合）、hash_map（散列映射表）、hash_multiset（散列多键集合）、hash_multimap（散列多键映射表）。

(三) 内存管理

栈是机器系统提供的数据结构，计算机会在底层对栈提供支持；分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比堆的效率高一点。堆则是C/C++函数库提供的，它的机制比较复杂，比如分配一块内存，库函数会按照一定的算法，在堆内存中搜索可用的足够大小的空间。

(四) 野指针

(五) 智能指针
为什么要使用智能指针：我们知道c++的内存管理是让很多人头疼的事，当我们写一个new语句时，一般就会立即把delete语句直接也写了，但是我们不能避免程序还未执行到delete时就跳转了或者在函数中没有执行到最后的delete语句就返回了，如果我们不在每一个可能跳转或者返回的语句前释放资源，就会造成内存泄露。使用智能指针可以很大程度上的避免这个问题，因为智能指针就是一个类，当超出了类的作用域是，类会自动调用析构函数，析构函数会自动释放资源。下面我们逐个介绍。

(六) C++的特点：封装，继承，多态。
? 封装是指把数据和功能结合在一起，形成一个整体，也就是通常说的类。封装的目的是增强安全性和简化编程，使用者不必了解具体的实现细节，而只是要通过外部接口，一特定的访问权限来使用类的成员。我觉得名字空间也是一种封装
? 继承：扩展已经存在的代码，封装和继承都是为了代码重用。
? 多态：按字面意思就是多种形态，也就是一种接口，多种方法，是为了接口重用。分为静态多态和动态多态。 动态多态是指不论传递过来的究竟是那个类的对象，函数都能够通过同一个接口调用到适应各自对象的实现方法。最常见的用法就是声明基类的指针，利用该指针指向任意一个子类对象，调用相应的虚函数，可以根据指向的子类的不同而实现不同的方法。如果没有使用虚函数的话，即没有利用C++多态性，则利用基类指针调用相应的函数的时候，将总被限制在基类函数本身，而无法调用到子类中被重写过的函数。因为没有多态性，函数调用的地址将是一定的，而固定的地址将始终调用到同一个函数，这就无法实现一个接口，多种方法的目的了。
(七) C++的命名空间：命名空间（namespace）是一种描述逻辑分组的机制，可以将按某些标准在逻辑上属于同一个集团的声明放在同一个命名空间中。原来C++标识符的作用域分成三级：代码块（{……}，如复合语句和函数体）、类和全局。现在，在类和全局之间，标准C++又添加了命名空间这一个作用域级别。命名空间可以是全局的，也可以位于另一个命名空间之中，但是不能位于类和代码块中。所以，在命名空间中声明的名称（标识符），默认具有外部链接特性（除非它引用了常量）。在所有命名空间之外，还存在一个全局命名空间，它对应于文件级的声明域。因此，在命名空间机制中，原来的全局变量，现在被认为位于全局命名空间中。标准C++库（不包括标准C库）中所包含的所有内容（包括常量、变量、结构、类和函数等）都被定义在命名空间std（standard标准）中了。
(八) STL的内存分配

(九) HTTP的返回状态

1. static的作用
2. const的作用
3. 类型转换符：

4. 构造函数的作用

5. linux开机启动.pull oneself by one’s bootstraps.从rom里读取BIOS硬件自检(power-on self-Test)启动顺序主引导记录grub/bootinit运行级别用户登录

6. linux常用命令
   ?文件命令ls,file,touch,mkdir,cat,more,less,head,tail,cp,mv,rm,rmdir,df,du,dd,tree,scp,gzip,bizp2,
   zip,tar,
   ? 文本处理：echo,sed,awk,cut,wc,split,paste,sort
   ? Shell基本工具：chsh,read,export,source,history,xargs,alias,expr
   ? type, which, whereis, find, locate, xargs,ps,ping,mount,tmux

用户点击鼠标后发生的事件顺序
?浏览器分析链接指向的URL?浏览器向DNS请求解析域名 ?DNS域名解析器解析出IP ?与服务器建立TCP连接 ?浏览器发出HTTP请求 ?服务器接收请求，把请求的文件发给浏览器 ?TCP连接释放 ?浏览器将文件的index.html进行解释

1、 FTP建立连接时采用两个并行的TCP连接，一个是控制连接21号端口，一个数据连接20号端口
计算机的核心是CPU，它承担了所有的计算任务。它就像一座工厂，时刻在运行。假定工厂的电力有限，一次只能供给一个车间使用。也就是说，一个车间开工的时候，其他车间都必须停工。背后的含义就是，单个CPU一次只能运行一个任务。
进程就好比工厂的车间，它代表CPU所能处理的单个任务。任一时刻，CPU总是运行一个进程，其他进程处于非运行状态。一个车间里，可以有很多工人。他们协同完成一个任务。
车间的空间是工人们共享的，比如许多房间是每个工人都可以进出的。这象征一个进程的内存空间是共享的，每个线程都可以使用这些共享内存。

可是，每间房间的大小不同，有些房间最多只能容纳一个人，比如厕所。里面有人的时候，其他人就不能进去了。这代表一个线程使用某些共享内存时，其他线程必须等它结束，才能使用这一块内存。可是，每间房间的大小不同，有些房间最多只能容纳一个人，比如厕所。里面有人的时候，其他人就不能进去了。这代表一个线程使用某些共享内存时，其他线程必须等它结束，才能使用这一块内存。

还有些房间，可以同时容纳n个人，比如厨房。也就是说，如果人数大于n，多出来的人只能在外面等着。这好比某些内存区域，只能供给固定数目的线程使用。这时的解决方法，就是在门口挂n把钥匙。进去的人就取一把钥匙，出来时再把钥匙挂回原处。后到的人发现钥匙架空了，就知道必须在门口排队等着了。这种做法叫做"信号量"（Semaphore），用来保证多个线程不会互相冲突。
不难看出，mutex是semaphore的一种特殊情况（n=1时）。也就是说，完全可以用后者替代前者。但是，因为mutex较为简单，且效率高，所以在必须保证资源独占的情况下，还是采用这种设计。
操作系统的设计，因此可以归结为三点：
（1）以多进程形式，允许多个任务同时运行；
（2）以多线程形式，允许单个任务分成不同的部分运行；
（3）提供协调机制，一方面防止进程之间和线程之间产生冲突，另一方面允许进程之间和线程之间共享资源。

数据库索引

标签：索引   and   之间   资源   有序   任务   队列   目的   his