C/C++编程：STL总结

た入场券 2022-05-18 04:12 192阅读 0赞

# 容器内的类型 #

> **container::value\_type**
> 
>  *  元素类型
>  *  用于(unordered)set和multiset时是常量
>  *  用于(unordered)map和multimap是是pair<cont key-type, mapped-type>

> **container::reference**
> 
>  *  元素的引用类型
>  *  典型定义：container::value\_type&
>  *  在vector<bool>中其实是个辅助类
> 
> **container::const\_reference**
> 
>  *  只读元素的引用类型
>  *  典型定义：const container::value\_type&
>  *  在vector<bool>中其实是bool

> **container::iterator**
> 
>  *  迭代器类型
> 
> **container::const\_iterator**
> 
>  *  只读迭代器的类型
> 
> **container::reverse\_iterator**
> 
>  *  反向迭代器的类型
> 
> **container::const\_reverse\_iterator**
> 
>  *  只读反向迭代器的类型

> **container::pointer**
> 
>  *  指针类型
> 
> **container::const\_pointer**
> 
>  *  只读指针类型

> **container::size\_type**
> 
>  *  无正负号整数类型，用来表示容器大小
> 
> **container::difference\_type**
> 
>  *  带正负号整数类型，用来定义距离

> **container::key\_type**
> 
>  *  用以定义关联式和无序容器的元素的key类型
>  *  用于(unordered)set和multiset时，相当于value\_type
> 
> **container::mapped\_type**
> 
>  *  用以定义关联式和无序容器的元素的value类型

> **container::key\_compare**
> 
>  *  关联式容器内的“比较准则”类型
> 
> **container::value\_compare**
> 
>  *  整个元素的“比较准则”类型
>  *  用于set和multiset时，相当于key\_compare
>  *  在map和multimap中，它是“比较准则”的辅助类，仅比较两元素的key

> **container::hasher**
> 
>  *  无序容器内的hashing函数的类型
> 
> **container::key\_equal**
> 
>  *  无序容器内的“相等判断式”的类型
> 
> **container::local\_iterator**
> 
>  *  无序容器内的bucket迭代器的类型
> 
> **container::const\_local\_iterator**
> 
>  *  无序容器内的bucket只读迭代器的类型

此外，所有容器(array)除外，都提供allocator\_type类型

# create，copy，destroy #

