C++之数据结构

前言

C++的基础数据结构基本都存在于STL的头文件中，包括栈、队列、堆、哈希表、数组等等结构，这里我要对这些结构的基本使用做一个总结，具体包含元素的插入、查找、删除、遍历、取出等基本操作。

1.简单容器（pair/tuple)

pair和tuple属于简单的一维向量容器，二者都属于静态容器，即必须提前申明元素个数和元素类型，其中pair中只能包含两个元素，tuple个数不限。下面就二者的创建、元素访问、元素修改进行对比说明：

	pair	tuple
形式	, eg:	, eg:
头文件	< utility >	< tuple >
直接创建	std::paira = {1, 2}	std::tuplefoo (10,’x’);
函数创建	std::paira =std::make_pair(1,2)	auto bar = std::make_tuple (“test”, 3.1, 14, ‘y’);
访问	a.first和a.second	std::get<位置>(bar)
修改	a.first=x	std::get<位置>(bar)=x
交换两容器	swap(a,b)或者a.swap(b)	swap(a,b)或者a.swap(b)

2.多功能容器(array/vector)

2.1 array

array是对数组的一种封装形式，比如：int a[] = {1,2,3,4} <=> std::arraya = {1,2,3,4}，因此其有以下几个特点：

• 静态数组：默认创建在栈上，元素类型和元素个数固定，要注意的是跟tuple不同，array的元素类型只支持基础数据类型，如：int、double、char…；

• 数组创建与初始化：

  std::array<int,5> x = {10, 20, 30, 40, 50};
  std::array<int,5> y = {1,2};//剩余默认填充为0
  std::array<char,5> z = {};//默认初始化为''

• 数组属性获取：

  a.size()//元素数量
  a.empty()//数组是否为空，eg:std::array<int,0> a;

• 元素直接访问：

  a[0];//返回第一个元素
  a.at(0);//同上
  a.front();//返回第一个元素
  a.back();//返回最后一个元素
  a.data();//返回数组头指针

• 迭代器访问：

  std::array<int,5> x = {10, 20, 30, 40, 50};
  std::array<int,5>::iterator it;//auto it = x.begin();
  for ( it = x.begin(); it != x.end(); ++it )//前向迭代
      std::cout << ' ' << *it;//*iterator返回迭代器指向的元素
  
  for ( auto it = x.rbegin(); it != x.rend(); ++it )//反向迭代
      std::cout << ' ' << *it;//*iterator返回迭代器指向的元素
  
  for ( int& p: x)//循环访问
      std::cout << ' ' << p;//*iterator返回迭代器指向的元素
  //防止修改元素
  for ( it = x.cbegin(); it != x.cend(); ++it )//前向迭代
      std::cout << ' ' << *it;//*iterator返回迭代器指向的元素
  
  for ( auto it = x.crbegin(); it != x.crend(); ++it )//反向迭代
      std::cout << ' ' << *it;//*iterator返回迭代器指向的元素

• 元素修改：

  元素的修改可直接利用元素的访问进行直接修改，并且array提供了一键填充的函数fill()以及容器交换的功能swap()。与此同时，array还提供了元素级的逻辑比较运算符,比如：>,==,<等等，都是要求所有元素都满足逻辑操作才返回true。

2.2 vector

vector是一个多功能的容器，其被创建于堆上，支持所有元素属性，其最大的特点就是动态容器特性，即可以动态调整内存，不过一般每次扩大内存都会比之前大一倍，然后将之前的元素复制到新内存，最后释放原内存。上述所有简单容器的功能vector都具备，用法也类似，所以我这里只介绍其不同的地方。其包含于<vector>头文件之中。

• 容器创建与初始化：

  std::vector<int> foo (3,0);//创建一个有3个int元素的容器，并初始化为0

