STL

STL算法

1、sort：排序

2、unique函数：一般用于sort后，清楚掉排序后重复的记录，使记录唯一。

3、find：查找一个记录。

4、unique_copy：可以将一个list对象中不重复的元素赋值到一个空的vector对象中。

5、find_first_of：第一段范围内查找与第二段范围中任意元素匹配的元素，然后返回一个迭代器，指向第一个匹配的元素。如果找不到匹配元素，则返回第一个范围的end迭代器。可以用于统计两个迭代器中重复的的元素个数。

6、copy:将一个迭代器中的元素复制到另一个迭代器中。

7、accumulate:可以用于统计vector元素之和。

find_if() 自定义比较函数
std::find_if():从给定区间中找出满足比较函数的第一个元素；
示例,从myvector中查找能够被30整除的第一个元素：

-Cpp 代码
1
bool cmpFunction (int i) {
2
return ((i%30)==0);
3
}
4
it = std::find_if (myvector.begin(), myvector.end(), cmpFunction);
5
std::cout << “first:” << *it <<std::endl;
count() 统计元素出现次数
std::count()：统计区间中某个元素出现的次数；
std:count_if()：count()的自定义比较函数版本

search_n() 查询单个元素重复出现的位置
search_n(): find用来查询单个元素，search_n则用来查找区间中重复出现n次的元素；

示例：查询myvector中30连续出现2次的位置：

-Cpp 代码
1
int myints[]={10,20,30,30,20,10,10,20};
2
std::vector myvector (myints,myints+8);
3
it = std::search_n (myvector.begin(), myvector.end(), 2, 30);
search_n() 支持自定义比较函数；

adjacent_find() 查询区间中重复元素出现的位置
adjacent_find() 查询区间中重复元素出现的位置，该算法支持自定义比较函数；

lower_bound() 有序区间中查询元素边界
lower_bound()用来在一个排序的区间中查找第一个不小于给定元素的值：
示例：查找容器v中不小于20的下界：

-Cpp 代码
1
int myints[] = {10,20,30,30,20,10,10,20};
2
std::vector v(myints,myints+8); // 10 20 30 30 20 10 10 20
3
std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
4
std::vector::iterator low,up;
5
low=std::lower_bound (v.begin(), v.end(), 20);
6
std::cout << "lower_bound at position " << (low- v.begin()) << ‘\n’;
类似算法有upper_bound(),查找有序区间中第一个大于给定元素的值；
还有equal_range(),查找有序区间的上下边界；（一次返回lower_bound()和upper_bound());

binary_search() 有序区间的二分查找
binary_search() 用来在一个有序区间中使用二分法查找元素是否在这个区间中，注，这个算法的返回值为bool，
不是下标位置，其内部的算法逻辑和lower_bound（）相似，行为表现为：

-Cpp 代码
1
template <class ForwardIterator, class T>
2
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
3
{
4
first = std::lower_bound(first,last,val);
5
return (first!=last && !(val<*first));
6
}
示例：从有序区间v中找3是否存在：

-Cpp 代码
1
int myints[] = {1,2,3,4,5,4,3,2,1};
2
std::vector v(myints,myints+9); // 1 2 3 4 5 4 3 2 1
3
std::sort (v.begin(), v.end());
4
if (std::binary_search (v.begin(), v.end(), 3))
5
std::cout << “found!\n”; else std::cout << “not found.\n”;
min_element() 查找最小元素
min_element() 在给定区间中查找出最小值;

-Cpp 代码
1
int myints[] = {3,7,2,5,6,4,9};
2
std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << ‘\n’;
类似算法有：max_element() 查找最大值；

区间查找 search()
search() 查找子区间首次出现的位置
find()用来查找单个元素，search()则用来查找一个子区间；
示例：从myvector中查找出现子区间[20，30]的位置:

-Cpp 代码
1
int needle1[] = {20,30};
2
it = std::search (myvector.begin(), myvector.end(), needle1, needle1+2);
3
if (it!=myvector.end())
4
std::cout << "needle1 found at position " << (it-myvector.begin()) << ‘\n’;
search支持自定义比较函数；
示例：查询给定区间中每个元素比目标区间小1的子区间；

-Cpp 代码
1
bool cmpFunction (int i, int j) {
2
return (i-j==1);
3
}
4
int myints[] = {1,2,3,4,5,1,2,3,4,5};
5
std::vector haystack (myints,myints+10);
6

