PPC的C/C++和人工智能学习笔记
每一篇学习笔记,都只是为了更好地掌握和理解

C++语言基础(16)_STL概念

今天学习C++的STL。

 

在上次课程的模板中,还有2个内容需要补充,一个是类模板中静态成员和常量成员的使用,另外一个是类模板的继承。

 

类模板中静态成员变量的使用:

template<class T>

class A {

public:

static T m_LENGTH;

};

 

template<class T>

T A<T>::m_LENGTH; //全局变量,不显式初始化

 

int main() {

A<int>::m_LENGTH = 10;

return 0;

}

 

类模板中常量成员变量的使用:

template<class T>

class A {

const T m_length;

public:

A(T length):m_length(length){}

T getLength() const { return m_length; }

};

 

int main() {

A<int> a(10);

cout << a.getLength() << endl;

return 0;

}

 

类模板的继承:

基类是模板,派生类肯定是模板。

template <class T>

class A {

T m_buff[10];

};

 

template<class T,class T1>

class B :public A {

T m_buffone;

T1 m_bb; //就算这里没有T1,B类也要加上template<class T>

};

 

int main() {

A<int> a;

B<char, int> b;

return 0;

}

 

参数类型也可以使用默认值,和函数的默认值一样,必须是从右向左。

template <class T=int>

class A {

T m_buff[10];

};

A<> a; //使用默认值,用这样的格式。

 

STL(标准模板库)

STL = Standard Template Library,标准模板库,是一个具有工业强度的,高效的C++程序库。从根本上说,STL是一些“容器”的集合,这些“容器”有list,vector,set,map等,STL也是算法和其他一些组件的集合。STL的目的是标准化组件,这样就不用重新开发,可以使用现成的组件。STL现在是C++的一部分,因此不用额外安装什么。STL被内建在你的编译系统之内。

 

STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。

 

STL的六大组件

容器(Container),是一种数据结构,如list,vector,和deques ,以模板类的方法提供。为了访问容器中的数据,可以使用由容器类输出的迭代器;

迭代器(Iterator),提供了访问容器中对象的方法。例如,可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上,C++的指针也是一种迭代器。但是,迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符地方法的类对象;

算法(Algorithm),是用来操作容器中的数据的模板函数。例如,STL用sort()来对一个vector中的数据进行排序,用find()来搜索一个list中的对象,函数本身与他们操作的数据的结构和类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用;

仿函数(Function object,仿函数(functor)又称之为函数对象(function object),其实就是重载了()操作符的struct,没有什么特别的地方;

迭代适配器(Adaptor);

空间配制器(allocator)其中主要工作包括两部分,一个是对象的创建与销毁,另外一个是内存的获取与释放。

 

STL容器:

序列式容器(Sequence containers):每个元素都有固定位置,取决于插入时机和地点,和元素值无关,如vector、deque、list;

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

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

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

 

关系式容器(Associated containers):元素位置取决于特定的排序准则,和插入顺序无关,如set、multiset、map、multimap;

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

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

 

另外有其他容器hash_map,hash_set,hash_multiset,hash_multimap。

 

容器的比较:

  Vector Deque List Set MultiSet Map MultiMap
内部结构 dynamic array array of arrays double linked list binary tree binary tree binary tree binary tree
随机存取 Yes Yes No No No Yes(key) No
搜索速度 很慢
快速插入移除 尾部 首尾 任何位置

 

容器的一些特点:

1、还是要坚持外部数据外部处理,内部数据内部处理,也就是说如果容器有插入数据行为,插入的是数据的拷贝;

2、容器里面的元素不管什么次序,满足一个情况,没有进行改变数据内容和次序操作的情况下,多次遍历,顺序相同,也就是容器里的数据次序是稳定的;

3、容器的各项操作并非绝对安全,并不是所有的操作都会抛异常(比如空栈pop(),越界访问等等)

 

容器都有些通用函数:拷贝构造,带参构造,求大小,判断空,关系运算符重载,交换,迭代器的操作,增,删,改,查等等。

 

容器中的迭代器也有一些通用操作:*解引用,++自增自减,=赋值。

for (int i = 0;;++i)//i可以理解为迭代器,但不是迭代器。

容器中的迭代器更多的像一个智能指针。

 

一个简单的例子:

vector<int> v;

vector<int>::iterator itpos;

for (int i = 0; i < 10; ++i)

v.push_back(i + 1);

for (int i = 0; i < 10; ++i)

{

printf(“%d\n”, v.at(i));

}

printf(“//====================\n”);

for (itpos = v.begin(); itpos != v.end(); ++itpos) //迭代器操作

printf(“%d\n”,*itpos);

 

 

STL迭代器:

iterator(迭代器)模式又称Cursor(游标)模式,用于提供一种方法顺序访问一个聚合对象中各个元素,而又不需暴露该对象的内部表示。或者这样说可能更容易理解:Iterator模式是运用于聚合对象的一种模式,通过运用该模式,使得我们可以在不知道对象内部表示的情况下,按照一定顺序(由iterator提供的方法)访问聚合对象中的各个元素。

 

迭代器的作用:能够让迭代器与算法不干扰的相互发展,最后又能无间隙的粘合起来,重载了*,++,==,!=,=运算符。用以操作复杂的数据结构,容器提供迭代器,算法使用迭代器;

 

常见的一些迭代器类型:iterator、const_iterator、reverse_iterator和const_reverse_iterator

 

迭代器一般声明例子:(实际使用中T用类型替代)

vector<T>::iterator it;

list<T>::iterator it;

deque<T>::iterator it;

 

只有顺序容器和关联容器支持迭代器遍历,各容器支持的迭代器的类别如下:

 

容器 支持的迭代器类别 说明
vector 随机访问 一种随机访问的数组类型,提供了对数组元素进行快速随机访问以及在序列尾部进行快速的插入和删除操作的功能。可以再需要的时候修改其自身的大小
deque 随机访问 一种随机访问的数组类型,提供了序列两端快速进行插入和删除操作的功能。可以再需要的时候修改其自身的大小
list 双向 一种不支持随机访问的数组类型,插入和删除所花费的时间是固定的,与位置无关。
set 双向 一种随机存取的容器,其关键字和数据元素是同一个值。所有元素都必须具有惟一值。
multiset 双向 一种随机存取的容器,其关键字和数据元素是同一个值。可以包含重复的元素。
map 双向 一种包含成对数值的容器,一个值是实际数据值,另一个是用来寻找数据的关键字。一个特定的关键字只能与一个元素关联。
multimap 双向 一种包含成对数值的容器,一个值是实际数据值,另一个是用来寻找数据的关键字。一个关键字可以与多个数据元素关联。
stack 不支持 适配器容器类型,用vector,deque或list对象创建了一个先进后出容器
queue 不支持 适配器容器类型,用deque或list对象创建了一个先进先出容器
priority_queue 不支持 适配器容器类型,用vector或deque对象创建了一个排序队列

 

STL算法:

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

STL中算法大致分为四类:

1)、非可变序列算法:指不直接修改其所操作的容器内容的算法。

2)、可变序列算法:指可以修改它们所操作的容器内容的算法。