• 容器属性：

  a.size();//容器大小
  a.empty();//容器是否为空
  a.resize(5);//调整容器大小为5，不足的初始化为0，多余的去掉，不影响已分配的内存大小
  a.resize(5,10);//调整容器大小为5，不足的初始化为10，不影响已分配的内存大小
  a.capacity();//容器当前已分配的大小(（)单位是元素)
  a.reserve(100);//强制调整容器已分配内存元素数量至100
  a.shrink_to_fit();//强制调整a.capacity()=a.size()

• 元素调整：

  a.assign(InputIterator first, InputIterator last);//将另一个容器的first~last位置处的元素赋值给a
  a.assign(size_type n, const value_type& val);//赋值n个val值
  a.erase(a.begin()+5);//移除a[6]
  a.erase(a.begin(),myvector.begin()+3);//移除a[0]~a[3]
  a.emplace(a.begin()+1, 100);//在a[0]和a[1]之间插入元素值100，返回当前迭代器a.begin+1
  a.emplace_back(100);//在a末尾添加100
  a.insert(a.begin()+1,100)//在a[1]之前插入100
  a.insert(a.begin(),2，100)//在a[0]处插入两个100
  a.insert (a.begin(), src, dst);//将src地址/迭代器到dst的地址/迭代器指向的元素插入到a.begin()处
  a.push_back (100);//在末尾添加100
  a.pop_back();//移除末尾元素
  a.clear();清空容器

3.队列(queue/dequeue)

队列，顾名思义就是遵循先进先出(First in First out, FIFO)原则的线性表结构，在c++的stl标准中也添加了队列结构。其中queue位于头文件<queue>中，用法和原理如下图所示：

注：初始化不需要定义元素个数，只需要定义元素类型，如：queue<int>q;

当然，随之元素不断的添加，queue很可能会发生内存冲突，因此可以利用queue(int,other)来初始化，其中other代表其它数据类型，一旦被定义，则第一个元素int失效，比如other = std::list<int>代表queue会在遵循FIFO的前提下采用链表存储队列。当然，还可以为其他类型，比如下面要提到的deque：

deque是双端队列，顾名思义其可以在队列的头部以及尾部插入和删除数据，其跟vector的用法很像，不过不同的是deque的动态内存体现在由多个连续的缓冲区组成，并由一块连续内存进行管理：

可以看到，map中包含每个缓冲区的节点，每个节点内含有当前缓冲区的中当前元素的指针，当前缓冲区头指针，当前缓冲区尾指针。

deque包含于<deque>头文件中，其绝大多数功能和vector类似，包括元素访问、元素修改等等，比较特殊的就是其添加和去除元素是在队列两端执行的，如：pop_back(),pop_front(),push_back(),push_front()。其初始化方式

4.链表(forawrd_list/list)

链表是一类典型的非连续内存线性表，其包括单向链表(forward_list)和双向列表(list)，分别位于同名头文件中。既然是线性表，其自然就具有基本功能，如元素的遍历访问、元素的删除、元素的插入、元素的添加、元素的修改等。二者的创建以及初始化方式相同，不同的就是功能上，单向链表不支持末尾方向的迭代、添加和取出。

初始化方式一般有：

//第一种，构造函数
int a[] = {1,2,3,4,5};
list<int> l1(a, a+5);        // 将数组a的内容赋值给l1
list<int> l2(2,100);         // 2个值为100的元素
list<int> l3(l2);
list<int> l4(l3.begin(),l3.end());  
list<int> l5 = {1,2,3,4,5};
//第二种，用push_back或push_front，forward_list不支持push_back()
for (int i = 1; i <= 5; ++i) 
    l5.push_back(i);
    l5.push_front (200);
    l5.push_front (300);
//第三种,用assign
list<int> first;
list<int> second;
first.assign(7,100);                       // 给first添加7个值为100的元素
second.assign(first.begin(), first.end()); // 复制first给second

另外，forward_list的元素删除是利用erase_after()，即将迭代器指向位置之后的一个元素删除，而list可以直接利用erase删除当前指向位置。除此之外，链表还提供了以下几个特殊功能：

