avatar

C++-STL-Vector and Stack

STL 是“Standard Template Library”的缩写,中文译为“标准模板库”。STL 是 C++ 标准库的一部分,不用单独安装。

C++ 对模板(Template)支持得很好,STL 就是借助模板把常用的数据结构及其算法都实现了一遍,并且做到了数据结构和算法的分离。例如,vector 的底层为顺序表(数组),list 的底层为双向链表,deque 的底层为循环队列,set 的底层为红黑树,hash_set 的底层为哈希表。

为方便,以下省略

1
2
3
4
#include <iostream>
#include <stack>
#include <iostream>
using namespace std;

Vector

初始化

vector有许多初始化方式

1
2
3
4
5
6
7
8
vector<int> v1;// 仅声明, 没有分配空间
v1.reserve(20); // 当容量<=20时, 扩到20, 大于不做改变
vector<int> v2 (20); // 20个为0的元素
vector<int> v3(20, 3); // 20个为3的元素
vector<int> v4(v3); // 用v3初始化
vector<int> v5 {1, 2, 3};
int a[] = {1, 2, 3, 4};
vector<int> v6(a, a + 3); // 用迭代器初始化

容量和大小

1
2
3
4
5
v1.size() // 返回大小
v1.capacity() // 容量,一般比大小大
v1.resize (5); // 大小变为5,少于就增加默认值,多余就减去栈顶值
v1.resize (7, 99); // 使用默认值99,增加
s1.shrink_to_fit() // 类似于swift的sizeToFit() ? 把容量缩减为大小相等

访问

1
2
3
cout << v1.front();
cout << v1.back();
auto p = v1.data(); // vector<T> 返回 T*, 该指针指向v1

添加

1
2
v1.push_back(3);
v1.emplace_back("string");

emplace_back比push_back更有效率,如果是push_back(“123”)是构造了一个”123”的字符串然后再移动,而emplace_back()是在尾部直接构造,同时emplace_back()也允许你使用对象,像初始化的emplace一样。

值得注意的是,不能使用非成员函数去添加容器的元素

插入

1
2
3
4
5
vector<string> s1 {"first", "second"};
s1.emplace(++begin(s1), 'a', 5) // "first", "aaaaa", "second"
auto iter = s1.emplace(++s1.begin(), "two");// "first", "two", "aaaaa", "second"
// 这里iter是插入元素的迭代器,如果使用iter作为迭代器会在two的后面插入
s1.insert(++s1.begin(), "three");// "first", "three", "two", "aaaaa", "second"

如果要在指定位置插入,就用s1.begin()+n

删除

1
2
3
4
5
vector<int> v1 {1, 2, 3, 4, 5, 6, 7};
v1.pop_back() // 删除最后一个
auto iter = data.erase(v1.begin()+1); // 删除第二个元素,返回删除元素的后一个元素的迭代器
// 当然,也可以通过迭代器删除一段
auto iter = data.erase(v1.begin()+1, v1.begin()+3); // 同样的,这里会返回这段的后一个元素的迭代器

接下来看erase-remove操作

1
2
3
4
5
#include <algorithm>
vector<int> v1 {1, 2, 3, 5, 5, 7, 8, 9};
auto iter = remove(v1.begin(), v1.end(), 5); // 1, 2, 3, 7, 8, 9, 8, 9 可见是帮我们做了前移
v1.erase(iter, v1.end()); // 删除多余的
v1.erase(remove(v1.begin(), v1.end(), 5);, v1.end()); // 当然也可以直接一次性

遍历

一共有三种遍历方式

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> v1 {1, 2, 3};
// 迭代器
for (auto iter = v1.begin(); iter != v1.end(); iter++)
truecout << *v1;

for (auto i : v1)
cout << i;

for (int i = 0; i < v1.size(); i++)
cout << v1[i];

for_each(v1.begin(), v1.end(), [](int value) { cout << value << endl;}); // 第三个参数是一个function, 这里使用了lambda表达式

Stack

  • top():返回一个栈顶元素的引用,类型为 T&。如果栈为空,返回值未定义。
  • push(const T& obj):可以将对象副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
  • push(T&& obj):以移动对象的方式将对象压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
  • pop():弹出栈顶元素。不过这个是void类型
  • size():返回栈中元素的个数。
  • empty():在栈中没有元素的情况下返回 true。
  • emplace():用传入的参数调用构造函数,在栈顶生成对象。
  • swap(stack<T> & other_stack):将当前栈中的元素和参数中的元素交换。参数所包含元素的类型必须和当前栈的相同。对于 stack 对象有一个特例化的全局函数 swap() 可以使用。

对于emplace()swap()函数举个例子吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct node 
{
int data;
node *next;
node(int data, node* next)
{
this->data = data;
this->next = next;
}
};

int main()
{
stack<int> stack1, stack2;
for (int i = 0; i < 9; i++)
{
stack1.push(i);
stack2.push(8-i);
}
// stack1: 0 1 2 ... 8
// stack2: 8 7 6 ... 0
stack1.swap(stack2);
// stack2: 8 7 6 ... 0
// stack1: 0 1 2 ... 8

stack<node> nodeStack;
nodeStack.emplace(1, nullptr);

}

参考:http://c.biancheng.net/stl/

文章作者: X Mεl0n
文章链接: http://www.zrzz.site/2020/04/01/C-STL-Vector-and-Stack/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 X Mεl0n | 随手记

评论