C++ STL序列式容器

序列式容器

vector list deque

0. 迭代器

前向迭代器

支持++p,*p等操作

双向迭代器

支持--p等操作哦

随机访问迭代器

p+=i 迭代器往后移动i个元素

p+i 返回迭代器后第i个元素的迭代器

p[i] 返回p后面第i个元素的引用

迭代器定义方式 具体格式
正向迭代器 容器类名::iterator 迭代器名;
常量正向迭代器 容器类名::const_iterator 迭代器名;
反向迭代器 容器类名::reverse_iterator 迭代器名;
常量反向迭代器 容器类名::const_reverse_iterator 迭代器名;

通过迭代器遍历

for(i=v.begin();i<v.end();++i){
    cout<<*i<<endl;
}

array<T,N>(数组容器),存储N个T类型的元素,长度初始化后不可变

vector,向量容器存放T类型的元素,长度可变,末尾添加删除元素效率高,随机访问效率低

deque,双端队列容器,可以在头部、尾部插入删除元素

list,链表容器,双向链表,长度可变,可以在任何地方添加删除元素,访问元素较慢

forward_list,正向链表容器,单向链表,只能从第一个元素开始访问,比list快,节省内存

array,vector,deque常见函数

函数 功能
begin 指向容器中第一个元素的迭代器
end 指向容器中最后一个元素所在位置的后一个位置的迭代器
rbegin 指向最后一个元素的迭代器
rend 指向容器中第一个元素所在位置的前一个位置的迭代器
cbegin/crbegin 功能同上,增加了const属性,不可修改
cend/crend 功能同上,增加了const属性,不可修改
assign 用新元素替换原有内容
size 返回元素个数
capacity 返回容量(vector)
empty 返回容器==空
resize 改变实际元素个数
front 返回第一个元素的引用
back 返回最后一个元素的引用
operator 索引访问
at 返回一个指向位置n的元素的引用
push_back 在序列尾添加元素
insert 指定元素添加元素
emplace 在指定位置生成元素
emplace_back 在序列尾部生成元素
pop_back 移除序列尾部元素
earse 移除一个或一段元素
clear 清空容器
swap 交换容器内两个元素
data 返回指向容器中的第一个元素的指针
before_begin 返回指向第一个元素前一个位置的迭代器(forward_list)
push_front 序列起始位置添加一个元素
insert_after 在指定位置后插入一个元素(forward_list)
pop_front 移除序列头部元素(list,forward_list)
earse_after 移除指定位置后面的一个元素或一段元素。(list,forward_list)
remove 移除所有和参数匹配的元素。
remove_if 移除满足条件的元素
unique 移除所有连续重复的元素。
sort 排序(list,forward_list)
merge 合并两个有序容器
splice 移动指定位置前面的所有元素到另一个同类型的 list 中
splice_after 移动指定位置后面的所有元素到另一个同类型的 list 中

1.STL array

声明后长度不可变

array<typename T,size_t N>
array<double,10> arr{};//不指定值,默认为0
array<double, 10> values {0.5,1.0,1.5,,2.0};//剩余元素为0
成员函数 功能
begin() 返回指向容器中第一个元素的随机访问迭代器。
end() 返回指向容器最后一个元素之后一个位置的随机访问迭代器,通常和 begin() 结合使用。
rbegin() 返回指向最后一个元素的随机访问迭代器。
rend() 返回指向第一个元素之前一个位置的随机访问迭代器。
cbegin() 和 begin() 功能相同,只不过在其基础上增加了 const 属性,不能用于修改元素。
cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crbegin() 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crend() 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
size() 返回容器中当前元素的数量,其值始终等于初始化 array 类的第二个模板参数 N。
max_size() 返回容器可容纳元素的最大数量,其值始终等于初始化 array 类的第二个模板参数 N。
empty() 判断容器是否为空,和通过 size()==0 的判断条件功能相同,但其效率可能更快。
at(n) 返回容器中 n 位置处元素的引用,该函数自动检查 n 是否在有效的范围内,如果不是则抛出 out_of_range 异常。
front() 返回容器中第一个元素的直接引用,该函数不适用于空的 array 容器。
back() 返回容器中最后一个元素的直接应用,该函数同样不适用于空的 array 容器。
data() 返回一个指向容器首个元素的指针。利用该指针,可实现复制容器中所有元素等类似功能。
fill(val) 将 val 这个值赋值给容器中的每个元素。
array1.swap(array2) 交换 array1 和 array2 容器中的所有元素,但前提是它们具有相同的长度和类型。

