美文网首页C++C++STL
[ACM基础] C++ STL 全面学习

[ACM基础] C++ STL 全面学习

作者: Me极客 | 来源:发表于2018-01-15 01:09 被阅读62次
读者请看

如果本文有不妥的地方,或者您有好的建议,或者槽点,或者问题,请留言,谢谢!

提供一个c++ 网页编译器

https://ideone.com/

入门须知

STL包括五种类型的组件:containers(容器)、iterators(迭代器)、algorithms(算法)、function objects(函数对象)和 allocators(内存分配器)


STL 的各 Container 以及 algorithms 并定义在命令空间“std”中,并不是定义在全局命名空间中,所以在 include 对应头文件后,还得加上这句:
using namespace std;


container 的类型都是模板参数类型,模板参数放在 <>(尖括号中)


在定义嵌套的 container 的时候,尖括号间要加上适当的空格:

vector< vector<int> > v1; // 正确的定义方式
vector<vector<int>> v2; // 错误的定义方式,编译器会把 >> 和输出操作的 >> 混淆

1-vector

声明:方法1

vector<int> v;

声明:方法2

vector<int> v(10); 

长度:

v.size();

添加一个新的元素:

push_back()

指定的位置添加元素的话,那么就得调用 insert() 函数
对应的 erase() 函数用于删掉指定的元素
如果你要调整 vector 的大小,可以调用 resize() 函数:
清空

clear()

2-Iterators

所有的 STL container 都可以通过 iterator 遍历。

Iterators 和指针很类似,它定义了如下基本操作:
1)获取一个 Iterators 的值:int x = *iter;
2)自增、自减 Iterators:iter++, iter–;
3)可以用 != < 等比较运算符对不同的 Iterators 进行比较;
4)Iterators 移动动指定的偏移位置,如 iter += 20(iter 前移 20 个元素的位置);
5)获取两个 Iterators 间的距离:int distance = iter2 – iter1;

通常 STL 的算法都会用两个 Iterators,一个 begin iterator、一个 end iterator,begin 指向 container 的第一个元素,end 指向 container 最后一个元素的下一个位置。每个 STL container 都有两个函数 begin()、end(),分别用于获取该 container 的 begin iterator 和 end iterator。
每个 container 都有两个函数 rbegin() 和 rend(),用于返回反向的 iterators,rbegin() 指向结尾、rend() 指向开头。在需要反向遍历 container 的时候,可用这两个函数。

还有一种是 const :const_iterator

3-string

String 有一个 substr() 函数,这个函数只需要通过下标值操作,不依赖于 iterators

string s = "hello"; 
 string 
      s1 = s.substr(0, 3), // "hel" 
      s2 = s.substr(1, 3), // "ell" 
      s3 = s.substr(0, s.length()-1), "hell" 
      s4 = s.substr(1); // "ello"

4-set

STL 的 Set(集合) 有以下基本性质或操作:
1)任意两元素都是不相等的;
2)可添加、删除元素;
3)可获取元素的个数;
4)可查询集合中是否有指定元素(可在 O(logN) 时间内完成)。

set<int> s; 
s.insert();  // 插入
s.erase();  // 删除
s.size();  // 大小

遍历 Set 的唯一方法是用 iterators

// Calculate the sum of elements in set 
 set<int> S; 
 // ... 
 int r = 0; 
 for(set<int>::const_iterator it = S.begin(); it != S.end(); it++) { 
      r += *it; 
 }

5-map

map<string, int> M; 

 M["Top"] = 1; 
 M["Coder"] = 2; 
 M["SRM"] = 10; 

 int x = M["Top"] + M["Coder"]; 

 if(M.find("SRM") != M.end()) { 
      M.erase(M.find("SRM")); // or even M.erase("SRM") 
 }

在底层实现上,map 和 set 都是基于红黑树的

6-常用宏

 typedef vector<int> vi; 
 typedef vector<vi> vvi; 
 typedef pair<int,int> ii; 
 #define sz(a) int((a).size()) 
 #define pb push_back 
 #defile all(c) (c).begin(),(c).end() 
 #define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++) 
 #define present(c,x) ((c).find(x) != (c).end()) 
 #define cpresent(c,x) (find(all(c),x) != (c).end())

