文档章节

C++ STL 总结

吃一堑消化不良
 吃一堑消化不良
发布于 2016/10/19 10:13
字数 5420
阅读 126
收藏 8

一、STL的六大组件

1、容器(Container),是一种数据结构,如list,vector,和deques ,以模板类的方法提供。为了访问容器中的数据,可以使用由容器类输出的迭代器;
2、迭代器(Iterator),提供了访问容器中对象的方法。例如,可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上,C++的指针也是一种迭代器。但是,迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符地方法的类对象;
3、算法(Algorithm),是用来操作容器中的数据的模板函数。例如,STL用sort()来对一个vector中的数据进行排序,用find()来搜索一个list中的对象,函数本身与他们操作的数据的结构和类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用;
4、仿函数(Function object,又称之为函数对象(function object)),其实就是重载了()操作符的struct,没有什么特别的地方
5、迭代适配器(Adaptor)
6、空间配制器(allocator),其中主要工作包括两部分:对象的创建与销毁、内存的获取与释放

以下主要讨论:容器,迭代器,算法,适配器:

二、STL容器

1、序列式容器(Sequence containers),每个元素都有固定位置——取决于插入时机和地点,和元素值无关,vectordequelist

   Vectors:将元素置于一个动态数组中加以管理,可以随机存取元素(用索引直接存取),数组尾部添加或移除元素非常快速。但是在中部或头部安插元素比较费时;

   Deques:是“double-ended queue”的缩写,可以随机存取元素(用索引直接存取),数组头部和尾部添加或移除元素都非常快速。但是在中部或头部安插元素比较费时;

   Lists:双向链表,不提供随机存取(按顺序走到需存取的元素,O(n)),在任何位置上执行插入或删除动作都非常迅速,内部只需调整一下指针;

2、关联式容器(Associated containers),元素位置取决于特定的排序准则,和插入顺序无关,setmultisetmapmultimap

   Sets/Multisets:内部的元素依据其值自动排序,Set内的相同数值的元素只能出现一次,Multisets内可包含多个数值相同的元素,内部由二叉树实现(实际上基于红黑树(RB-tree)实现),便于查找;

   Maps/Multimaps:Map的元素是成对的键值/实值,内部的元素依据其值自动排序,Map内的相同数值的元素只能出现一次,Multimaps内可包含多个数值相同的元素,内部由二叉树实现(实际上基于红黑树(RB-tree)实现),便于查找;

另外有其他容器hash_maphash_sethash_multisethash_multimap

三、STL迭代器 

Iterator(迭代器)模式又称Cursor(游标)模式,用于提供一种方法顺序访问一个聚合对象中各个元素, 
而又不需暴露该对象的内部表示。

常见的一些迭代器类型:iteratorconst_iteratorreverse_iteratorconst_reverse_iterator

1、迭代器的使用方法

1)序列式容器(Sequence containers)

std::vector<int> Vec; 
std::vector<int>::iterator itVec; 
for( itVec = Vec.begin(); itVec != Vec.end(); ) 
{ 
    if( WillDelete( *itVec) ) 
    { 
        itVec = Vec.erase(itVec); 
    } 
    else 
        itList++; 
}

序列式容器(vector、deque)删除当前的iterator会使后面所有元素的iterator都失效。这是因为vetor,deque使用了连续分配的内存,删除一个元素导致后面所有的元素会向前移动一个位置。还好erase方法可以返回下一个有效的iterator。 

对于list来说,它使用了不连续分配的内存,并且它的erase方法也会返回下一个有效的iterator,因此关联式容器的两种方法都可以使用。

2)关联式容器(Associated containers)

std::list<int> List; 
std::list<int>::iterator itList; 
for( itList = List.begin(); itList != List.end(); ) 
{ 
    if( WillDelete( *itList) ) 
    {
        //方法1
        itList = List.erase(itList); 
        //方法2
        List.erase( itList++ ); 
    } 
    else 
        itList++; 
}