array通过[]访问元素,为了避免越界,可以使用at()成员函数,越界会抛出out_of_range异常

2.STL vector

vector<double> val;
//扩容,当val.size()>20则不做操作
val.reserve(20);
std::vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19};
std::vector<double> values(20);//指定元素个数,初始为0
std::vector<double> values(20,1);//指定元素个数,初始为1
函数成员 函数功能
begin() 返回指向容器中第一个元素的迭代器。
end() 返回指向容器最后一个元素所在位置后一个位置的迭代器,通常和 begin() 结合使用。
rbegin() 返回指向最后一个元素的迭代器。
rend() 返回指向第一个元素所在位置前一个位置的迭代器。
cbegin() 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crbegin() 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crend() 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
size() 返回实际元素个数。
max_size() 返回元素个数的最大值。这通常是一个很大的值,一般是 232-1,所以我们很少会用到这个函数。
resize() 改变实际元素的个数。
capacity() 返回当前容量。
empty() 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
reserve() 增加容器的容量。
shrink _to_fit() 将内存减少到等于当前元素实际所使用的大小。
operator[ ] 重载了 [ ] 运算符,可以向访问数组中元素那样,通过下标即可访问甚至修改 vector 容器中的元素。
at() 使用经过边界检查的索引访问元素。
front() 返回第一个元素的引用。
back() 返回最后一个元素的引用。
data() 返回指向容器中第一个元素的指针。
assign() 用新元素替换原有内容。
push_back() 在序列的尾部添加一个元素。
pop_back() 移出序列尾部的元素。
insert() 在指定的位置插入一个或多个元素。并返回新插入元素所在位置的迭代器
erase() 移出一个元素或一段元素。,根据索引删除,
clear() 移出所有的元素,容器大小变为 0。
swap() 交换两个容器的所有元素。
remove() 根据值删除元素,不会改变容器的大小和容量
emplace() 在指定的位置直接生成一个元素。
emplace_back() 在序列尾部生成一个元素。

访问元素的方式

vec[n];
vec.at(n);
vec.front();//首元素
vec.back();//尾元素
vec.data();//返回首元素的指针
*(vec.data()+n);
push_back();
emplace_back();

这两个函数都可以在容器末尾添加元素

push_back添加元素时,会生成一个元素,再将元素移动(或拷贝)至容器中,而emplace_back会

直接在容器末尾生成,因此emplace_back更加高效

iterator insert(pos,elem);//在指定位置之前插入一个元素elem
iterator insert(pos,n,elem);//在指定位置之前插入n个元素elem
iterator insert(pos,first,last);//在pos之前,插入其他容器中[first,last)区域内的所有元素,返回第一个新元素的迭代器的位置
iterator insert(pos,initlist);//在pos之前插入初始化列表的所有元素,返回第一个新元素的迭代器的位置
iterator emplace(const_iterator pos,args);

pos:指定插入元素的位置,args:新插入元素的构造函数对应的多个参数

删除元素

erase(n);//删除指定位置的元素
erase(first,last);//删除指定位置[first,last)的元素
remove(pos,n);//从pos开始删除值为n的元素

remove不会改变容器大小和容量

​ remove() 的实现原理是,在遍历容器中的元素时,一旦遇到目标元素,就做上标记,然后继续遍历,直到找到一个非目标元素,即用此元素将最先做标记的位置覆盖掉,同时将此非目标元素所在的位置也做上标记,等待找到新的非目标元素将其覆盖。因此,1,3,3,4,3,5,remove(3)如果将上面程序中 demo 容器的元素全部输出,得到的结果为 1 4 5 4 3 5