3)、排序算法:包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。

4)、数值算法:对容器内容进行数值计算。

 

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

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

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

binary_search:            在有序序列中查找value,找到返回true。重载的版本实用指定的比较函数对象或函数指针来判断相等。

count:                    利用等于操作符,把标志范围内的元素与输入值比较,返回相等元素个数。

count_if:                 利用输入的操作符,对标志范围内的元素进行操作,返回结果为true的个数。

equal_range:              功能类似equal,返回一对iterator,第一个表示lower_bound,第二个表示upper_bound。

find:                     利用底层元素的等于操作符,对指定范围内的元素与输入值进行比较。当匹配时,结束搜索,返回该元素的一个InputIterator。

find_end:                 在指定范围内查找”由输入的另外一对iterator标志的第二个序列”的最后一次出现。找到则返回最后一对的第一个ForwardIterator,否则返回输入的”另外一对”的第一个ForwardIterator。重载版本使用用户输入的操作符代替等于操作。

find_first_of:            在指定范围内查找”由输入的另外一对iterator标志的第二个序列”中任意一个元素的第一次出现。重载版本中使用了用户自定义操作符。

find_if:                  使用输入的函数代替等于操作符执行find。

lower_bound:              返回一个ForwardIterator,指向在有序序列范围内的可以插入指定值而不破坏容器顺序的第一个位置。重载函数使用自定义比较操作。

upper_bound:              返回一个ForwardIterator,指向在有序序列范围内插入value而不破坏容器顺序的最后一个位置,该位置标志一个大于value的值。重载函数使用自定义比较操作。

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

search_n:                 在指定范围内查找val出现n次的子序列。重载版本使用自定义的比较操作。

 

<二>排序和通用算法(14个):提供元素排序策略

inplace_merge:            合并两个有序序列,结果序列覆盖两端范围。重载版本使用输入的操作进行排序。

merge:                    合并两个有序序列,存放到另一个序列。重载版本使用自定义的比较。

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

partial_sort:             对序列做部分排序,被排序元素个数正好可以被放到范围内。重载版本使用自定义的比较操作。

partial_sort_copy:        与partial_sort类似,不过将经过排序的序列复制到另一个容器。

partition:                对指定范围内元素重新排序,使用输入的函数,把结果为true的元素放在结果为false的元素之前。

random_shuffle:           对指定范围内的元素随机调整次序。重载版本输入一个随机数产生操作。

reverse:                  将指定范围内元素重新反序排序。