关联容器删除当前的iterator,仅仅会使当前的iterator失效,只要在erase时,递增当前iterator即可。这是因为map之类的容器,使用了红黑树来实现,插入、删除一个结点不会对其他结点造成影响。 

2、迭代器失效

1)vector 

内部数据结构:数组。 
随机访问每个元素,所需要的时间为常量。 
在末尾增加或删除元素所需时间与元素数目无关,在中间或开头增加或删除元素所需时间随元素数目呈线性变化。 
可动态增加或减少元素,内存管理自动完成,但程序员可以使用reserve()成员函数来管理内存。 
vector的迭代器在内存重新分配时将失效(它所指向的元素在该操作的前后不再相同)。当把超过capacity()-size()个元素插入vector中时,内存会重新分配,所有的迭代器都将失效;否则,指向当前元素以后的任何元素的迭代器都将失效。当删除元素时,指向被删除元素以后的任何元素的迭代器都将失效。 

2)deque 

内部数据结构:数组。 
随机访问每个元素,所需要的时间为常量。 
在开头和末尾增加元素所需时间与元素数目无关,在中间增加或删除元素所需时间随元素数目呈线性变化。 
可动态增加或减少元素,内存管理自动完成,不提供用于内存管理的成员函数。 
增加任何元素都将使deque的迭代器失效。在deque的中间删除元素将使迭代器失效。在deque的头或尾删除元素时,只有指向该元素的迭代器失效。 

3)list 

内部数据结构:双向环状链表。 
不能随机访问一个元素,可双向遍历。 
在开头、末尾和中间任何地方增加或删除元素所需时间都为常量。 
可动态增加或减少元素,内存管理自动完成。 
增加任何元素都不会使迭代器失效。删除元素时,除了指向当前被删除元素的迭代器外,其它迭代器都不会失效。 

4)slist 

内部数据结构:单向链表。 
不可双向遍历,只能从前到后地遍历,其它的特性同list相似。 

5)stack 

适配器,它可以将任意类型的序列容器转换为一个堆栈,一般使用deque作为支持的序列容器。 
元素只能后进先出(LIFO),不能遍历整个stack。 

6)queue 

适配器,它可以将任意类型的序列容器转换为一个队列,一般使用deque作为支持的序列容器。 
元素只能先进先出(FIFO),不能遍历整个queue。

7)priority_queue 

适配器,它可以将任意类型的序列容器转换为一个优先级队列,一般使用vector作为底层存储方式。 
只能访问第一个元素,不能遍历整个priority_queue,第一个元素始终是优先级最高的一个元素。

8)set 

键和值相等,键唯一。 
元素默认按升序排列。 
如果迭代器所指向的元素被删除,则该迭代器失效。其它任何增加、删除元素的操作都不会使迭代器失效。

9)multiset 

键可以不唯一,其它特点与set相同。 

10)hash_set 

与set相比较,它里面的元素不一定是经过排序的,而是按照所用的hash函数分派的,它能提供更快的搜索速度(当然跟hash函数有关),其它特点与set相同。 

11)hash_multiset 

键可以不唯一,其它特点与hash_set相同。 

12)map 

键唯一,元素默认按键的升序排列。 
如果迭代器所指向的元素被删除,则该迭代器失效。其它任何增加、删除元素的操作都不会使迭代器失效。

13)multimap 

键可以不唯一,其它特点与map相同。 

14)hash_map 

与map相比较,它里面的元素不一定是按键值排序的,而是按照所用的hash函数分派的,它能提供更快的搜索速度(当然也跟hash函数有关),其它特点与map相同。 

(15)hash_multimap 

键可以不唯一,其它特点与hash_map相同。 

四、STL算法

STL算法部分主要由头文件<algorithm>,<numeric>,<functional>组成。要使用 STL中的算法函数必须包含头文件<algorithm>,对于数值算法须包含<numeric>,<functional>中则定义了一些模板类,用来声明函数对象。

以下对所有算法进行细致分类并标明功能:

1、查找算法(13个):判断容器中是否包含某个值