因此删除指定元素需要和erase搭配

auto it=remove(demo.begin(),demo.end(),3);
demo.erase(it,demo.end());
vector<int> demo{1,2,3};
demo.clear();
//demo.size()=0
//demo.capacity()=6

vector<bool>并不是一个STL容器,也不容纳bool

vector<bool> 打包 bool 以节省空间,每个保存在“vector”中的“bool”占用一个单独的bit,而禁止有指向单个比特的指针。

3.STL deque

deque相比vector,可以高效的在容器底部或尾部插入元素,且容器内的元素不一定会放在一段连续内存里

deque<int> dq;//初始化空队列
deque<int> dq(100);//初始化100个默认值的队列
deque<int> dq(100,1);//初始化100个1的队列
函数成员 函数功能
begin() 返回指向容器中第一个元素的迭代器。
end() 返回指向容器最后一个元素所在位置后一个位置的迭代器,通常和 begin() 结合使用。
rbegin() 返回指向最后一个元素的迭代器。
rend() 返回指向第一个元素所在位置前一个位置的迭代器。
cbegin() 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crbegin() 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crend() 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
size() 返回实际元素个数。
max_size() 返回容器所能容纳元素个数的最大值。这通常是一个很大的值,一般是 232-1,我们很少会用到这个函数。
resize() 改变实际元素的个数。
empty() 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
shrink _to_fit() 将内存减少到等于当前元素实际所使用的大小。
at() 使用经过边界检查的索引访问元素。
front() 返回第一个元素的引用。
back() 返回最后一个元素的引用。
assign() 用新元素替换原有内容。
push_back() 在序列的尾部添加一个元素。
push_front() 在序列的头部添加一个元素。
pop_back() 移除容器尾部的元素。
pop_front() 移除容器头部的元素。
insert() 在指定的位置插入一个或多个元素。
erase() 移除一个元素或一段元素。
clear() 移出所有的元素,容器大小变为 0。
swap() 交换两个容器的所有元素。
emplace() 在指定的位置直接生成一个元素。
emplace_front() 在容器头部生成一个元素。和 push_front() 的区别是,该函数直接在容器头部构造元素,省去了复制移动元素的过程。
emplace_back() 在容器尾部生成一个元素。和 push_back() 的区别是,该函数直接在容器尾部构造元素,省去了复制移动元素的过程。

注:创建first容器后,容器进行添加操作,会导致first失效

访问deque元素

dq[n];//访问容器的中第n个元素
dq.at(n);//访问容器的中第n个元素,有边界控制
dq.front();//访问dq的首元素
dq.back();//访问dq的尾元素

4.STL list

list双向链表容器,各元素靠指针维持顺序,分别指向前后两个元素,不能通过索引访问元素

list<int> l;
list<int> l(10);
list<int> l(10,5);
函数 功能
remove(val) 删除容器中所有等于 val 的元素。
remove_if() 删除容器中满足条件的元素。
unique() 删除容器中相邻的重复元素,只保留一个。
merge() 合并两个事先已排好序的 list 容器,并且合并之后的 list 容器依然是有序的。
sort() 通过更改容器中元素的位置,将它们进行排序。
reverse() 反转容器中元素的顺序。

访问元素:

l.front();//返回list的第一个元素的引用
l.back();//返回list的最后一个元素的引用

list插入元素:

push_front();
push_back();
emplace_back();
emplace_front();
emplace();//在指定位置生成元素
insert();//在指定位置插入元素
splice();//在指定位置插入其他list容器中的元素

splice 将其他list容器中的元素添加当前list容器中指定位置处。

void splice(iterator pos,list& x);//pos:插入位置,x:另一个list容器
void splice(iterator pos,list& x,iterator i);//将x容器中i指向的元素移动到当前容器中pos指明的位置
void splice(iterator pos,list& x,iterator first,iterator last);//将x容器[first,last)范围内所有元素移动到当前容器pos位置上。

splice方法会将x容器中的相应元素添加到当前容器,该元素会从x中删除

unique()