[完整学习]-array [序列容器 连续存储 固定长度]

template < class T, size_t N > class array;  // 固定长度 不可变

头文件写法

#include <array>

构造函数写法(三种方法,与c的数组初始化类似)

array<int, 5> myarray = { 9, 7, 5, 3, 1 };   // 1.使用操作符号=
array<int, 5> myarray { 9, 7, 5, 3, 1 };       // 2.类似于java的方法
array<int, 5> myarray;                         // 3.先定义,后写入数据,写入数据有讲究  
myarray = { 0, 1, 2, 3, 4 };                    // 符合的
myarray = { 9, 8, 7 };                           // 符合, 3和4位置数据是0!
myarray = { 0, 1, 2, 3, 4, 5 };                   //不允许!!!

获取元素:1.使用的操作符 []

//      [ ]  数组操作符号  注意没有边界检测
array<int, 5> myarray;  
cout << myarray[1];   
myarray[2] = 6;

获取元素:2.使用函数 at() front() back() data()

array<int, 5> myarray { 9, 7, 5, 3, 1 };
                        // 使用函数  at()
myarray.at(1) = 6;      // 正确运行,并赋值   
myarray.at(9) = 10;     // 9无效,会报错
myarray.front()                   // front  获取第一个元素
myarray.back()                    // back  获取最后一个元素
                                  // data() 获取第一个元素的指针  如下面的复制的例子
const char* cstr = "Test string"; 
array<char,12> charray;
memcpy (charray.data(),cstr,12);
cout << charray.data() << '\n';

容量大小 size() max_size() empty()

array<double, 5> myarray { 9.0, 7.2, 5.4, 3.6, 1.8 };
myarray.size();      // 获取内容容量
myarray.max_size()   // 获取容器的最大容量
myarray.empty()      // 根据内容容量size()来判断,返回bool

修改器|编辑器 fill() swap()

array<int,6> myarray;
myarray.fill(5);                   //数组用某一个对象填充
                                   // swap 交换俩个数组,数组长度必须保持一致
void swap (array& x){}     // 函数定义   
array<int,5> first = {10, 20, 30, 40, 50};   // 以下有一个例子
array<int,5> second = {11, 22, 33, 44, 55};
first.swap (second);

迭代器遍历

array<int,5> myarray = { 2, 16, 77, 34, 50 };
for ( auto it = myarray.begin(); it != myarray.end(); ++it )
    cout << ' ' << *it;

排序 sort()

// sort需要此头文件
#include <algorithm>                       
array<int, 5> myarray { 7, 3, 1, 9, 5 };
sort(myarray.begin(), myarray.end());   // 正序排序
sort(myarray.rbegin(), myarray.rend()); // 倒序排序
for (const auto &element : myarray)     // 输出;Java也有类似方法
    cout << element << ' ';

[完整学习]-vector[序列容器 动态数组 分配符操作]

template < class T, class Alloc = allocator<T> > class vector; // 

头文件写法

#include <vector>

构造函数写法(3种方法,与array初始化类似)

std::vector<int> array2 = { 9, 7, 5, 3, 1 }; 
std::vector<int> array3 { 9, 7, 5, 3, 1 };
std::vector<int> array;  
array = { 0, 1, 2, 3, 4 }; // 正确,数组自动调整大小来适应
array = { 9, 8, 7 }; // 现在数组长度是3

重新分配向量函数 : assign()函数 包含3种用法(c11)

vector<int> first;   /* assign方法1 */     
first.assign (5,100);    //  初始化5个为100的元素 相当于 fill()函数
vector<int> second;  /* assign方法2  使用迭代器指针*/
vector<int>::iterator it; 
it=first.begin()+1;
second.assign (it,first.end()-1);   // 两个参数 是初始化的迭代器指针;
vector<int> third;   /* assign方法3 数组参数 c98不可以*/ 
int myints[] = {1,2,3};
third.assign (myints,myints+3);   //  类似于方法2,指定开始和结束的指针

获取元素:1.使用的操作符 []

