• C++ STL 的相关资料记录
  • 持续更新

STL

  • C++ STL(标准模板库)是一套功能强大的 C++ 模板类,提供了通用的模板类和函数,这些模板类和函数可以实现多种流行和常用的算法和数据结构,如向量、链表、队列、栈。
  • C++ 标准模板库的核心包括以下三个组件:
    • 容器(Containers):容器是用来管理某一类对象的集合。C++ 提供了各种不同类型的容器,比如 deque、list、vector、map 等。
    • 算法(Algorithms):算法作用于容器。它们提供了执行各种操作的方式,包括对容器内容执行初始化、排序、搜索和转换等操作。
    • 迭代器(iterators):迭代器用于遍历对象集合的元素。这些集合可能是容器,也可能是容器的子集。

参考链接

STL 容器

顺序容器 Sequential Containers

类型 特性
vector 可变大小数组。支持快速随机访问。在尾部之外的位置插入/删除元素可能很慢
deque 双端队列。支持快速随机访问。在头尾位置插入/删除速度很快
list 双向链表。只支持双向顺序访问。在任何位置插入/删除速度都很快
forward_list 单向链表。只支持单向顺序访问。在任何位置插入/删除速度都很快
array 固定大小数组。支持快速随机访问。不能添加/删除元素
string 类似vector,但用于保存字符。支持快速随机访问。在尾部插入/删除速度很快
  • forward_listarray是C++11新增类型。与内置数组相比,array更安全易用。forward_list没有size操作。

容器选择原则

  • 除非有合适的理由选择其他容器,否则应该使用vector
  • 如果程序有很多小的元素,且空间的额外开销很重要,则不要使用listforward_list
  • 如果程序要求随机访问容器元素,则应该使用vectordeque
  • 如果程序需要在容器头尾位置插入/删除元素,但不会在中间位置操作,则应该使用deque
  • 如果程序只有在读取输入时才需要在容器中间位置插入元素,之后需要随机访问元素。则:
    • 确定是否真的需要在容器中间位置插入元素。当处理输入数据时,可以先向vector追加数据,再调用标准库的sort函数重排元素,从而避免在中间位置添加元素
    • 如果必须在中间位置插入元素,可以在输入阶段使用list。输入完成后将list中的内容拷贝到vector 中。
  • 不确定应该使用哪种容器时,可以先只使用vectorlist的公共操作:使用迭代器,不使用下标操作,避免随机访问。这样在必要时选择vectorlist都很方便。

迭代器

  • 一个迭代器范围(iterator range)由一对迭代器表示。这两个迭代器通常被称为begin和end,分别指向同一个容器中的元素或尾后地址。end迭代器不会指向范围中的最后一个元素,而是指向尾元素之后的位置。这种元素范围被称为左闭合区间(left-inclusive interval),其标准数学描述为[begin,end)。迭代器begin和end必须指向相同的容器,end可以与begin指向相同的位置,但不能指向begin之前的位置(由程序员确保)。
  • 区分:
    • begin / end
    • cbegin / cend
    • rbegin / rend

容器定义和初始化

  • 将一个容器初始化为另一个容器的拷贝时,两个容器的容器类型和元素类型都必须相同
  • 传递迭代器参数来拷贝一个范围时,不要求容器类型相同,而且新容器和原容器中的元素类型也可以不同,但是要能进行类型转换
// each container has three elements, initialized from the given initializers
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};
list<string> list2(authors);        // ok: types match
deque<string> authList(authors);    // error: container types don't match
vector<string> words(articles);     // error: element types must match
// ok: converts const char* elements to string
forward_list<string> words(articles.begin(), articles.end());
  • 定义和使用array类型时,需要同时指定元素类型和容器大小。对array进行列表初始化时,初始值的数量不能大于array的大小。如果初始值的数量小于array的大小,则只初始化靠前的元素,剩余元素会被值初始化。如果元素类型是类类型,则该类需要一个默认构造函数。
  • 可以对array进行拷贝或赋值操作,但要求二者的元素类型和大小都相同。
