vector
vector<int> a; //定义一个长度为10的vector
cout << a.empty() << endl;; //若为空返回true 否则返回false
cout << a.size() << endl; //返回是否为空
//系统为某一程序分配空间时,所需的时间与空间大小无关,与申请次数有关 => 倍增思想
for (int i = 0; i < 10; i ++) a.push_back(i);
for (int i = 0; i < a.size(); i ++) printf("%d ", a[i]);
puts("");
for(vector<int>::iterator i = a.begin(); i != a.end(); i ++) cout << *i << ' ';
puts("");
for(auto x : a) cout << x << ' ';
puts("");
cout << a.front() << endl;
cout << a.back() << endl;
a.clear(); //清空,注意:queue没有清空
//支持比较运算,按字典序
vector<int> x(3, 4), y(4, 3);
if(x > y) cout << "x > y" << endl;
pair
pair<int, string> p;
// pair<int, pair<int, string>> p;
p = make_pair(10, "zwx");
// p = {20, "zwx"}; //C++ 11
cout << p.first << endl;
cout << p.second << endl;
//支持比较运算,以first为第一关键字,以second为第二关键字
string 字符串
string a = "zwx";
a += "def";
a += 'c';
cout << a << endl;
cout << a.substr(1, 4) << endl; //第一个参数起始位置,第二个参数数组长度
cout << a.substr(1) << endl;
printf("%s\n", a.c_str());
queue 队列
queue<int> q;
for(int i = 0; i < 10; i ++) q.push(i);
for(int i = 0; i < 10; i ++) {
cout << q.front() << ' ' << q.back() << endl;
q.pop();
}
//清空
q = queue<int>();
//q.clear(); queue不存在clear函数
priority_queue 优先队列(堆)
priority_queue<int> heap; //默认大根堆
priority_queue<int, vector<int>, greater<int>> heap; //小根堆
heap.push();
heap.pop();
heap.top(); //返回堆顶元素
heap.clear();
stack 栈
stack<int> s;
s.push();
s.pop();
s.empty();
s.size();
s.top();
deque 双端队列
deque<int> dq;
dq.size();
dq.empty();
dq.clear();
dq.front(), dq.back();
dq.push_front(), dq.pop_front();
dq.push_back(), dq.pop_back();
dq.begin(), dq.end();
set & multiset => 维护有序序列
set<int> S; //不能有重复元素
multiset<int> MS; //可以有重复元素
S.insert(), MS.insert();
S.find(), MS.find();
S.count(), MS.count();
S.erase();
(1) 输入是一个数,删除所有x这个数 O(k + log(n))
(2) 输入是一个迭代器,删除迭代器
lower_bound(x); //返回大于等于x的最小的数的迭代器
upper_bound(x); //返回大于x的最小的数
map & multimap 维护有序序列
insert() 插入的数是一个pair
erase() 输入的参数是一个pair或者迭代器
find()
时间复杂度 O(logn)
begin() / end() ++ --
unordered_map & unordered_set
与上面类似,好处是所有增删改查的时间复杂度是O(1)
缺点:不支持lower_bound
, upper_bound
,迭代器的 ++
--
bitset 压位
- C++中的
bool
是一个字节,长度为1024的bool
数组需要1024字节,即1kB
的内存 - 若每一个字节存8位,则只需128个字节
- 只需使用1/8的空间
bitset<10000> S; //定义长度为10000的bitset
~ & | ^ //支持所有位运算操作
>> << //支持移位操作
== !=
[]
count() //返回有多少个1
any() //判断是否至少有一个1
none() //判断是否全为0
set() //把所有位置为1
set(k, v) //把第k位置为1
reset() //把所有位变成0
flip() //等价于~
flip(k) //把第k位取反
秀秀秀
666