std::vector<int> array; 
array[6] = 2; // []没有边界检测 

获取元素:2.使用函数 at() front() back() data()

std::vector<int> array; 
array.at(7) = 3; // 会边界检测
                 // front() back() data() 这三个函数也有 同array一样

容量 size() resize() capacity() max_size() empty() reserve() shrink_to_fit()

vector<int> array { 9, 7, 5, 3, 1 };
array.size();      // vector会自动记住自己的长度,通过这个size函数访问
array.resize(10);  // 后面的元素使用0补齐,不够原来的就丢弃;此函数不会修改capacity;
array.max_size();  // max_size: 1073741823  最大长度
array.capacity();  // 目前vector申请的空间的大小;
array.empty();     // 检测是否为空  
array.reserve(n);  //  如果n小于capacity那么没用,如果大于capacity那么capacity变为n;
array.shrink_to_fit() // 节省内存的一种方法,会使size=capacity;

增加元素

push_back(obj); // 随着增加,vactor.capacity() 是线性增加,2倍增速;注意是末尾加入;

insert();  // c11 返回值都是指向插入元素的迭代器
           // 以下是三种声明的用法     注意:都是插入迭代器之前
iterator insert (const_iterator position, const value_type& val);   
//在指定位置loc前插入值为val的元素,返回指向这个元素的迭代器, 
iterator insert (const_iterator position, size_type n, const value_type& val);
//在指定位置loc前插入num个值为val的元素 
iterator insert (const_iterator position, InputIterator first, InputIterator last);
//在指定位置loc前插入区间[start, end)的所有元素 . 
/* 方法1:举例 */
vector<int> myvector (3,100);
vector<int>::iterator it;
it = myvector.begin();
it = myvector.insert ( it , 200 );
/* 方法2:举例 */
myvector.insert (it,2,300);
/* 方法3:举例 */
it = myvector.begin();
vector<int> anothervector (2,400);
myvector.insert (it+2,anothervector.begin(),anothervector.end());
/* 方法4:采用数组的方式 */
int myarray [] = { 501,502,503 };
myvector.insert (myvector.begin(), myarray, myarray+3);

/* 一个比较好的方法:避免不必要的临时对象的产生  */
emplace(); // iterator emplace (const_iterator position, Args&&... args);
emplace_back(); // void emplace_back (Args&&... args); 
    /* 方法1 例子*/
std::vector<int> myvector = {10,20,30};
auto it = myvector.emplace ( myvector.begin()+1, 100 );
myvector.emplace ( it, 200 );
myvector.emplace ( myvector.end(), 300 );
for (auto& x: myvector)
  std::cout << ' ' << x;

// out:10 200 100 20 30 300
    /* 方法2 例子*/
std::vector<int> myvector = {10,20,30};
myvector.emplace_back (100);
myvector.emplace_back (200);
for (auto& x: myvector)
   std::cout << ' ' << x;

//out:10 20 30 100 200

删除元素

pop_back(); // 删除最后一个元素;
clear();  //清除向量的全部元素,使得size等于0;

erase();  // 真正移除 有两种声明的方式 如下
iterator erase (const_iterator position);
// 删除当前iterator指向的数据,同时后面的数据自动前移
iterator erase (const_iterator first, const_iterator last);
// 删除一个范围的数据
std::vector<int> myvector;
for (int i=1; i<=10; i++) myvector.push_back(i);
/* 方法1 : 举例*/
myvector.erase (myvector.begin()+5);  
/* 方法2 : 举例*/
myvector.erase (myvector.begin(),myvector.begin()+3);

了解即可的函数

swap();  //  void swap (vector& x);

了解即可 的 全部迭代器

Iterators:

begin end
//Return iterator to beginning/end
rbegin rend
//Return reverse iterator to reverse beginning/end
cbegin  cend 
//Return const_iterator to beginning/end
crbegin  crend 
//Return const_reverse_iterator to reverse beginning/end 

备注:内存会自动安全释放;

[完整学习]-stack[容器适配器 LIFO先进后出]

头文件

#include <stack>

构造函数