array<int, 42>      // type is: array that holds 42 ints
array<string, 10>   // type is: array that holds 10 strings
array<int, 10>::size_type i;   // array type includes element type and size
array<int>::size_type j;       // error: array<int> is not a type

赋值和swap(Assignment and swap)

  • 赋值运算符两侧的运算对象必须类型相同。assign允许用不同但相容的类型赋值,或者用容器的子序列赋值。由于其旧元素被替换,因此传递给assign的迭代器不能指向调用assign的容器本身。
  • array不支持assign,也不允许用花括号列表进行赋值。
list<string> names;
vector<const char*> oldstyle;
names = oldstyle;   // error: container types don't match
// ok: can convert from const char*to string
names.assign(oldstyle.cbegin(), oldstyle.cend());
  • swap 交换两个相同类型容器的内容。除array外,swap不对任何元素进行拷贝、删除或插入操作,只交换两个容器的内部数据结构,因此可以保证快速完成
vector<string> svec1(10);   // vector with ten elements
vector<string> svec2(24);   // vector with 24 elements
swap(svec1, svec2);
  • 赋值相关运算会导致指向左边容器内部的迭代器、引用和指针失效。而swap操作交换容器内容,不会导致迭代器、引用和指针失效(array和string除外)。
  • 对于array,swap会真正交换它们的元素。因此在swap操作后,指针、引用和迭代器所绑定的元素不变,但元素值已经被交换
array<int, 3> a = { 1, 2, 3 };
array<int, 3> b = { 4, 5, 6 };
auto p = a.cbegin(), q = a.cend();
a.swap(b);
// 输出交换后的值,即4、5、6
while (p != q)
{
    cout << *p << endl;
    ++p;
}
  • 对于其他容器类型(除string),指针、引用和迭代器在swap操作后仍指向操作前的元素,但这些元素已经属于不同的容器了。
vector<int> a = { 1, 2, 3 };
vector<int> b = { 4, 5, 6 };
auto p = a.cbegin(), q = a.cend();
a.swap(b);
// 输出交换前的值,即1、2、3
while (p != q)
{
    cout << *p << endl;
    ++p;
}
  • 新标准库同时提供了成员和非成员函数版本的swap。非成员版本的swap在泛型编程中非常重要,建议统一使用非成员版本的swap

关系运算符(Relational Operator)

  • 每个容器类型都支持相等运算符(==、!=)。除无序关联容器外,其他容器都支持关系运算符(>、>=、<、<=)。关系运算符两侧的容器类型和保存元素类型都必须相同。
  • 两个容器的比较实际上是元素的逐对比较,其工作方式与string的关系运算符类似:
vector<int> v1 = { 1, 3, 5, 7, 9, 12 };
vector<int> v2 = { 1, 3, 9 };
vector<int> v3 = { 1, 3, 5, 7 };
vector<int> v4 = { 1, 3, 5, 7, 9, 12 };
v1 < v2     // true; v1 and v2 differ at element [2]: v1[2] is less than v2[2]
v1 < v3     // false; all elements are equal, but v3 has fewer of them;
v1 == v4    // true; each element is equal and v1 and v4 have the same size()
v1 == v2    // false; v2 has fewer elements than v1
  • 容器的相等运算符实际上是使用元素的==运算符实现的,而其他关系运算符则是使用元素的<运算符。如果元素类型不支持所需运算符,则保存该元素的容器就不能使用相应的关系运算。