7
int needle2[] = {1,2,3};
8
// using predicate comparison:
9
it = std::search (haystack.begin(), haystack.end(), needle2, needle2+3, cmpFunction);
find_end() 查找子区间最后一次出现的位置
search() 用来查找子区间第一次出现的位置，而find_end()用来查找子区间最后一次出现的位置：
find_end()支持自定义比较函数；

equal() 判断两个区间是否相等
equal（）用来判断两个区间是否相等，该算法支持自定义比较函数；

mismatch() 查询两个区间首次出现不同的位置；
mismatch() 查询两个区间首先出现不同的位置，这个算法也支持自定义比较函数；
8、equal:两个vector，一段区间所有元素都相等，则返回true。

9、mismatch:返回两个vector第一个不相等的位置。

STL容器

//list

list i_list;
for (int i = 1; i < 5; i++)
{
i_list.push_back(i);
}
list::iterator it = i_list.begin();
while (it != i_list.end())
{
cout << *it++ << endl;
}

list 容器常用方法

begin()和end()：：l_list.begin()得到一个指向容器起始位置的iterator。可以调用list容器的 end() 函数来得到list末端下一位置

push_back() && push_front()：在尾部或者在头部插入元素

pop_back(） && pop_front() ：从尾部或者头部获得元素

clear()：清空list链表

assign()：list.assign(list2.begin(),list2.end());将list2的元素复制到list1 中

swap()：交换两个链表 list1.swap(list2);swap(list1,list2);

reverse()：将链表逆序；

merge()：合并两个链表，并默认是升序。list1.merge(list2,greater());list2被清空

insert()：在指定位置插入一个或多个元素。

i_list.insert(i_list.end(), 100);

i_list.insert(i_list.begin(),2, 90);//在起始位插入两个99
i_list.insert(i_list.begin(),i_list2.begin(),i_list2.end());//将list2的元素插入list1的首部

erase()：删除一个元素或者部分元素

i_list.erase(i_list.begin());

i_list.erase(i_list.begin(),i_list.end());

//vector :常见方法及使用

vector创建方式：

vector V;//创建一个空的

vector v(v1);//复制一个vector

vector v(n);//创建一个含有n个数据的vector，数据由构造函数产生

vector v(n, elem) //创建一个含有n个elem拷贝的vector。
vector v(beg, end) //创建一个以[beg; end)区间的vector。
v.~vector () //销毁所有数据，释放内存。

vector 常见使用方法同list

set 与 map 中不同的方法

//iterator lower_bound (const value_type& val) const;

若value在set中，返回的是value第一次出现的迭代器

//iterator upper_bound (const value_type& val) const;

若value在set中，返回的是value元素的下一个元素的迭代器

若value不在set中，两者返回的是第一个 >value的迭代器

s.insert(1);
s.insert(5);
s.insert(6);
cout << *s.lower_bound(2) << endl;//5
cout << *s.lower_bound(3) << endl;//5
cout << *s.upper_bound(3) << endl;//5
return 0;

map 使用

map<int, string> m_map;

//插入元素（第一种方式）
m_map.insert( pair<int, string>(1, “hua”) );
m_map.insert( pair<int, string>(2, “wei”) );

//或者（第二种方式）

m_map.insert( map<int,string>::value_type(1,“hua”) );
m_map.insert( map<int,string>::value_type(2,“wei”) );

//亦或者（第三种方式）

map<int, string> mapStudent;
mapStudent[1] = “one”;(key:1,value:one)
mapStudent[3] = “two”;
mapStudent[4] = “three”;

应用第三种方式插入元素的时候，若关键字已经存在，是可以实现将之前的元素覆盖的功能的，而前两种方式不可以

//遍历：正向
map<int, string>::iterator it = m_map.begin();
while (it != m_map.end())
{
cout << it->first << it->second << endl;
*it++;
}

map<int, string>::const_iterator c_iter;
for (c_iter = mapStudent.cbegin(); c_iter != mapStudent.cend(); c_iter++)
cout << c_iter->first << ’ ’ << c_iter->second << endl;

//遍历：反向

map<int, string>::reverse_iterator r_iter;
for (r_iter = mapStudent.rbegin(); r_iter != mapStudent.rend(); r_iter++)
cout << r_iter->first << ’ ’ << r_iter->second << endl;