set
#include <bits/stdc++.h>
using namespace std;
int main()
{
set<int> s;//声明一个存放int的set,名字为s
s.insert(5);//向s中加入5,当前s中的元素为[5],时间复杂度为O(logn)
s.insert(1);//向s中加入1,当前s中的元素为[1,5],时间复杂度为O(logn)
s.insert(6);//向s中加入6,当前s中的元素为[1,5,6],时间复杂度为O(logn)
s.insert(6);//向s中加入6,当前s中的元素为[1,5,6],时间复杂度为O(logn),
因为s会自动去重排序
所以s中的元素不变
//让我来输出一下s中的元素吧
for (auto it = s.begin(); it != s.end();it++)
{
cout << *it << '\n';//*表示输出it所指向的那个位置的元素
}
cout << '\n';
cout << s.size() << '\n';//输出s的大小
cout << s.empty() << '\n';//返回s是否为空
auto it= s.find(101);//在s中查找101并且返回指向101的迭代器,
如果没找到会返回s.end(),
时间复杂度为O(logn)
if(it!=s.end())
{
cout << "s have " << 101 << '\n';
}
else
{
cout << "s don't have " << 101 << '\n';
}
it= s.find(6);//在s中查找6并且返回指向6的迭代器,
如果没找到会返回s.end(),时间复杂度为O(logn)
if(it!=s.end())
{
cout << "s have " << 6 << '\n';
}
else
{
cout << "s don't have " << 6 << '\n';
}
s.erase(it);//删除it指向的位置,这里就是删除6,时间复杂度为O(logn)。
需要注意的是千万不要删s.end()这个位置,会RE,时间复杂度为O(logn)
s.insert(99);//现在s是[1,5,99]
it=s.lower_bound(5); //返回指向第一个大于等于5的元素的迭代器,
如果没有返回s.end(),时间复杂度为O(logn)
cout << *it << '\n';
it=s.upper_bound(5); //返回指向第一个大于5的元素的迭代器,
如果没有返回s.end(),时间复杂度为O(logn)
cout << *it << '\n';
s.clear();//清空s,时间复杂度为O(n)
return 0;
}
map
#include <bits/stdc++.h>
using namespace std;
int main()
{
map<string, int> mp;///声明一个下标为string,值为int的map,名字为mp。
//这里我们赋予mp一些意义,表示人的姓名映射到人的智商
//我们插入智商为180的myj
mp["myj"] = 180;//这样mp里面就记录了myj的智商为180,时间复杂度为O(logn)
cout << mp["myj"] << '\n'; //查询myj的智商,时间复杂度为O(logn)
cout << mp.count("zr") << '\n';//查询mp中是否含有下标"zr",
如果不确定里面是否含有,一定要这样查询,时间复杂度为O(logn)
//cout<<mp["zr"]<<'\n';
//如果这样直接查询为得到0,有的同学会想如果是0那就说明没有呗,没必要用count。
这样显然不对!万一zr的智商就是0呢,你就无法判断是不存在还是真的为0
//还会引发一个更致命的问题,这样查询会向mp里面添加元素,
多次查询可能会炸空间,不信的话你试试。
cout << mp.size() << '\n';//输出mp的大小,时间复杂度为O(1)
cout << mp.empty() << '\n';//输出mp是否为空,时间复杂度为O(1)
mp["zr"] = 5;//继续添加元素
//遍历mp
for (auto it = mp.begin(); it != mp.end();it++)
{
///这里it->first表示下标,it->second表示值
cout << it->first << ' ' << it->second << '\n';
//cout << (*it).first << ' ' << (*it).second << '\n';//这种写法也可以
}
auto it=mp.lower_bound("mya");//查询mp下标中大于等于"mya"的第一元素,
返回其迭代器,时间复杂度为O(logn)。
因为这里下标是string所以按照字典序排序的话,mya <myj <zr
cout << it->first << ' ' << it->second << '\n';
// mp.upper_bound();同上,只不过不是"大于等于"而是"大于"
mp.clear();//清空mp,时间复杂度为O(n)
return 0;
}
queue
#include <bits/stdc++.h>
using namespace std;
int main()
{
queue<int> q;//声明一个存放int的队列,名字为q
q.push(1);//队尾插入一个1,此时队列为[1],时间复杂度为O(1)
q.push(2);//队尾插入一个2,此时队列为[1,2],时间复杂度为O(1)
q.push(100);//队尾插入一个100,此时队列为[1,2,100],时间复杂度为O(1)
cout << q.front() << '\n';//front()返回队首元素
队列不改变,仍然为[1,2,100],时间复杂度为O(1)
q.pop();//弹出队首,此时队列为[2,100],时间复杂度为O(1),
大家对比一下vector删除第一个元素的复杂度。
cout << q.size() << '\n';//返回队列中元素的个数,时间复杂度为O(1)
cout << q.empty() << '\n';//返回一个bool量表示队列是否为空
//队列没有clear的方法,需要这样清空
while(!q.empty())//只要队列不为空
q.pop();//弹出队首元素
//
cout << q.size() << '\n';
//队列不能用[]索引,q[1]这种写法是错误的!
return 0;
}
string
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;//声明一个string ,名字为s
s = "myj";//将"myj"赋值给s
s = s + " "; //在s的后面加上一个空格,现在s为"myj ",
时间复杂度为O(新的字符串的长度)
s += "nb";//在s的后面加上一个"nb",现在s为"myj nb",
时间复杂度为O(要加上的字符串的长度)
cout << s<<'\n';//string 可以直接使用cout输出,
也可以用cin直接输入
printf("%s\n", s.c_str()); //用printf输出要这样写,
记住即可,将来你会明白的
cout << s.substr(4, 2) << '\n';//取s的子串,
从下标为4的地方开始向后取2个字符,结果应为"nb"
string a = s;//声明一个新的string,名字为a,并将s赋值给a,
此时a为"myj nb",时间复杂度为O(n),
注意char 数组不能这样直接赋值!
a.replace(0,3, "zr");//把从下标0开始的连续3个字符替换为"zr",
现在a为"zr nb",时间复杂度为O(n)
if(s<a)//string可以直接按照字典序比较大小,
字典序很好理解,你就假设字典里面有这两个单词,
那个在前面,
那个就更小。显然"myj nb"<"zr nb"。
{
cout << s << '<' << a << '\n';
}
else if(s>a)
{
cout << s << '>' << a << '\n';
}
else
{
cout << s << '=' << a << '\n';
}
//对s进行遍历,这里我们输出s的奇数下标
//myj nb
//012345
//取奇数小标结果就是"y b"
for (int i = 0; i < (int)s.length();i++)//s/length()返回的是字符串长度,
写(int)是一个好习惯,
相信我有时候会救你。
{
if(i%2==1) cout << s[i];
}
cout << '\n';
//
s.clear(); //清空s,现在s为"",时间复杂度通常为O(1)
//现在a为"zr nb",但是众所周知zr是个菜鸡,所以我们想把"zr nb"变成"zr is sb"
//这里提供一种办法(其实有一万种方法)
a.erase(3, 1);//把从下标3开始的连续1个字符删除,现在s为"zr b",时间复杂度为O(n)
a.insert(3, "is s");//在下标3前面插入"is s",现在s为"zr is sb",时间复杂度为O(n)
cout << a << '\n';
return 0;
}
vector
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> a;//声明一个装int的vector,vector的名字是a
//vector<double> b;//声明一个装double的vector,vector的名字是b
a.push_back(1);//在a的末尾装入1,当前的a是[1],时间复杂度O(1)
a.push_back(2);//在a的末尾装入2,当前的a是[1,2]
a.push_back(3);//在a的末尾装入3,当前的a是[1,2,3]
cout << a.size() << '\n';//输出a的大小,结果为3,时间复杂度O(1)
cout << a[1] << '\n';//输出a[1]的值,vector和数组一样可以用[]来访问其中的元素
//让我们输出整个vector中的元素,看看和预期是否相同
for (int i = 0; i < (int)a.size();i++)//相信我,加这个int有时会救你
{
cout << a[i] << ' ';
}
cout << '\n';
//接下来的操作大家自行输出vector验证
a.erase(a.begin() + 1)
;//删除a[1],当前的a是[1,3],时间复杂度O(n)
a.erase(a.begin() + 1);
//删除a[1],当前的a是[1]
//
a.insert(a.begin() + 0, 100);
//在a[0]前面插入100,当前的a是[100,1],时间复杂度O(n)
a.insert(a.begin() + 1, 99);
//在a[1]前面插入99,当前的a是[100,99,1]
//
sort(a.begin(), a.end());
//对整个vector进行排序,当前的a是[1,99,100],时间复杂度O(n*logn)
reverse(a.begin(), a.end());
//翻转整个vector,当前a是[100,99,1],时间复杂度O(n)
//用迭代器进行遍历,输出vector
vector<int>::iterator itt; //声明一个指向vector<int>容器的迭代器
for (itt = a.begin(); itt != a.end();itt++)
{
cout << *itt << ' ';
}
cout << '\n';
//
sort(a.begin(), a.end());
//auto为自动类型,会根据右边的类型自动声明左边的类型
,避免了迭代器的繁琐声明
//如果在这里编译报错,请打开C++11标准
auto it=lower_bound(a.begin(), a.end(), 99);
//查找大于等于99的第一个元素,并返回指向它的迭代器,时间复杂度O(logn)
cout << *it << '\n';
it=upper_bound(a.begin(), a.end(), 99);
//查找大于99的第一个元素,并返回指向它的迭代器,
时间复杂度O(logn)
cout << *it << '\n';
a.clear();///清空vector,此时a为[],时间复杂度O(n)
/*
使用lower_bound 和upper_bound之前一定要把vector从小到大排序!!!!!!
使用lower_bound 和upper_bound之前一定要把vector从小到大排序!!!!!!
使用lower_bound 和upper_bound之前一定要把vector从小到大排序!!!!!!
*/
a.push_back(1); //此时a为[1],时间复杂度O(1)
a.pop_back();//删除最后一个元素,此时a为[],时间复杂度O(1)
cout << a.size() << '\n';
return 0;
}
stack
#include <bits/stdc++.h>
using namespace std;
int main()
{
stack<int> s;//声明一个存放int的栈,名字为s
s.push(1);//栈顶放入一个1,此时栈为[1],时间复杂度为O(1)
s.push(2);//栈顶放入一个2,此时栈为[1,2],时间复杂度为O(1)
s.push(100);//栈顶放入一个100,此时栈为[1,2,100],时间复杂度为O(1)
cout << s.top() << '\n';//top()返回栈顶元素,栈不改变,
仍然为[1,2,100],时间复杂度为O(1)
s.pop();//弹出栈顶,此时栈为[1,2],时间复杂度为O(1),
大家可以对比vector删除最后一个元素的复杂度
cout << s.size() << '\n';//返回栈中元素的个数,时间复杂度为O(1)
cout << s.empty() << '\n';//返回一个bool量表示栈是否为空
//栈没有clear的方法,需要这样清空
while(!s.empty())//只要栈不为空
s.pop();//弹出栈顶元素
//
cout << s.size() << '\n';
//栈不能用[]索引,s[1]这种写法是错误的!
return 0;
}