操作

  • 添加:

    • push_back
    • push_front
    • insert: 将元素插入到迭代器指定的位置之前。一些不支持push_front的容器可以使用insert将元素插入开始位置。
      • 在新标准库中,接受元素个数或范围的insert版本返回指向第一个新增元素的迭代器,而旧版本中这些操作返回void。如果范围为空,不插入任何元素,insert会返回第一个参数。
      list<string> 1st;
      auto iter = 1st.begin();
      while (cin >> word)
        iter = 1st.insert(iter, word);  // same as calling push_front
      
    • 新标准库增加了三个直接构造而不是拷贝元素的操作:emplace_front、emplace_back和emplace,其分别对应push_front、push_back和insert。当调用push或insert时,元素对象被拷贝到容器中。而调用emplace时,则是将参数传递给元素类型的构造函数,直接在容器的内存空间中构造元素。
      // construct a Sales_data object at the end of c
      // uses the three-argument Sales_data constructor
      c.emplace_back("978-0590353403", 25, 15.99);
      // error: there is no version of push_back that takes three arguments
      c.push_back("978-0590353403", 25, 15.99);
      // ok: we create a temporary Sales_data object to pass to push_back
      c.push_back(Sales_data("978-0590353403", 25, 15.99));
      
    • forward_list 有特殊版本的 insert 和 emplace 操作,且不支持 push_back 和 emplace_back。vector 和 string 不支持 push_front 和 emplace_front。
  • 访问:

    • 每个顺序容器都有一个front成员函数,而除了forward_list之外的顺序容器还有一个back成员函数。这两个操作分别返回首元素和尾元素的引用。在调用front和back之前,要确保容器非空。
    • 在容器中访问元素的成员函数都返回引用类型。如果容器是const对象,则返回const引用,否则返回普通引用。
    • 可以快速随机访问的容器(string、vector、deque 和 array)都提供下标运算符。保证下标有效是程序员的责任。如果希望确保下标合法,可以使用 at 成员函数。at 类似下标运算,但如果下标越界,at 会抛出 out_of_range 异常。
  • 删除:

    • 删除 deque 中除首尾位置之外的任何元素都会使所有迭代器、引用和指针失效。删除 vector 或string 的元素后,指向删除点之后位置的迭代器、引用和指针也都会失效。删除元素前,程序员必须确保目标元素存在。
    • pop_front 和 pop_back 函数分别删除首元素和尾元素。vector 和 string 类型不支持 pop_front,forward_list 类型不支持 pop_back。
    • erase 函数删除指定位置的元素。可以删除由一个迭代器指定的单个元素,也可以删除由一对迭代器指定的范围内的所有元素。两种形式的 erase 都返回指向删除元素(最后一个)之后位置的迭代器
      // delete the range of elements between two iterators
      // returns an iterator to the element just after the last removed element
      elem1 = slist.erase(elem1, elem2);  // after the call elem1 == elem2
      
    • clear 函数删除容器内的所有元素。
  • 改变容器大小(Resizing a Container)

    • resize 函数接受一个可选的元素值参数,用来初始化添加到容器中的元素,否则新元素进行值初始化。如果容器保存的是类类型元素,且 resize 向容器添加新元素,则必须提供初始值,或元素类型提供默认构造函数。
  • 容器操作可能使迭代器失效(Container Operations May Invalidate Iterators)

    • 向容器中添加或删除元素可能会使指向容器元素的指针、引用或迭代器失效。失效的指针、引用或迭代器不再表示任何元素,使用它们是一种严重的程序设计错误。
    • 必须保证在每次改变容器后都正确地重新定位迭代器。不要保存end函数返回的迭代器。
      // safer: recalculate end on each trip whenever the loop adds/erases elements
      while (begin != v.end())
      {
          // do some processing
          ++begin;    // advance begin because we want to insert after this element
          begin = v.insert(begin, 42);    // insert the new value
          ++begin;    // advance begin past the element we just added
      }
      
  • vector对象是如何增长的(How a vector Grows)

    • vector和string的实现通常会分配比新空间需求更大的内存空间,容器预留这些空间作为备用,可用来保存更多新元素。
    • capacity函数返回容器在不扩充内存空间的情况下最多可以容纳的元素数量。reserve函数告知容器应该准备保存多少元素,它并不改变容器中元素的数量,仅影响容器预先分配的内存空间大小。
    • 只有当需要的内存空间超过当前容量时,reserve才会真正改变容器容量,分配不小于需求大小的内存空间。当需求大小小于当前容量时,reserve并不会退回内存空间。因此在调用reserve之后,capacity会大于或等于传递给reserve的参数。
    • 在C++11中可以使用 shrink_to_fit 函数来要求deque、vector和string退回不需要的内存空间(并不保证退回)。
  • string 操作

    • 构造方法:
      • 拷贝构造
      • 求子串
    • 操作:
      • append
        string s("C++ Primer"), s2 = s;     // initialize s and s2 to "C++ Primer"
        s.insert(s.size(), " 4th Ed.");     // s == "C++ Primer 4th Ed."
        s2.append(" 4th Ed.");     // equivalent: appends " 4th Ed." to s2; s == s2
        
      • replace
        // equivalent way to replace "4th" by "5th"
        s.erase(11, 3);         // s == "C++ Primer Ed."
        s.insert(11, "5th");    // s == "C++ Primer 5th Ed."
        // starting at position 11, erase three characters and then insert "5th"
        s2.replace(11, 3, "5th");   // equivalent: s == s2
        
      • 搜索:
        • string 的每个搜索操作都返回一个 string::size_type 值,表示匹配位置的下标。不建议用int或其他带符号类型来保存string搜索函数的返回值。
      • 比较:
        • string 类型提供了一组compare函数进行字符串比较操作,类似C标准库的strcmp函数
      • 数值转换(Numeric Conversions)
        • 进行数值转换时,string参数的第一个非空白字符必须是符号(+或-)或数字。它可以以0x或0X开头来表示十六进制数。对于转换目标是浮点值的函数,string参数也可以以小数点开头,并可以包含e或E来表示指数部分。
        • 如果给定的 string 不能转换为一个数值,则转换函数会抛出invalid_argument异常。如果转换得到的数值无法用任何类型表示,则抛出 out_of_range 异常。