//在iterator对标识元素范围内,查找一对相邻重复元素,找到则返回指向这对元素的第一个元素的ForwardIt
//否则返回last。重载版本使用输入的二元操作符代替相等的判断
ForwardIt adjacent_find(ForwardIt first, ForwardIt last);

//在有序序列中查找value,找到返回true。重载的版本实用指定的比较函数对象或函数指针来判断相等
boo binary_search(ForwardIt first, ForwardIt last, const T& value);

//利用等于操作符,把标志范围内的元素与输入值比较,返回相等元素个数
size_t count(ForwardIt first, ForwardIt last, const T& value);

//利用输入的操作符,对标志范围内的元素进行操作,返回结果为true的个数
size_t count_if(ForwardIt first, ForwardIt last, Predicate P);

//功能类似equal,返回一对iterator,第一个表示lower_bound,第二个表示upper_bound
pair<const_iterator,const_iterator> equal_range (const key_type& k) const; 

//利用底层元素的等于操作符,对指定范围内的元素与输入值进行比较
//当匹配时,结束搜索,返回该元素的一个InputIterator
ForwardIt find (ForwardIt first, ForwardIt last, const T& val);

//在指定范围内查找"由输入的另外一对iterator标志的第二个序列"的最后一次出现
//找到则返回最后一对的第一个ForwardIterator,否则返回输入的"另外一对"的第一个ForwardIt
//重载版本使用用户输入的操作符代替等于操作
ForwardIt find_end(ForwardIt first1, ForwardIt last, ForwardIt first2, ForwardIt last2);

//在指定范围内查找"由输入的另外一对iterator标志的第二个序列"中任意一个元素的第一次出现
//重载版本中使用了用户自定义操作符
ForwardIt find_first_of(ForwardIt _First1, ForwardIt _Last1
                       ,ForwardIt _First2, ForwardIt _Last2);

//使用输入的函数代替等于操作符执行find
InputIterator find_if(ForwardIt first, ForwardIt last, Predicate pred); 

//返回一个非递减序列[first, last)中的第一个大于等于值val的位置
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const _Tp& val);

//返回的是最后一个大于等于val的位置,也是有一个新元素val进来时的插入位置           
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const _Tp& val);

//给出两个范围,返回一个ForwardIt ,查找成功指向第一个范围内第一次出现子序列(第二个范围)的位置
//查找失败指向last1。重载版本使用自定义的比较操作
ForwardIt search(ForwardIt _First1, ForwardIt _Last1, ForwardIt _First2, ForwardIt _Last2);

//在指定范围内查找val出现n次的子序列。重载版本使用自定义的比较操作。
ForwardIt search_n ( ForwardIt first, ForwardIt last, Size count, const T& value );

2、排序和通用算法(14个):提供元素排序策略

//合并两个有序序列,存放到另一个序列。重载版本使用自定义的比较。
OutputIt merge(InputIt first1, InputIt last1, InputIt first2, InputIt last2,OutputIt result);

//合并两个有序序列,结果序列覆盖两端范围。重载版本使用输入的操作进行排序。
void inplace_merge(InputIt first, InputIt middle, InputIt last);

//将范围内的序列重新排序,使所有小于第n个元素的元素都出现在它前面,而大于它的都出现在后面。
//重载版本使用自定义的比较操作。
void nth_element(InputIt first, InputIt middle, InputIt last);

//该函数是的将范围内最小的(middle-frist)个元素放到最前面并且排序
void partial_sort(InputIt first, InputIt middle, InputIt last);

//与partial_sort类似,不过将经过排序的序列复制到另一个容器
OutputIt partial_sort_copy(InputIt first, InputIt last, 
                           RandomIt result_first, OutputIt result_last);

//对指定范围内元素重新排序,使用输入的函数,把结果为true的元素放在结果为false的元素之前
OutputIt partition (InputIt first, InputIt last, UnaryPredicate pred);

//对指定范围内的元素随机调整次序。重载版本输入一个随机数产生操作
void random_shuffle (InputIt first, InputIt last);