/* 方法1: 空栈 */
std::stack<int> first;  
/* 方法2:队列构造 */
std::deque<int> mydeque (3,100);
std::stack<int> second (mydeque); 
/* 方法3:容器空栈 */
std::stack<int,std::vector<int> > third; 
/* 方法4:容器构造栈 */
std::vector<int> myvector (2,200);
std::stack<int,std::vector<int> > fourth (myvector);

方法

empty() // 判断空栈
size()  // 得到栈的空间大小
top()   // return 栈的顶部元素
push()  // 插入元素 无返回值
pop()  // 删除顶部元素 无返回值

emplace() // 构造插入一个元素 例如 插入字符串

了解的函数

swap();

[完整学习]-queue[容器适配器 FIFO先进先出 队列]

头文件

#include <queue>

构造函数

/* 方法1:空队列 */
std::queue<int> first;    
/* 方法2:双端队列构造 */     
std::deque<int> mydeck (3,100);        
std::queue<int> second (mydeck);   
/* 方法3:链表构造空队列 */   
std::queue<int,std::list<int> > third; 
/* 方法4:链表构造队列 */
std::list<int> mylist (2,200);     
std::queue<int,std::list<int> > fourth (mylist);

方法

empty();
size();
front();  // 访问队首元素
back();   // 访问队尾元素
push(x);  // 入队,将x接到队列的末端
pop();    // 出队,弹出队列的第一个元素,注意,并不会返回被弹出元素的值。
emplace(x); // 将x接到队列的末端

其他函数

swap();

[完整学习]-deque[双端队列 序列 动态数组]

deque相当与array和vector里面的vector;
头文件

#include <deque> 

构造函数

/* 方法1:空队列 */
std::deque<int> first;
/* 方法2:fill构造 */
std::deque<int> second (4,100);    
/* 方法3:迭代器构造 */
std::deque<int> third (second.begin(),second.end());
/* 方法4:拷贝构造 */
std::deque<int> fourth (third); 
/* 方法5:数组构造 */
int myints[] = {16,2,77,29};
std::deque<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );
for (std::deque<int>::iterator it = fifth.begin(); it!=fifth.end(); ++it)
   std::cout << ' ' << *it;
/* 方法6:= 构造  return *this */
std::deque<int> first (3);    
std::deque<int> second (5);   
second = first;

迭代器可以参考vector的,一共8个;

[完整学习]-list[]

头文件

[完整学习]-forward_list[]

头文件

[完整学习]-map[]

头文件

[完整学习]-set[]

头文件

[完整学习]-unordered_map[]

头文件

[完整学习]-unordered_set[]

头文件

相关文章

  • [ACM基础] C++ STL 全面学习

    读者请看 如果本文有不妥的地方,或者您有好的建议,或者槽点,或者问题,请留言,谢谢! 提供一个c++ 网页编译器 ...

  • c++ stl

    STL in ACM - To be an ACMan - 博客园 stl 在 acm中的应用总结 - 若流芳千古...

  • C++ STL 学习笔记

    C++ STL 学习笔记

  • ACM基础——STL详解

    [TOC] 本内容参考北大基础训练PPT《C++模板与STL库介绍(单栋栋)》 概论 C++中有两个方面体现重用:...

  • STL之参考文献

    C++标准库是离不开模板的,STL占了C++标准库80%以上。 学习STL(c++ 98)的主要参考: gcc 3...

  • 浅析STL allocator

    STL allocator是做什么用? 在学习STL中containers会发现C++ STL里定义了很多的容器(...

  • 读书笔记17.06.03

    C++ STL:Listlist是C++标准模版库(STL,Standard Template Library)中...

  • [C++] STL 容器

    参考:[C++] STL 容器 (一) - 基本介紹[C++] STL 容器 (二) - Iterator 部分示例:

  • C++11 模板元编程 - Traits in TLP

    C++标准库STL中的type_traits文件中,已经有了比较全面的C++ trait组件,可以用来对代码做各种...

  • STL学习

    title: STL学习date: 2018-11-23 19:49:39 0. 前言 STL是C++中的一个类库...

网友评论

    本文标题:[ACM基础] C++ STL 全面学习

    本文链接:https://www.haomeiwen.com/subject/aetroxtx.html