容器适配器

  • 标准库定义了stack、queue和priority_queue三种容器适配器。容器适配器可以改变已有容器的工作机制
  • 默认情况下,stack和queue是基于deque实现的,priority_queue是基于vector实现的。可以在创建适配器时将一个命名的顺序容器作为第二个类型参数,来重载默认容器类型。
// empty stack implemented on top of vector
stack<string, vector<string>> str_stk;
// str_stk2 is implemented on top of vector and initially holds a copy of svec
stack<string, vector<string>> str_stk2(svec);
  • 所有适配器都要求容器具有添加和删除元素的能力,因此适配器不能构造在 array 上。适配器还要求容器具有添加、删除和访问尾元素的能力,因此也不能用 forward_list 构造适配器。

关联容器

关联容器支持高效的关键字查找和访问操作。2个主要的关联容器(associative-container)类型是mapset

  • map中的元素是一些键值对(key-value):关键字起索引作用,值表示与索引相关联的数据。
  • set中每个元素只包含一个关键字,支持高效的关键字查询操作:检查一个给定关键字是否在set中。

标准库提供了8个关联容器,它们之间的不同体现在三个方面:

  • map还是set类型。
  • 是否允许保存重复的关键字。
  • 是否按顺序保存元素。

允许重复保存关键字的容器名字都包含单词multi;无序保存元素的容器名字都以单词unordered开头。

使用关联容器(Using an Associative Container)

map类型通常被称为关联数组(associative array)。

map中提取一个元素时,会得到一个pair类型的对象。pair是一个模板类型,保存两个名为firstsecond的公有数据成员。map所使用的pairfirst成员保存关键字,用second成员保存对应的值。

// count the number of times each word occurs in the input
map<string, size_t> word_count;     // empty map from string to size_t
string word;
while (cin >> word)
    ++word_count[word];     // fetch and increment the counter for word
for (const auto &w : word_count)    // for each element in the map
    // print the results
    cout << w.first << " occurs " << w.second
        << ((w.second > 1) ? " times" : " time") << endl;

set类型的find成员返回一个迭代器。如果给定关键字在set中,则迭代器指向该关键字,否则返回的是尾后迭代器。

pair