//将指定范围内元素重新反序排序
void reverse (InputIt first, InputIt last);

//与reverse类似,不过将结果写入另一个容器
OutputIt reverse_copy (InputIt first, InputIt last, OutputIt result);

//将指定范围内元素移到容器末尾,由middle指向的元素成为容器第一个元素
void rotate (InputIt first, InputIt middle, InputIt last);

//与rotate类似,不过将结果写入另一个容器
OutputIt rotate_copy (InputIt first, InputIt middle, InputIt last, InputIt result);

//以升序重新排列指定范围内的元素,重载版本使用自定义的比较操作
void sort(InputIt first, InputIt last);

//与sort类似,不过保留相等元素之间的顺序关系
void stable_sort(InputIt first, InputIt last);

//与partition类似,不过保证保留容器中的相对顺序
OutputIt stable_partition (InputIt first, InputIt last, UnaryPredicate pred);

3、删除和替换算法(15个)

//复制序列
OutputIt copy(InputIt first, InputIt last, OutputIt result);

//与copy相同,不过元素是以相反顺序被拷贝
OutputIt copy_backward(InputIt first, InputIt last, OutputIt result);

//交换两个InputIt的值
void iter_swap(InputIt a, InputIt b);

//删除指定范围内所有等于指定元素的元素
//注意,该函数不是真正删除函数。内置函数不适合使用remove和remove_if函数
OutputIt remove (InputIt first, InputIt last, const T& val);

//将所有不匹配元素复制到一个制定容器,返回OutputIterator指向被拷贝的末元素的下一个位置
OutputIt remove_copy (InputIt first, InputIt last, OutputIt result, const T& val);

//删除指定范围内输入操作结果为true的所有元素
OutputIt remove_if (InputIt first, InputIt last, UnaryPredicate pred);

//将所有不匹配元素拷贝到一个指定容器
OutputIt remove_copy_if (InputIt first, InputIt last, OutputIt result, UnaryPredicate pred);

//将指定范围内所有等于old_value的元素都用new_value代替
void replace (InputIt  first, InputIt last, const T& old_value, const T& new_value);

//与replace类似,不过将结果写入另一个容器
OutputIt replace_copy (InputIt  first, InputIt  last,
                       OutputIt result, const T& old_value, const T& new_value);

//将指定范围内所有操作结果为true的元素用新值代替
void replace_if(InputIt first, InputIt last, UnaryPredicate pred, const T& new_value);

//与replace_if,不过将结果写入另一个容器
OutputIt replace_copy_if (InputIt first, InputIt last,
                          OutputIt result, UnaryPredicate pred, const T& new_value);

//交换存储在两个对象中的值
void swap (T& a, T& b);

//将指定范围内的元素与另一个序列元素值进行交换(这里已经默认这两个待交换区间的长度相等)
OutputIt swap_ranges(InputIt _First1, InputIt  _Last1, InputIt _First2);

//清除序列中重复元素,和remove类似,它也不能真正删除元素。重载版本使用自定义比较操作。
OutputIt unique (InputIt first, InputIt last);

//与unique类似,不过把结果输出到另一个容器。
OutputIt unique_copy (InputIt first, InputIt last, OutputIt result);

4、排列组合算法(2个):提供计算给定集合按一定顺序的所有可能排列组合

//取出当前范围内的排列,并重新排序为下一个排列,重载版本使用自定义的比较操作
bool next_permutation (InputIterator first, InputIterator last);

//取出指定范围内的序列并将它重新排序为上一个序列
//如果不存在上一个序列则返回false,重载版本使用自定义的比较操作
bool prev_permutation (InputIterator  first, InputIterator last);

5、算术算法(4个)

//iterator对标识的序列段元素之和,加到一个由val指定的初始值上
//重载版本不再做加法,而是传进来的二元操作符被应用到元素上
T accumulate(InputIt first, InputIt last, T init);

//创建一个新序列,其中每个元素值代表指定范围内该位置前所有元素之和。重载版本使用自定义操作代替加法
OutputIt partial_sum(InputIt first, InputIt last, OutputIt result);

