【算法设计与分析】2.常见STL总结-创新互联

定义

setname;

  set翻译为集合，是一个内部自动有序且不含重复元素的容器。

元素访问
  注意，由于除了vector和string之外的STL容器都不支持*(it+i)的访问方式，所以只能按以下方式枚举：

#include#includeusing namespace std;
int main()
{setst;
	st.insert(3);
	st.insert(5);
	st.insert(2);
	st.insert(3);
	for (set::iterator it = st.begin(); it != st.end(); it++)
	{cout<< *it<< endl; //2 3 5
	}
	return 0;
}

  可以发现，set内的元素自动递增排序，且自动去除了重复的元素。

insert()
  insert(x)可以将x插入到set容器中，并且自动排序和去重，时间复杂度为 O ( log ⁡ N ) O(\log N) O(logN)，N为元素个数。

find()
  find(value)返回set中对应值为value的迭代器，时间复杂度为 O ( log ⁡ N ) O(\log N) O(logN)。若不存在，则返回st.end()

#include#includeusing namespace std;
int main()
{setst;
	for (int i = 1; i<= 3; i++)
	{st.insert(i);
	}
	set::iterator it = st.find(2);
	cout<< *it<< endl;
	it = st.find(4);
	if (it == st.end())
	{cout<< "Not found"<< endl;
	}
	return 0;
}

erase()
  1.删除单个元素：st.erase(it)，it为所需要删除元素的迭代器，可结合find()函数实现，时间复杂度 O ( 1 ) O(1) O(1)。或者st.erase(value)，value为所需要元素的值，时间复杂度 O ( log ⁡ N ) O(\log N) O(logN)。

st.erase(st.find(100));
st.erase(100);

  2.删除一个区间内的所有元素：st.erase(first,last)，first为所需要删除区间的起始迭代器，last为所需要删除区间的末尾迭代器的下一个地址。

st.erase(st.find(100),st.end());//删除元素30到末尾之间的元素

size()
  获取set内元素的个数，时间复杂度 O ( 1 ) O(1) O(1)。

clear()
  清空set中所有的元素，时间复杂度 O ( N ) O(N) O(N)。

主要用途

1. 自动去重并按升序排序。
2. set中元素唯一，如果遇到不唯一的情况，需要使用multiset。
3. C++11添加了unordered_set，使其去重但不排序，速度比set快很多。

定义

#include//注意string和string.h是不一样的头文件
string str;
string str="abcd";

元素访问

1. 元素下标

string str="abcd";
cout<

2. 迭代器

string::iterator it;
string str="abcd";
for(it=str.begin();it!=str.end();it++)
{cout<<*it;
}

operatpr+=
  string的加法，可以将string直接拼接起来。

string str1="abc";
string str2="def";
string str3=str1+str2;//将str1和str2拼接，赋给str3
str1+=str2;//将str2直接拼接到str1上

compare operator
  两个string类型可以直接使用==,!=,<,<=,>,>=比较大小，比较顺序是字典序。

#include#includeusing namespace std;
int main()
{string str1 = "aa";
	string str2 = "aaa";
	string str3 = "abc";
	string str4 = "xyz";
	if (str1< str2) cout<< "ok1"<< endl;//ok1
	if (str1 != str3) cout<< "ok2"<< endl;//ok2
	if (str4 >= str3) cout<< "ok3"<< endl;//ok3
	return 0;
}

length()/size()
  length()返回字符串存放的字符数，时间复杂度为 O ( 1 ) O(1) O(1)，size()与其用法基本相同。

insert()

1. insert(pos,string)，在pos号位置插入字符串string，时间复杂度 O ( N ) O(N) O(N)。

string str="abcxyz",str2="opq";
str.insert(3,str2);
cout<

2. insert(it,it1,it2)，it为原字符串欲插入的位置，it2和it3为待插字符串的首尾迭代器，用来表示串[it2,it3)将被插在it的位置上，时间复杂度 O ( N ) O(N) O(N)。

string str1="abcxyz",str2="opq";
str1.insert(str1.begin()+3,str2.begin(),str2.end());//abcopqxyz

erase()

1. erase(it)，删除单个元素，it为元素的迭代器，时间复杂度 O ( N ) O(N) O(N)。
2. erase(first,last)，删除区间内的元素，时间复杂度 O ( N ) O(N) O(N)。
3. erase(pos,length)，pos为需要删除的起始位置，length为要删除的长度，时间复杂度 O ( N ) O(N) O(N)。

clear()
  清空string中的所有元素，时间复杂度 O ( 1 ) O(1) O(1)。

substr()
  substr(pos,len)返回从pos开始，长度为len的子串，时间复杂度为 O ( l e n ) O(len) O(len)

string::npos
  它是一个常数，值为-1，用作find函数失配时的返回值。

find()
  str1.find(str2)，当str2时str1的子串时，返回其在str中第一次出现的位置，否则返回string::npos。
str1.find(str2,pos)从str1的pos号开始匹配，返回值同上。时间复杂度 O ( m n ) O(mn) O(mn)，m和n分别是str1和str2的长度。

replace()
  str1.replace(pos,len,str2)把str1从pos号位置开始，长度为len的子串替换为str2。
str1.replace(it1,it2,str2)把str1的迭代器[it1,it2)范围的子串替换为str2。

#include#includeusing namespace std;
int main()
{string str1 = "abcxyz";
	string str2 = "opq";
	str1.replace(3, 4, str2);
	cout<< str1<< endl;//abcopq
	str1.replace(str1.begin() + 1, str1.end(), str2);
	cout<< str1<< endl;//aopq
}

mapmp;

mapmp;
mp['c']=20;
mp['c']=30;

#include#include

queuename;

#include#includeusing namespace std;
int main()
{queueq;
	for (int i = 1; i<= 5; i++)
	{q.push(i);//将i入队
	}
	cout<< q.front()<< endl;//1
	cout<< q.back()<< endl;//5
	return 0;
}

priority_queuename;

#include#includeusing namespace std;
int main()
{priority_queueq;
	q.push(3);
	q.push(4);
	q.push(1);
	cout<< q.top()<< endl;//4
	return 0;	
}

priority_queueq;
priority_queue,less>;
priority_queue,greater>;

struct fruit
{string name;
	int price;
}

struct fruit
{string name;
	int price;
	friend bool operator< (fruit f1,fruit f2)
	{return f1.price< f2.price;//价格高优先级高
	}
}

struct fruit
{string name;
	int price;
	friend bool operator< (fruit f1,fruit f2)
	{return f1.price >f2.price;//价格低优先级高
	}
}

struct cmp
{bool operator () (fruit f1,fruit f2)
	{return f1.price< f2.price;
    {}

priority_queue,cmp>p;

stackname;

#includepairname;

mapmp;
mp.insert(make_pair("heihei",5));
mp.insert(pair("haha",10));