pair定义在头文件utility中。一个pair可以保存两个数据成员,分别命名为firstsecond

pair<string, string> anon;        // holds two strings
pair<string, size_t> word_count;  // holds a string and an size_t
pair<string, vector<int>> line;   // holds string and vector<int>

pair的默认构造函数对数据成员进行值初始化。

定义
  • 定义map时,必须指定关键字类型和值类型;定义set时,只需指定关键字类型。
  • 初始化map时,提供的每个键值对用花括号{}包围。
map<string, size_t> word_count;   // empty
// list initialization
set<string> exclude = { "the", "but", "and" };
// three elements; authors maps last name to first
map<string, string> authors =
{
    {"Joyce", "James"},
    {"Austen", "Jane"},
    {"Dickens", "Charles"}
};
  • map 和 set 中的关键字必须唯一,multimap 和 multiset 没有此限制。

关键字类型的要求(Requirements on Key Type)

  • 对于有序容器——map、multimap、set和multiset,关键字类型必须定义元素比较的方法。默认情况下,标准库使用关键字类型的 < 运算符来进行比较操作。
  • 用来组织容器元素的操作的类型也是该容器类型的一部分。如果需要使用自定义的比较操作,则必须在定义关联容器类型时提供此操作的类型。操作类型在尖括号中紧跟着元素类型给出。
bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
{
    return lhs.isbn() < rhs.isbn();
}