void unique();
void unique(BinaryPredicate);//传入二元谓词函数

两种方式都可去重,第二种可以自定义去重规则

remove_if();//传入自定义为此函数,删除满足条件的元素

5.STL forward_list

C++11新容器,底层为单链表结构,数据存储是分散随机的。可以在序列任何位置添加和删除元素。

forward_list只提供前向迭代器,无rbegin,rend等函数

相较于list,消耗内存小,空间效率高

forward_list<int> fl;
forward_list<int> fl(10);
forward_list<int> fl(10,5);//初始化10个5
before_begin() 返回一个前向迭代器,其指向容器中第一个元素之前的位置。
begin() 返回一个前向迭代器,其指向容器中第一个元素的位置。
end() 返回一个前向迭代器,其指向容器中最后一个元素之后的位置。
cbefore_begin() 和 before_begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
cbegin() 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
empty() 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
max_size() 返回容器所能包含元素个数的最大值。这通常是一个很大的值,一般是 232-1,所以我们很少会用到这个函数。
front() 返回第一个元素的引用。
assign() 用新元素替换容器中原有内容。
push_front() 在容器头部插入一个元素。
emplace_front() 在容器头部生成一个元素。该函数和 push_front() 的功能相同,但效率更高。
pop_front() 删除容器头部的一个元素。
emplace_after() 在指定位置之后插入一个新元素,并返回一个指向新元素的迭代器。和 insert_after() 的功能相同,但效率更高。
insert_after() 在指定位置之后插入一个新元素,并返回一个指向新元素的迭代器。
erase_after() 删除容器中某个指定位置或区域内的所有元素。
swap() 交换两个容器中的元素,必须保证这两个容器中存储的元素类型是相同的。
resize() 调整容器的大小。
clear() 删除容器存储的所有元素。
splice_after() 将某个 forward_list 容器中指定位置或区域内的元素插入到另一个容器的指定位置之后。
remove(val) 删除容器中所有等于 val 的元素。
remove_if() 删除容器中满足条件的元素。
unique() 删除容器中相邻的重复元素,只保留一个。
merge() 合并两个事先已排好序的 forward_list 容器,并且合并之后的 forward_list 容器依然是有序的。
sort() 通过更改容器中元素的位置,将它们进行排序。
reverse() 反转容器中元素的顺序。

forward_list不提供size函数,如果想获取长度,采用iterator中的distance函数。

int count=distance(begin(fl),end(fl));
int count=distance(fl.begin(),fl.end());

begin(),end()为STL容器方法,可以获取容器第一个,最后一个元素的迭代器

begin(),end(),参数可以是普通数组,可可以是容器,为普通数组将返回第一个、最后一个元素的指针,为容器返回迭代器。

6.vector自定义排序

  • 重载运算符

    struct Book{
    	int page;
    	string name;
    	bool operator <(const Book& b) const // 升序排序时必须写的函数
        {
            return page < b.page;
        }
        bool operator >(const Book& b) const // 降序排序时必须写的函数
        {
            return page > b.page;
        }
    }
    vector<Book> books;
    sort(books.begin(), books.end(), less<Book>());
    
  • 全局比较函数

    struct Book{
    	int page;
    	string name;
    };
    
    bool lessmark(const Book& b1, const Book& b2)
    {
         return b1.page < b2.page;
    }
    bool greatermark(const Book& b1, const Book& b2)
    {
         return b1.page > b2.page;
    }
    vector<Book> books;
    sort(books.begin(), books.end(), lessmark); //升序排序
    
  • 仿生函数(重写())

    struct Book{
    	int page;
    	string name;
    };
    class CompLess{
    public:
        bool operator ()(const Book& b1, const Book& b2)
        {
            return b1.page < b2.page;
        }
    };
    class CompGreater{
    public:
        bool operator ()(const Book& b1, const Book& b2)
        {
            return b1.page > b2.page;
        }
    };
    vector<Book> books;
    sort(books.begin(), books.end(), CompLess()); //升序排序
    
上一篇:STL 模板复习


下一篇:最详细STL(四)priority_queue