//对两个序列做内积(对应元素相乘,再求和)并将内积加到一个输入的初始值上。重载版本使用用户定义的操作
T inner_product(InputIt first1, InputIt last1, InputIt first2, T init);

//创建一个新序列,新序列中每个新值代表当前元素与上一个元素的差。重载版本用指定二元操作计算相邻元素的差
OutputIt adjacent_difference (InputIt first, InputIt last, OutputIt result);

6、生成和异变算法(6个)

//将输入值赋给标志范围内的所有元素
void fill (InputIt first, InputIt last, const T& val);

//将输入值赋给first到first+n范围内的所有元素
void fill_n (OutputIt first, Size n, const T& val);

//用指定函数依次对指定范围内所有元素进行迭代访问,返回所指定的函数类型。该函数不得修改序列中的元素
Function for_each (InputIt first, InputIt last, Function fn);

//连续调用输入的函数来填充指定的范围
void generate (InputIt first, InputIt last, Generator gen);

//与generate函数类似,填充从指定iterator开始的n个元素
void generate_n (OutputIt first, Size n, Generator gen);

//将输入的操作作用于指定范围内的每个元素,并产生一个新的序列。
//重载版本将操作作用在一对元素上,另外一个元素来自输入的另外一个序列。结果输出到指定容器。
OutputIt transform (InputIt first, InputIt last, OutputIt result, UnaryOperation op);              

7、关系算法(8个)

//如果两个序列在标志范围内元素都相等,返回true。重载版本使用输入的操作符代替默认的等于操作符
bool equal(InputIt first1, InputIt last1, InputIt first2);

//判断第一个指定范围内的所有元素是否都被第二个范围包含,使用底层元素的<操作符,成功返回true
//重载版本使用用户输入的函数。
bool includes(InputIt first1, InputIt last1, InputIt first2, InputIt last2);

//比较两个序列,重载版本使用用户自定义比较操作
bool lexicographical_compare(InputIt first1, InputIt last1, InputIt first2, InputIt last2);

//返回两个元素中较大一个。重载版本使用自定义比较操作
const T& max(const T& a, const T& b);

//返回一个OutputIt,指出序列中最大的元素。重载版本使用自定义比较操作
OutputIt max_element(InputIt first, InputIt last);

//返回两个元素中较小一个,重载版本使用自定义比较操作
const T& min(const T& a, const T& b);

//返回一个ForwardIterator,指出序列中最小的元素,重载版本使用自定义比较操作
OutputIt min_element (InputIt first, InputIt last);         

//并行比较两个序列,指出第一个不匹配的位置,返回一对iterator,标志第一个不匹配元素位置
//如果都匹配,返回每个容器的last。重载版本使用自定义的比较操作
pair<InputIt, InputIt> mismatch (InputIt first1, InputIt last1, InputIt first2);

8、集合算法(4个)

//构造一个有序序列,包含两个序列中所有的不重复元素,重载版本使用自定义的比较操作
OutputIt set_union(InputIt first1, InputIt last1, InputIt first2, InputIt last2, OutputIt result);

//构造一个有序序列,其中元素在两个序列中都存在,重载版本使用自定义的比较操作
OutputIt set_intersection(InputIt first1, InputIt last1, InputIt first2, InputIt last2,
                          OutputIt result);

//构造一个有序序列,该序列仅保留第一个序列中存在的而第二个中不存在的元素。重载版本使用自定义的比较操作
OutputIterator set_difference(InputIt first1, InputIt last1, InputIt first2, InputIt last2,
                          OutputIt result);

//构造一个有序序列,该序列取两个序列的对称差集(并集-交集)
OutputIterator set_symmetric_difference(InputIt first1, InputIt last1, 
                                        InputIt first2, InputIt last2, OutputIt result);

9、堆算法(4个)

//把指定范围内的元素生成一个堆。重载版本使用自定义比较操作
void make_heap(InputIt first, InputIt last);