reverse_copy:             与reverse类似,不过将结果写入另一个容器。

rotate:                   将指定范围内元素移到容器末尾,由middle指向的元素成为容器第一个元素。

rotate_copy:              与rotate类似,不过将结果写入另一个容器。

sort:                     以升序重新排列指定范围内的元素。重载版本使用自定义的比较操作。

stable_sort:              与sort类似,不过保留相等元素之间的顺序关系。

stable_partition:         与partition类似,不过不保证保留容器中的相对顺序。

 

<三>删除和替换算法(15个)

copy:                     复制序列

copy_backward:            与copy相同,不过元素是以相反顺序被拷贝。

iter_swap:                交换两个ForwardIterator的值。

remove:                   删除指定范围内所有等于指定元素的元素。注意,该函数不是真正删除函数。内置函数不适合使用remove和remove_if函数。

remove_copy:              将所有不匹配元素复制到一个制定容器,返回OutputIterator指向被拷贝的末元素的下一个位置。

remove_if:                删除指定范围内输入操作结果为true的所有元素。

remove_copy_if:           将所有不匹配元素拷贝到一个指定容器。

replace:                  将指定范围内所有等于vold的元素都用vnew代替。

replace_copy:             与replace类似,不过将结果写入另一个容器。

replace_if:               将指定范围内所有操作结果为true的元素用新值代替。

replace_copy_if:          与replace_if,不过将结果写入另一个容器。

swap:                     交换存储在两个对象中的值。

swap_range:               将指定范围内的元素与另一个序列元素值进行交换。

unique:                   清除序列中重复元素,和remove类似,它也不能真正删除元素。重载版本使用自定义比较操作。

unique_copy:              与unique类似,不过把结果输出到另一个容器。

 

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

next_permutation:         取出当前范围内的排列,并重新排序为下一个排列。重载版本使用自定义的比较操作。

prev_permutation:         取出指定范围内的序列并将它重新排序为上一个序列。如果不存在上一个序列则返回false。重载版本使用自定义的比较操作。

 

 

<五>算术算法(4个)

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

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

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

adjacent_difference:      创建一个新序列,新序列中每个新值代表当前元素与上一个元素的差。重载版本用指定二元操作计算相邻元素的差。

 

<六>生成和异变算法(6个)

fill:                     将输入值赋给标志范围内的所有元素。

fill_n:                   将输入值赋给first到first+n范围内的所有元素。

for_each:                 用指定函数依次对指定范围内所有元素进行迭代访问,返回所指定的函数类型。该函数不得修改序列中的元素。

generate:                 连续调用输入的函数来填充指定的范围。

generate_n:               与generate函数类似,填充从指定iterator开始的n个元素。

transform:                将输入的操作作用与指定范围内的每个元素,并产生一个新的序列。重载版本将操作作用在一对元素上,另外一个元素来自输入的另外一个序列。结果输出到指定容器。

 

 

<七>关系算法(8个)

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

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

lexicographical_compare:  比较两个序列。重载版本使用用户自定义比较操作。

max:                      返回两个元素中较大一个。重载版本使用自定义比较操作。

max_element:              返回一个ForwardIterator,指出序列中最大的元素。重载版本使用自定义比较操作。

min:                      返回两个元素中较小一个。重载版本使用自定义比较操作。

min_element:              返回一个ForwardIterator,指出序列中最小的元素。重载版本使用自定义比较操作。

mismatch:                 并行比较两个序列,指出第一个不匹配的位置,返回一对iterator,标志第一个不匹配元素位置。如果都匹配,返回每个容器的last。重载版本使用自定义的比较操作。

 

 

<八>集合算法(4个)

set_union:                构造一个有序序列,包含两个序列中所有的不重复元素。重载版本使用自定义的比较操作。

set_intersection:         构造一个有序序列,其中元素在两个序列中都存在。重载版本使用自定义的比较操作。

set_difference:           构造一个有序序列,该序列仅保留第一个序列中存在的而第二个中不存在的元素。重载版本使用自定义的比较操作。

set_symmetric_difference: 构造一个有序序列,该序列取两个序列的对称差集(并集-交集)。

 

 

<九>堆算法(4个)

make_heap:                把指定范围内的元素生成一个堆。重载版本使用自定义比较操作。

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

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

sort_heap:                对指定范围内的序列重新排序,它假设该序列是个有序堆。重载版本使用自定义比较操作。

 

 

STL适配器:

STL提供了三个容器适配器:queue、priority_queue、stack。这些适配器都是包装了vector、list、deque中某个顺序容器的包装器。注意:适配器没有提供迭代器,也不能同时插入或删除多个元素。

 

 

 

(2017-04-13 www.vsppc.com)

学习笔记未经允许不得转载:PPC的C/C++和人工智能学习笔记 » C++语言基础(16)_STL概念

分享到:更多 ()

评论 72

评论前必须登录!