C++常用数据类型以及STL容器总结

C++ STL标准资源库

STL包括三个核心组件：

容器：管理某一个类型的集合
算法：作用于容器
迭代器：遍历容器的对象

C++基本数据类型

内置数据类型

类型	占用位（字节）
char	1
int	4
short	2
long	8 (16位机器是4)
long long	8
float	4
double	8
long double	16

typedef声明

格式typedef type newname
例如：

typedef int feet 表示feet是int的别名

定义struct的时候

struct TWO_NUMS{
    int a;
    int b;
};
//上述定义在之后进行实例创建的时候比如要如下引用
struct TWO_NUMS two_nums;
//但使用如下定义
struct TWO_NUMS{
    int a;
    int b;
} TwoNums;
TwoNums two_nums; //就可以如此引用

枚举类enum

enum color {red, blue, green} c;
则red = 0, blue = 1, green = 2
enum color {red, blue = 5, green} c;
red = 0, blue = 5, green = 6

C++ 存储类

auto: 声明变量时根据初始化表达式自动推断该变量的类型、声明函数时函数返回值的占位符。(C++11)
static: 指示编译器在程序的生命周期内保持局部变量的存在，而不需要在每次它进入和离开作用域时进行创建和销毁。static只在作用域内可见。在编译二进制文件中，static修饰的部分保存在静态内存段 1.修饰局部变量可以保持离开作用域时数据保持不销毁。2.修饰全局变量或全局函数 3.修饰类变量，各个对象共享一个static副本
extern: 提供一个全局变量的引用，全局变量对所有的程序文件都是可见的。extern 是用来在另一个文件中声明一个全局变量或函数。
thread_local: 变量仅可在它在其上创建的线程上访问。变量在创建线程时创建，并在销毁线程时销毁。

C++ 函数

传值调用：复制，并传入副本。对传入参数本身没有影响
指针调用：复制，传入指针（也就是传入地址）。在操作的过程中对地址解引用进行修改。也就是实际上是在内存上进行更改。会影响到传入参数的实际内容
引用调用：将参数的引用复制传给函数。会影响到传入参数的实际内容

lambda表达式

C++11对匿名函数的支持，广泛用于排序cmp等操作
[capture](parameters)->return-type{body}
例如：
[](int x, int y){ return x < y ; }
[](int x, int y) -> int { int z = x + y; return z + x; }
[]表示没有定义变量，使用未定义变量会报错
[x, &y]表示x传值调用，y为引用调用
[&]所有传入参数为引用调用
[=]所有传入参数为传值调用

C++ 数组

存储一个固定大小的相同类型元素的顺序集合。在内存上连续分布。可以实现O(1)操作访问。声明时必须确定arraySize。
type arrayName [ arraySize ];

多维数组

type name[size1][size2]...[sizeN];

指向数组的指针

double balance [10]; //balance本身是指向一个大小为10的double数组的头指针。
double *p;
p = balance;
*(p + 4);//是访问balance[4]的合法方式

向函数传递数组

传递数组头指针，对数组的操作会影响实际值。安全的保证不修改要使用const
传递数组形参。int param[]就是可以的，C++不会对形参的边界进行边界检查，但是如果不传param_size就有可能造成segament fault访问越界。也可以int param[10]。

函数返回数组

C++不允许返回一个完整的数组。只能返回一个数组头指针

int * getNums(){
    ...;
}

int main(){
    int *p;
    p = getNums();
    //这里就要注意我并不知道p的限度在哪里。而C++对内存越界操作并不直接检查，会产生隐形bug
}

C++字符串 c_str

char str[6] = {'h', 'e', 'l', 'l', 'o', '\0'}; 字符串是以null为终止的一维字符数组
char str[] = "hello";

c_str操作函数：

strcpy(s1, s2); 复制s2到s1，注意复制有可能越界
strcat(s1, s2); 连接s2到s1上
strlen(s1)
strcmp(s1, s2); 相同返回0，s1>s2返回positive，s1<s2返回negative
strchr(s1, ch); 返回ch在s1中第一次出现的位置
strstr(s1, s2); 返回s2在s1中第一次出现的位置（普通实现O(n^2), KMP实现O(n)）

C++指针

指针是一个变量，占用4个字节。他的值表示的是一个内存地址。
可以对指针进行的操作++， –， +， -。来移动指针内容在内存上表示的变量。但是注意指针本身所占用的4字节地址并不会变。

C++引用

不存在空引用，引用必须连接到一个合法的内存地址
一旦引用被初始化，就不能被指向另一个对象。
引用必须在创建时初始化。

顺序STL容器

array

具有固定大小，不支持添加或删除元素

#include <array>
template<
    class T,
    std::size_t N
> struct array;

内存分配策略：

局部变量在栈上分配（对比vector，vector底层实现是动态数组，局部变量在堆上分配）
使用new分配的话在堆上分配
全局变量或静态变量，在静态存储区分配

成员函数：

成员访问：
- at A.at(int)
- operator[] A[int]
- front A.front()
- back A.back()
- data A.data() 返回指向第一个元素的指针
迭代器：
- begin()
- end()
容量：
- empty()
- size()
- max_size() 返回可容纳的最大元素数
操作：
- fill()
- swap(array & other) 将容器内容与other内容进行交换

优势：

比数组安全，提供了越界检查
array::swap线性时间内容交换

vector