// bookstore can have several transactions with the same ISBN
// elements in bookstore will be in ISBN order
multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);
操作
  • 类型
    • 对于set类型,key_type和value_type是一样的。set中保存的值就是关键字。对于map类型,元素是关键字-值对。即每个元素是一个pair对象,包含一个关键字和一个关联的值。由于元素关键字不能改变,因此pair的关键字部分是const的。另外,只有map类型(unordered_map、unordered_multimap、multimap、map)才定义了mapped_type。
    set<string>::value_type v1;        // v1 is a string
    set<string>::key_type v2;          // v2 is a string
    map<string, int>::value_type v3;   // v3 is a pair<const string, int>
    map<string, int>::key_type v4;     // v4 is a string
    map<string, int>::mapped_type v5;  // v5 is an int
    
  • 迭代器
    • 解引用关联容器迭代器时,会得到一个类型为容器的value_type的引用。对map而言,value_type是pair类型,其first成员保存const的关键字,second成员保存值。
      // get an iterator to an element in word_count
      auto map_it = word_count.begin();
      // *map_it is a reference to a pair<const string, size_t> object
      cout << map_it->first;          // prints the key for this element
      cout << " " << map_it->second;  // prints the value of the element
      map_it->first = "new key";      // error: key is const
      ++map_it->second;               // ok: we can change the value through an iterator
      
    • 虽然set同时定义了iterator和const_iterator类型,但两种迭代器都只允许只读访问set中的元素。类似map,set中的关键字也是const的。
      set<int> iset = {0,1,2,3,4,5,6,7,8,9};
      set<int>::iterator set_it = iset.begin();
      if (set_it != iset.end())
      {
          *set_it = 42;       // error: keys in a set are read-only
          cout << *set_it << endl;    // ok: can read the key
      }
      
    • map 和 set 都支持begin和end操作。使用迭代器遍历map、multimap、set或multiset时,迭代器按关键字升序遍历元素。
  • 添加:
    • 使用insert成员可以向关联容器中添加元素。向map和set中添加已存在的元素对容器没有影响。
    • 通常情况下,对于想要添加到map中的数据,并没有现成的pair对象。可以直接在insert的参数列表中创建pair。
      // four ways to add word to word_count
      word_count.insert({word, 1});
      word_count.insert(make_pair(word, 1));
      word_count.insert(pair<string, size_t>(word, 1));
      word_count.insert(map<string, size_t>::value_type(word, 1));
      
    • insert或emplace的返回值依赖于容器类型和参数:
      • 对于不包含重复关键字的容器,添加单一元素的insert和emplace版本返回一个pair,表示操作是否成功。pair的first成员是一个迭代器,指向具有给定关键字的元素;second成员是一个bool值。如果关键字已在容器中,则insert直接返回,bool值为false。如果关键字不存在,元素会被添加至容器中,bool值为true。
      • 对于允许包含重复关键字的容器,添加单一元素的insert和emplace版本返回指向新元素的迭代器。
  • 删除:
    • 与顺序容器不同,关联容器提供了一个额外的erase操作。它接受一个key_type参数,删除所有匹配给定关键字的元素(如果存在),返回实际删除的元素数量。对于不包含重复关键字的容器,erase的返回值总是1或0。若返回值为0,则表示想要删除的元素并不在容器中。
  • map的下标操作(Subscripting a map
    • map下标运算符接受一个关键字,获取与此关键字相关联的值。如果关键字不在容器中,下标运算符会向容器中添加该关键字,并值初始化关联值。
    • 由于下标运算符可能向容器中添加元素,所以只能对非const的map使用下标操作。
    • 对map进行下标操作时,返回的是mapped_type类型的对象;解引用map迭代器时,返回的是value_type类型的对象。
  • 访问元素:
    • 如果multimap或multiset中有多个元素具有相同关键字,则这些元素在容器中会相邻存储。
    • lower_bound和upper_bound操作都接受一个关键字,返回一个迭代器。如果关键字在容器中,lower_bound返回的迭代器会指向第一个匹配给定关键字的元素,而upper_bound返回的迭代器则指向最后一个匹配元素之后的位置。如果关键字不在multimap中,则lower_bound和upper_bound会返回相等的迭代器,指向一个不影响排序的关键字插入位置。因此用相同的关键字调用lower_bound和upper_bound会得到一个迭代器范围,表示所有具有该关键字的元素范围。
      // definitions of authors and search_item as above
      // beg and end denote the range of elements for this author
      for (auto beg = authors.lower_bound(search_item),
              end = authors.upper_bound(search_item);
          beg != end; ++beg)
          cout << beg->second << endl;    // print each title
      
    • lower_bound和upper_bound有可能返回尾后迭代器。如果查找的元素具有容器中最大的关键字,则upper_bound返回尾后迭代器。如果关键字不存在,且大于容器中任何关键字,则lower_bound也返回尾后迭代器。
    • equal_range操作接受一个关键字,返回一个迭代器pair。若关键字存在,则第一个迭代器指向第一个匹配关键字的元素,第二个迭代器指向最后一个匹配元素之后的位置。若关键字不存在,则两个迭代器都指向一个不影响排序的关键字插入位置。
      // definitions of authors and search_item as above
      // pos holds iterators that denote the range of elements for this key
      for (auto pos = authors.equal_range(search_item);
              pos.first != pos.second; ++pos.first)
          cout << pos.first->second << endl;  // print each title
      
无序容器
  • 新标准库定义了4个无序关联容器(unordered associative container),这些容器使用哈希函数(hash function)和关键字类型的 == 运算符组织元素。
  • 无序容器和对应的有序容器通常可以相互替换。但是由于元素未按顺序存储,使用无序容器的程序输出一般会与有序容器的版本不同。
  • 无序容器在存储上组织为一组桶,每个桶保存零或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素,容器首先计算元素的哈希值,它指出应该搜索哪个桶。容器将具有一个特定哈希值的所有元素都保存在相同的桶中。因此无序容器的性能依赖于哈希函数的质量和桶的数量及大小。
    20210814224446
  • 默认情况下,无序容器使用关键字类型的 == 运算符比较元素,还使用一个 hash<key_type> 类型的对象来生成每个元素的哈希值。标准库为内置类型和一些标准库类型提供了hash模板。因此可以直接定义关键字是这些类型的无序容器,而不能直接定义关键字类型为自定义类类型的无序容器,必须先提供对应的hash模板版本。

STL 常用算法

搜索

二分查找
  • upper_bound()
//查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);
  • lower_bound()
//在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);