std::forward_list<int> list1 = {10, 20, 30, 40, 30, 20, 10};
std::list<int> list2 = {10, 20, 30, 40, 30, 20, 10};
list1.remove(20);//移除20
bool single_digit (const int& value) { return (value<20); }
list2.remove_if(single_digit);//移除小于20的元素
list1.sort();//从小到大排序
list2.sort(std::greater<int>());//从大到小排序
list1.merge(other);//合并两个链表，不过最好先排序再合并，止痒合并之后会自动排序，不然顺序看不懂
list.unique(); //链表去重，可自定义指标，如：
bool same_integral_part (double first, double second)
{ return ( int(first)==int(second) ); }

还有链表的衔接功能，具体可以去看官网。

5.哈希表和红黑树(map/unordered_map)

map和unordered_map的功能就是实现了类似于字典查询的功能，即<class T1, class T2>的key-value模式，二者都在同名头文件之下，虽然功能一样，但是二者的底层实现完全不同。map采用的是红黑树结构，即一种自平衡的二叉排序树，其查询速度是logn，利用中序遍历方式便利，因此map本身会对元素进行排序。而unordered_map采用的是散列表的结构，散列函数为除留余数法，并利用链地址法防止散列冲突。因此map比unordered_map在时间效率上慢，不过空间占用要少。

二者的功能一致，主要包含：创建、查找、增加、删除、遍历，另外要注意的是，map的排序是默认排序，如果key不是常见的数值元素，最好自定义一个比较函数。

//创建
std::map<std::string,int> mymap = {
                { "alpha", 0 },
                { "beta", 0 },
                { "gamma", 0 } };//可以利用pair结构填充
  mymap.at("alpha") = 10;
  mymap.at("beta") = 20;
  mymap.at("gamma") = 30;
  mymap["alpha"]="an element";
  mymap["beta"]="another element";
  mymap["gamma"]=mymap['b'];
//增加
mymap.insert (std::pair<string,int>("abc",100) );
//删除
mymap.erase ("abc");
it=mymap.find("alpha");
mymap.erase (it);
//遍历
//同vector
//查找
it = mymap.find('b');//如果it != mymap.end()则存在，否则不存在，mymap.end()指向最后一个元素之后

6.集合(set/unordered_set)

集合的特性就是元素的独一性，与上一章类似，set和unordered_set分别采用红黑树和哈希表的方式创建，支持的元素不止基本数据类型，还支持容器。使用方式如下：

//创建
std::set<int> first;                           // empty set of ints
int myints[]= {10,20,30,40,50};
std::set<int> second (myints,myints+5);        // range
std::set<int> third (second);                  // a copy of second
std::set<int> fourth (second.begin(), second.end());  

std::set<vector<int>> s;

//增加
s.insert({1, 2});
s.insert({1, 3});
s.insert({1, 2});
//删除
myset.erase (it);//删除迭代器指向的元素
myset.erase (40);
it = myset.find (60);
myset.erase (it, myset.end());
//遍历
//同上
//查找
//同map
//功能
second.count(10);//统计10的个数

7.栈(stack)

栈跟队列很像，不同的就是栈式遵循先进后出(Last in First out, LIFO)，功能很简单：

std::stack<int> mystack;

mystack.push(10);//添加
mystack.push(20);

mystack.top() -= 5;//栈顶元素-5
mystack.pop();//取出栈顶元素

8.串(string)

字符串(string)与字符数组(char[])很像，从速度上来讲string操作更慢，从操作效率来讲，string更简单，其中string在<string>头文件下，char相关字符操作在<cstring>头文件下。

要注意的是下面两种char数组的区别：

char a[] = "123";//实际存储为{'1', '2', '3', '\0'}，strlen(a)=3
char b[] = {'1', '2', '3'};//实际存储为{'1', '2', '3'}，strlen(b)=3

具体如下：