> **container::container()**
> 
>  *  default构造函数
>  *  建立一个新的空容器
> 
> explicit **container::container(const CompFunc & cmpPred)**
> 
>  *  以cmpPred为排序准则建立一个空容器
>  *  排序准则必须定义一个strict weak ordering
> 
> explicit **container::container(size\_type bnum)**
> 
> explicit **container::container(size\_type bnum, const Hasher &hasher)**
> 
> explicit **container::container(size\_type bnum, const Hasher &hasher, const KeyEqual &eqPred)**
> 
>  *  建立一个空容器，带有至少bnum个bucket，hasher用作hashing函数，eqPred用作“鉴定数值”相等的准则
>  *  如果没有传入eqPred，就使用容器默认的“等值准则”
>  *  如果没有传入hasher，就使用容器默认的hashing函数
> 
> **container::container(initializer-list)**
> 
>  *  建立一个新容器，以**initializer-list**内的容器为初值
>  *  对于array，这个操作是隐式定义的
> 
> **container::container(initializer-list，const CompFunc & cmpPred)**
> 
>  *  建立一个新容器，排序准则为**cmpPred**，以**initializer-list**内的容器为初值
>  *  排序准则必须定义一个strict weak ordering
> 
> explicit **container::container(initializer-list，size\_type bnum)**
> 
> explicit **container::container(initializer-list，size\_type bnum, const Hasher &hasher)**
> 
> explicit **container::container(initializer-list，size\_type bnum, const Hasher &hasher，const CompFunc & cmpPred)**
> 
>  *  建立一个新容器，带有至少bnum个bucket，hasher用作hashing函数，eqPred用作“鉴定数值”相等的准则，以**initializer-list**内的容器为初值
>  *  如果没有传入eqPred，就使用容器默认的“等值准则”
>  *  如果没有传入hasher，就使用容器默认的hashing函数
> 
> **container::container(const container & c)**
> 
>  *  copy构造函数
>  *  建立一个新容器，容器初值为c中元素的拷贝
>  *  针对c中的每一个元素调用copy构造函数
>  *  对于array，这个操作是隐式定义的
> 
> **container::container(container & c)**
> 
>  *  move构造函数
>  *  建立一个新容器，容器初值为c中的元素
>  *  经此调用后，c仍然有效，但其内含“不确定”
>  *  对于array，这个操作是隐式定义的
> 
> **container::container(size\_type num)**
> 
>  *  建立一个容器，可含num个元素
>  *  元素由其default构造函数创建
> 
> **container::container(size\_type num， const T&value)**
> 
>  *  建立一个容器，可含num个元素
>  *  所有元素但是value的拷贝
>  *  对于string、value并非pass by reference
> 
> **container::container(InputIterator beg，InputIterator end)**
> 
>  *  建立一个容器，以区间\[beg, end）内的所有元素为初值
> 
> **container::container(InputIterator beg，InputIterator end， const CompFunc & cmpPred)**
> 
>  *  建立一个容器，以区间\[beg, end）内的所有元素为初值，eqPred用作“鉴定数值”相等的准则
>  *  排序准则必须定义一个strict weak ordering
> 
> **container::container(InputIterator beg，InputIterator end， size\_type bnum)**
> 
> **container::container(InputIterator beg，InputIterator end， size\_type bnum, const Hasher &hasher)**
> 
> **container::container(InputIterator beg，InputIterator end， size\_type bnum, const Hasher &hasher，const CompFunc & cmpPred)**
> 
>  *  立一个容器，带有至少bnum个bucket，hasher用作hashing函数，eqPred用作“鉴定数值”相等的准则，以区间\[beg, end）内的所有元素为初值
>  *  如果没有传入eqPred，就使用容器默认的“等值准则”
>  *  如果没有传入hasher，就使用容器默认的hashing函数
> 
> **container::~container()**
> 
>  *  析构函数
>  *  移除所有元素，并释放内存
>  *  对每个元素调用其析构函数

# 赋值操作总结 #

> **container& container::operator = (const container &c)**
> 
>  *  这是一个copy assignment操作符
>  *  将c的所有元素赋值给现有元素，易即以c的元素替换所有现有元素
>  *  这个操作符会针对被overwritten的元素调用其assignment操作符，针对被appended的元素调用其copy拷贝函数，针对被removed的元素调用其析构函数
> 
> **container& container::operator = (container &c)**
> 
>  *  这是一个move assignment操作符
>  *  将c的所有元素搬移给\*this，易即以c的元素替换所有现有元素
>  *  调用之后，c依旧有效，但是内容不明确（不保证）
> 
> **container & container::operator =（initializer-list）**
> 
>  *  将initializer-list的所有元素赋值给现有元素，也就是说以传入元素拷贝替换所有现有元素
>  *  这个操作符会针对被overwritten的元素调用其assignment操作符，针对被appended的元素调用其copy拷贝函数，针对被removed的元素调用其析构函数
> 
> **void container::assign(initializer-list)**
> 
>  *  将initializer-list的所有元素赋值给现有元素，也就是说以传入元素拷贝替换所有现有元素
> 
> void array::fill(const T & value)
> 
>  *  将value赋值给所有元素，也就是说以value的拷贝替换所有现有元素
> 
> **void container::assign(size\_type num, const T&value)**
> 
>  *  赋值num个value，也就是说用num个value拷贝替换掉所有现有元素
> 
> **void container::assign(InputIterator beg, InputIterator end)**
> 
>  *  赋值\[beg, end)区间内的所有元素，也就是说用\[begin, end)内的元素拷贝替换掉所有现有元素
> 
> void container::swap(container & c)
> 
> void swap(container &c1, container &c2)
> 
>  *  和c交换内容，或者交换c1和c2的女儿

# 插入单一元素 #

>     iterator container::insert(const T & value)
>     iterator container::insert(T & value)
>     pair<iterator, bool> container::insert(const T & value)
>     pair<iterator, bool> container::insert(T & value)
> 
>  *  在关联式容器或者无序容器中安插value
>  *  第一和第三形式会复制value
>  *  第三和第四形式会搬移value放进容器中，所以此后value的值将不再明确
>  *  如果是multiset或者multimap，采用第一、第二形式，它们返回新元素的位置。新元素的位置在既有等值元素的尾端
>  *  如果是set或者map，采用第三、第四形式，如果安插不成功（已有重复值），返回既有元素的位置和一个false。如果安插成功，返回新元素位置和一个false

>     iterator container::emplace(args)
>     pair<iterator, bool> container::emplace(args)
> 
>  *  在关联式容器或者无序容器中安插新元素，以args为初值
>  *  如果是multiset或者multimap，采用第一形式，返回新元素的位置。新元素的位置在既有等值元素的尾端
>  *  如果是set或者map，采用第二形式，如果安插不成功（已有重复值），返回既有元素的位置和一个false。如果安插成功，返回新元素位置和一个false
> 
>     iterator container::emplace(const_iterator pos, args)
> 
>  *  在指定pos上安插新元素，以args为初值，返回新元素的位置

>     iterator container::insert(const_iterator pos, const T & value)
>     iterator container::insert(const)iterator pos, T && value)
> 
>  *  在iterator pos位置上安插value，返回新元素的位置
>  *  第一形式会复制value
>  *  第二形式会搬移value，所以此后value的值不再明确
>  *  如果容器不允许重复，而且容器内已经有重复值，则调用无作用，将返回既有元素的位置

# STL元素直接访问总结 #

> **reference container::at(size\_type idx)**
> 
> **const\_reference container::at(size\_type idx) const**
> 
>  *  返回索引idx所代表的元素（第一个元素索引为0）
>  *  如果传入一个无效索引，会抛出out\_of\_range异常
>  *  后续的改动或者内存重新分配，可能导致这里返回的reference失效
>  *  如果调用者保证idx合法有效，最好使用速度更快的operator\[\]
> 
> **T & map::operator at(const key\_type & key);**
> 
>  *  返回map中key对应的value
>  *  如果没有容器内没有这个key，会抛出out\_of\_range异常

> **reference container::operator\[\](size\_type idx)**
> 
> **const\_reference container::operator\[\](size\_type idx)const**
> 
>  *  返回索引idx所代表的元素（第一个元素索引为0）
>  *  如果传入一个无效索引，会导致不确定的行为。所以调用者应该始终确保索引有效，否则应该使用at
>  *  后续的改动或者内存重新分配，可能导致这里返回的reference失效
> 
> T & map**::operator\[\](const key\_type& key)**
> 
> **T & map::operator\[\](key\_type& key)**

> **reference container::front()**
> 
> **const\_reference container::front() const**
> 
>  *  返回第一个元素
>  *  如果容器为空，会导致不明确行为
> 
> **reference container::back()**
> 
> **const\_reference container::back() const**
> 
>  *  返回最后元素
>  *  如果容器为空，会导致不明确行为

> **T \* container::data()**
> 
> **const T \* container::data() const**
> 
>  *  两者返回一个pointer指向第一元素

# stl非更易型操作总结 #

## 大小相关的操作 ##

> **bool container::empty() const**
> 
>  *  检查容器是否为空
>  *  相当于begin() == end()，但是可能更快一些
>  *  复杂度：常量时间
> 
> **size\_type container::size() const**
> 
>  *  返回现有元素数量
>  *  检查容器是否为空应该用empty，因为empty更快
>  *  复杂度：常量时间
> 
> **size\_type container::max\_size() const**
> 
>  *  返回容器可内含的最大元素个数
>  *  这是一个与实现技术相关的值，可能取决于容器的内存模型。更明确的说，由于vector通常使用单一内存区段，所以vector的这个值旺旺小于其他容器
>  *  复杂度：常量时间

## 元素比较操作 ##

> **bool operator == (const container & c1, (const container & c2)**
> 
> **bool operator != (const container & c1, (const container & c2)**
> 
>  *  返回两个容器相等或者不等
>  *  条件：元素数量相同，元素内容相同。元素顺序相同
> 
> **bool operator < (const container & c1, (const container & c2)**
> 
> **bool operator <= (const container & c1, (const container & c2)**
> 
> **bool operator > (const container & c1, (const container & c2)**
> 
> **bool operator >= (const container & c1, (const container & c2)**
> 
>  *  返回两个同型容器的比较结果
>  *  检查某容器是否小于另一容器，用的是字典顺序式比较

## 关联式容器和无序容器特有的操作 ##

> **size\_type container::count(const T&value) const**
> 
>  *  返回与value相等的元素个数
>  *  T是被排序额类型
> 
> 1.  在set和multiset中，T是元素类型
> 2.  在map和multimap中，T是key类型
> 
> **iterator container::find(const T&value)**
> 
> **const\_iterator container::find(const T&value) const**
> 
>  *  返回第一个“其值等于value”的元素的位置，如果找不到这样的元素就返回end()
>  *  T是被排序额类型
> 
> 1.  在set和multiset中，T是元素类型
> 2.  在map和multimap中，T是key类型
> 
> **iterator container::lower\_bound(const T&value)**
> 
> **const\_iterator container::lower\_bound(const T&value) const**
> 
> **iterator container::upper\_bound(const T&value)**
> 
> **const\_iterator container::upper\_bound(const T&value) const**
> 
>  *  返回一个iterator指向“根据排序准则，可安插value拷贝”的第一个位置，如果找不到这样的元素就返回end()
>  *  T是被排序额类型
> 
> 1.  在set和multiset中，T是元素类型
> 2.  在map和multimap中，T是key类型
> 
> pair<**iterator** ,**iterator** > **container::equal\_range(const T&value)**  
> pair<**const\_iterator** ,**const\_iterator** > **container::equal\_range(const T&value)const**
> 
>  *  返回一对iterator，指向“根据排序准则，可安插value拷贝”的第一个位置
>  *  相当于make\_pair(lower\_bound(value), upper\_bount(value))
>  *  T是被排序额类型
> 
> 1.  在set和multiset中，T是元素类型
> 2.  在map和multimap中，T是key类型