//并不真正把最大元素从堆中弹出,而是重新排序堆。它把first和last-1交换,然后重新生成一个堆
//可使用容器的back来访问被"弹出"的元素或者使用pop_back进行真正的删除,重载版本使用自定义的比较操作
void pop_heap(InputIt first, InputIt last);                

//假设first到last-1是一个有效堆,要被加入到堆的元素存放在位置last-1,重新生成堆
//在指向该函数前,必须先把元素插入容器后,重载版本使用指定的比较操作
void push_heap(InputIt first, InputIt last);

//对指定范围内的序列重新排序,它假设该序列是个有序堆。重载版本使用自定义比较操作
void sort_heap(InputIt first, InputIt last);             

 

© 著作权归作者所有

吃一堑消化不良
粉丝 28
博文 188
码字总数 112947
作品 0
浦东
程序员
私信 提问
VS2010/MFC编程入门教程之目录和总结(鸡啄米)

鸡啄米的这套VS2010/MFC编程入门教程到此就全部完成了,虽然有些内容还未涉及到,但帮助大家进行VS2010/MFC的入门学习业已足够。以此教程的知识为基础,学习VS2010/MFC较为深入的内容已非难事...

weixin_40647819
2018/05/23
0
0
4-C++远征之起航篇-学习笔记

c++教程起航篇 我们会讲C++那些事,C++与C语言的关系。 C++诞生于贝尔实验室。 C++之父: 本贾尼·斯特劳斯特卢普 C++社区排行榜 最新排行,c++排名第三,Python排名第四 C++语言的应用领域:...

天涯明月笙
2018/07/20
0
0
如何学习一门新的语言二——方法与步骤

之前发表过一篇文章,也是谈如何学习一门新的语言《如何学习一门新的语言》,这篇文章主要的关注点是心态。 今天这篇文章主要的关注点是具体的方法和步骤,是我学习C++和python的一些经验,整...

晨曦之光
2012/06/06
121
0
SonarQube C/C++/Objective C 3.11 发布

SonarQube C/C++/Objective C 3.11 发布,这是 Sonar 平台用来检查 C/C++/Objective-C 代码的插件。 更新日志: Bug [CPP-552] - NOSONAR tag should work for preprocessing directives (......

oschina
2016/04/14
773
0
【转载】数据结构利器之私房STL

数据结构利器之私房STL 此系列的文章适合初学有意剖析STL和欲复习STL的同学们。 学过c++的同学相信都有或多或少接触过STL。STL不仅仅是c++中很好的编程工具(这个词可能有点歧义,用类库更恰...

悠米海
2012/12/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

数据库

数据库架构 数据库架构可以分为存储文件系统和程序实例两大块,而程序实例根据不同的功能又可以分为如下小模块。 1550644570798 索引模块 常见的问题有: 为什么要使用索引 什么样的信息能成...

一只小青蛙
今天
5
0
PHP常用经典算法实现

<? //-------------------- // 基本数据结构算法 //-------------------- //二分查找(数组里查找某个元素) function bin_sch($array, $low, $high, $k){ if ( $low <= $high){ $mid = int......

半缘修道半缘君丶
昨天
5
0
GIL 已经被杀死了么?

本文原创并首发于公众号【Python猫】,未经授权,请勿转载。 原文地址:https://mp.weixin.qq.com/s/8KvQemz0SWq2hw-2aBPv2Q 花下猫语: Python 中最广为人诟病的一点,大概就是它的 GIL 了。...

豌豆花下猫
昨天
5
0
git commit message form

commit message一般包括3部分:Header、Body、Footer。 <type>(<scope>):<subject>blank line<body>blank line<footer> header是必需的,body、footer可以省略。 header中type、subject......

ninjaFrog
昨天
5
0
聊聊Elasticsearch的CircuitBreakerService

序 本文主要研究一下Elasticsearch的CircuitBreakerService CircuitBreakerService elasticsearch-7.0.1/server/src/main/java/org/elasticsearch/indices/breaker/CircuitBreakerService.ja......

go4it
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部