//创建
std::string s0 ("Initial string");
// constructors used in the same order as described above:
std::string s1;
std::string s2 (s0);//copy s0
std::string s3 (s0, 8, 3);//copy s0[8]~s0[11]
std::string s4 ("A character sequence");
std::string s5 ("Another character sequence", 12);//只保留12个字符
std::string s6a (10, 'x');//10个x
std::string s6b (10, 42);      // 42 is the ASCII code for '*'
std::string s7 (s0.begin(), s0.begin()+7);//copy s0[0]~s0[6]

//属性
std::string str ("Test string");
std::cout << "size: " << str.size() << "\n";//11
std::cout << "length: " << str.length() << "\n";//11
std::cout << "capacity: " << str.capacity() << "\n";//15
std::cout << "max_size: " << str.max_size() << "\n";//429496729

//元素访问
str.at(i);
str[i];
for ( std::string::iterator it=str.begin(); it!=str.end(); ++it)
    std::cout << *it;

//元素赋值
//string
std::string str;
std::string base="The quick brown fox jumps over a lazy dog.";
str.assign(base);
str.assign(base,10,9);//copy base[10]~base[18],"brown fox"
str.assign("pangrams are cool",7);//截断为长度7,"pangram"
str.assign("c-string");
str.assign(10,'*');// "**********"
str.assign<int>(10,0x2D);// "----------"
str.assign(base.begin()+16,base.end()-12);// "fox jumps over"
//char[]
char ch1[] = "give me";
char ch2[] = "a cup";
strcpy(ch1,ch2);//ch1 = "a cup";

//数组合并
//string
string str1 = "give me ";
string str2 = "a cup";
str1 = str1 + str2;//ch1=give me a cup
//char
char ch1[15] = "give me "; // 注意长度，合并后为13
char ch2[] = "a cup";
strcat(ch1,ch2);//ch1=give me a cup

//合并
//string
string str1 = "ab";
string str2 = "cdefg";
str1.append(str2,2,3); // str1=str1+str2[2~4],abefg
//char
char ch1[10] = "ab";  // 注意合并后的长度
char ch2[] = "abc";
strncat(ch1,ch2,3);    // ch1+ch2[0~2],ababc

//替换
//string
str1.replace(0,1,str2,4,2);//str1[0]=str2[4]+str2[5]
//char
strncpy(ch1,ch2,3);//ch1=ch1+ch2[0~2]

//拷贝
//string
string str1 = "abc";
char ch2[10] = "defg";
str1.copy(ch2,10,1);//将str1[1~10]放在ch2，覆盖
//char
char ch1[10] = "abc";
char ch2[] = "de";
memmove(ch1,ch2,2);//将ch2[0~1]放在ch1，覆盖

//插入
std::string str="to be question";
std::string str2="the ";
std::string str3="or not to be";
std::string::iterator it;

str.insert(6,str2);                 // to be (the )question
str.insert(6,str3,3,4);             // to be (not )the question
str.insert(10,"that is cool",8);    // to be not (that is )the question
str.insert(10,"to be ");            // to be not (to be )that is the question
str.insert(15,1,':');               // to be not to be(:) that is the question
it = str.insert(str.begin()+5,','); // to be(,) not to be: that is the question
str.insert (str.end(),3,'.');       // to be, not to be: that is the question(...)
str.insert (it+2,str3.begin(),str3.begin()+3); // (or )

//删除
std::string str ("This is an example sentence.");
str.erase (10,8); //从第10个位置删除8个元素，"This is an sentence."
str.erase (str.begin()+9); //删除第10个元素， "This is a sentence."
str.erase (str.begin()+5, str.end()-9);  //    

//查找
string str("Hello worldw");
int m = str.find('w',0);   // 从str起始位置开始查找w字符
int n = str.find_first_not_of('w',0);  // 查找str起始位置开始不是w的字符
int k = str.find_first_of('w',0);  // 从str起始位置开始查找第一个w字符
int l = str.find_last_of('w');   // 查找最后一个w的位置
int p = str.find_last_not_of('w');  // 查找最后一个不是w的字符的位置
int q = str.rfind('w');　// 反向查找

