c++基础

C++11新特性

1.auto关键字。

# 2.nullptr关键字和std:nullptr类型。

# 3.基于范围的for循环 range-based for loops.

# 4.constexptr编译器常量类型。

# 5.模版别名：使用typedef为类型定义别名。C++11中可以使用using定义类型别名。

# 6.lambda表达式。

# 7.long long

# 8.列表初始化

# 9.decltype修饰符

# 10.标准库函数begin和end

STL容器之vector

一、什么是vector?

vector是一个能存放任意数据类型（类，结构，普通变量类型等）的动态数组！和普通数组一样可以通过下标索引来进行访问！在数据结构中就相当于顺序储存的线性表，寻找元素非常快，但是插入元素的时间却很大（list是一个双向链表，在同一个为止插入大量的数据时速度很快，但是查找的速度就会慢很多。与其它动态序列容器相比（deques,lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。

vector动态数组可以通过数组名进行直接赋值！

vector<string> c; 

vector<string> b;    b = c;

缺点：当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。（比普通的数组具有更高的时间复杂度和空间复杂度）

二、常用操作

2.1、增(定义、初始化)

2.2、删

（入参是指针变量（迭代器），比如begain(),end()），例如vec.erase(vec.begin()+2);删除第3个元素

2.3、改（插入）

2.4、查（遍历）

可以使用类似数组下标访问向量。

2.6、翻转与排序

2.7、二维向量

三、注意点

迭代器中删除元素的操作时：

对vector、queue等，每次erase操作，函数会删除指定迭代器位置的元素，然后将后面的元素前移一位，erase返回指向被删除元素下一元素的迭代器。（其实，我认为，返回的还是指定的迭代器，只不过它现在指向了被删除元素的下一元素，如有不对，恳请大家指正！）

    对于erase操作，还有一种写法是：Vec.erase(itVec++)

    不过需要注意，这种写法对vector、deque等容器无效！

上面两种写法，第一种对各种容器都有效，第二种写法只对map，list等容器有效。为了方便统一，还是建议采取第一种写法。

STL容器之set

一、什么是set?

set关联式容器。

set作为一个容器也是用来存储同一数据类型的数据类型，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一（集合内无重复相同的数据），而且系统能根据元素的值自动进行排序。

应该注意的是set中数元素的值不能直接被改变。

C++ STL中标准关联容器set,

multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。

关于set有下面几个问题：

（1）为何map和set的插入删除效率比用其他序列容器高？

不需要做内存拷贝和内存移动。说对了，确实如此。

set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。

（2）为何每次insert之后，以前保存的iterator不会失效？

iterator这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说，每一次删除和插入，指针都有可能失效，调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候，牢记这个原则：不要使用过期的iterator。

（3）当数据元素增多时，set的插入和搜索速度变化如何？

如果你知道log2的关系你应该就彻底了解这个答案。在set中查找是使用二分查找，也就是说，如果有16个元素，最多需要比较4次就能找到结果，有32个元素，最多比较5次。那么有10000个呢？最多比较的次数为log10000，最多为14次，如果是20000个元素呢？最多不过15次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了1次，多了1/14的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。

set使用方法：

二、常用操作

2.1、增(定义、初始化、新增数据)

2.2、删

set中的删除操作是不进行任何的错误检查的，比如定位器的是否合法等等，所以用的时候自己一定要注意。

2.3、查

2.4、改

三、注意点

注意begin() 和 end()函数是不检查set是否为空的，使用前最好使用empty()检验一下set是否为空.

count() 用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。

equal_range() ，返回一对定位器，分别表示第一个大于或等于给定关键值的元素和 第一个大于给定关键值的元素，这个返回值是一个pair类型，如果这一对迭代器中哪个返回失败，就会等于end()的值。

pair<set<int>::const_iterator,set<int>::const_iterator>pr; 

pr = s.equal_range(3);

cout<<"第一个大于等于 3 的数是 ："<<*pr.first<<endl; 

cout<<"第一个大于 3的数是 ： "<<*pr.second<<endl;

lower_bound(key_value) ，返回第一个大于等于key_value的迭代器

upper_bound(key_value)，返回最后一个大于等于key_value的迭代器