#include
底层数据结构是动态数组，管理连续内存空间。与array唯一的区别是对空间的运用上。对于超过现有vector大小的插入，vector容量2倍扩展。vector如果是空的话，也占用1个元素大小。

成员函数：保留array所有的function。增加的function：
* push_back(class T)
* pop_back()
* iterator insert(const_iterator position, const value_type& val) 注意会改变vector所有元素的标号，传入参数为iterator
* erase(const_iterator position) 同样会改变vector所有元素的标号
* clear()
* swap()

insert和erase会出现迭代器失效的问题

string

#include
只存储字符元素的vector.

成员函数：与vector相同。与vector不同的：

operator+= 表示在string后添加
c_str() 返回char* 类型
size_t copy(char* buf, size_t len, size_t pos = 0) const;
string substr(size_t pos = 0, size_t len = npos) const;
size_t find(const string& str, size_t pos = 0) const; 查找从pos后开始，str第一次出现的位置。还有rfind查找最后一次出现的位置

非成员函数支持：

operator+ 连接两个string
operator>> 从inputstream提取一个string
operator<< 向outputstream输出string的内容
getline(istream& is, string& str, char delim); 或getline(isstream& is, string& str);
< =组合的逻辑运算符。不相等的话从头来比较char的asii码大小。

deque

#include
vector是单向开口的连续存储空间，deque是双向开口的连续存储空间。可以在头和尾方便的进行元素的插入和删除工作。O(1)访问元素。底层实现是数组和链表，将一段一段连续空间连起来。
原理是用一段连续空间存储指针，每一个指针指向缓冲区，缓冲区是内容主体。

成员函数：保留vector所有。vector不同的:

push_back()
push_front()
pop_back()
pop_front()
swap()

stack

#include
在deque上实现。没有迭代器 只提供栈顶操作

成员函数：

top()
push()
pop()
size()
empty()

queue

#include
在deque上实现。没有迭代器

成员函数：

empty()
size()
front()
back()
push_back()
pop_front()

priority_queue

实现一个堆（一种平衡二叉树，每一个根节点都大于所有子节点叫大顶堆，每一个根节点都小于所有子节点叫小顶堆）O(1)时间查找最大最小元素

成员函数与stack相同。

template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;

//默认大顶堆
//创建小顶堆
priority_queue<int, vector<int>, std::greater<int>> small_heap;
//greater表示实现l > r
//less表示实现l < r

forward_list

单向链表。O(1)时间实现元素的增加和删除

成员函数：

容量：
- empty()
  STL中唯一不提供size()的容器
成员访问：
- front()返回头指针元素
操作：
- push_front()
- pop_front()
- insert_after()
- erase_after()
- swap()
- merge(forward_list &fwdlist, Compare comp); 默认升序排列合并
- sort( Compare comp) 默认升序排列
- reverse()
- remove(const value_type &val) 删除特定元素。还有remove_if
- unique() 删除重复元素

list

双向循环链表。支持任意位置的O(1)插入删除操作，但是不支持快速随机访问（与vector的区别）

成员函数：

成员访问：
- front()
- back()
操作：
- push_front
- pop_front
- push_back
- pop_back
- emplace(const_iterator position, Args&&… args); 在posistion出construct一个元素并插入

关联STL容器（set和map）

底层都是红黑二叉树来实现的

set

set 元素的键值就是实值，实值就是键值。
set 不允许两个元素有相同的键值。
不可以通过 set 的迭代器改变其元素值，即 set iterator 是一种 constant iterators。
当对 set 进行插入删除操作后，原有的迭代器依然有效，被删除元素的迭代器除外。

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

set是升序排列的。

主要成员函数：

迭代器：
- begin()
- end()
容量
- empty()
- size()
操作：
- insert(const value_type &val)
- erase(const value_type &val) 或 erase(const_iterator position)
- swap()
- clear()
find(const value_type &val) 返回迭代器.没找到返回end()
count(const value_type &val) 返回val的值。但是set本身不允许有duplicate

Set衍生：

unordered_set

template < class Key,                        // unordered_set::key_type/value_type
           class Hash = hash<Key>,           // unordered_set::hasher
           class Pred = equal_to<Key>,       // unordered_set::key_equal
           class Alloc = allocator<Key>      // unordered_set::allocator_type
           > class unordered_set;

根据hash表加速迭代器访问速度。（每一个元素的内存地址为hash_function(Key)）

multiset可以保存duplicate

template < class T,                        // multiset::key_type/value_type
           class Compare = less<T>,        // multiset::key_compare/value_compare
           class Alloc = allocator<T> >    // multiset::allocator_type
           > class multiset;

map key-value pair

map 的所有元素都是 pair，同时拥有实值value和键值key。pair 的第一元素为键值，第二元素为实值。
map 不允许两个元素拥有相同的键值。
不可以通过 map 的迭代器改变其元素的键值，可以修改元素的实值。
当对 map 元素进行增加或删除操作后，原有的迭代器依然有效，被删除的元素的迭代器除外。

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

从这个模板类可以看出，map是排序的，默认为升序排列。在声明map的时候可以声明Compare。

成员函数：

成员访问：
- at()
- operator[]，返回mapped_value, 如果没有键值被匹配上，则添加一个key。
  其余的与set相同。

map的衍生

unordered_map

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

同样是hash表

multimap，可以保存duplicate key的map