//转换
string str1 = "Hello World";
const char* ch1;
ch1 = str1.c_str();

9.bitset

有时候为了操作的效率以及大数据处理，我们可能会用到数组元素只有{0,1}，仅仅占用1bit，不同于bool型的数组，其可以用来做2进制操作，位于同名头文件。

//创建
bitset<4> bitset1;　　//0000
bitset<8> bitset2(12);　　//将12转化为8位2进制，00001100
string s = "100101";
bitset<10> bitset3(s);　　//0000100101
char s2[] = "10101";
bitset<13> bitset4(s2);　　//0000000010101

bitset<2> bitset1(12);　　//12的二进制为1100（长度为4），但bitset1的size=2，只取后面部分，即00
string s = "100101";　　
bitset<4> bitset2(s);　　//s的size=6，而bitset的size=4，只取前面部分，即1001
char s2[] = "11101";
bitset<4> bitset3(s2);　　//与bitset2同理，只取前面部分，即1110

//位运算
bitset<4> foo (string("1001"));
bitset<4> bar (string("0011"));

cout << (foo^=bar) << endl;       // 1010 (foo对bar按位异或后赋值给foo)
cout << (foo&=bar) << endl;       // 0010 (按位与后赋值给foo)
cout << (foo|=bar) << endl;       // 0011 (按位或后赋值给foo)

cout << (foo<<=2) << endl;        // 1100 (左移２位，低位补０，有自身赋值)
cout << (foo>>=1) << endl;        // 0110 (右移１位，高位补０，有自身赋值)

cout << (~bar) << endl;           // 1100 (按位取反)
cout << (bar<<1) << endl;         // 0110 (左移，不赋值)
cout << (bar>>1) << endl;         // 0001 (右移，不赋值)

cout << (foo==bar) << endl;       // false (0110==0011为false)
cout << (foo!=bar) << endl;       // true  (0110!=0011为true)

cout << (foo&bar) << endl;        // 0010 (按位与，不赋值)
cout << (foo|bar) << endl;        // 0111 (按位或，不赋值)
cout << (foo^bar) << endl;        // 0101 (按位异或，不赋值)

//元素的访问和修改
bitset<4> foo ("1011");//最低位是0，与常规数组索引相反！！！！！！！！

cout << foo[0] << endl;　　//1
cout << foo[1] << endl;　　//1
cout << foo[2] << endl;　　//0

//功能
bitset<8> foo ("10011011");

cout << foo.count() << endl;　　//5　　bitset中1的个数
cout << foo.size() << endl;　　 //8　　bitset的大小

cout << foo.test(0) << endl;　　//true　　test函数用来查下标处的元素是0还是1，并返回false或true
cout << foo.test(2) << endl;　　//false　　foo[2]为0，返回false

cout << foo.any() << endl;　　//true　　any函数检查bitset中是否有1
cout << foo.none() << endl;　　//false　none函数检查bitset中是否没有1
cout << foo.all() << endl;　　//false　　all函数检查bitset中是全部为1
bitset<8> foo ("10011011");

cout << foo.flip(2) << endl;　　//10011111　　指定位取反
cout << foo.flip() << endl;　　 //01100000　　全部取反

cout << foo.set() << endl;　　　　//11111111　　全部置1
cout << foo.set(3,0) << endl;　　//11110111　　第3位置0
cout << foo.set(3) << endl;　　  //11111111　　第3位置1

cout << foo.reset(4) << endl;　　//11101111　　第4位置0
cout << foo.reset() << endl;　　 //00000000　　全部置0

//转换
bitset<8> foo ("10011011");

string s = foo.to_string();　　//“10011011”
unsigned long a = foo.to_ulong();　　//155，将bitset转换成unsigned long类型
unsigned long long b = foo.to_ullong();　　/155，将bitset转换成unsigned long long类型

---

参考资料

1. http://www.cplusplus.com/reference