C++ primer 第九章-顺序容器

Hi！这里是山幺幺的c++ primer系列。写这个系列的初衷是，虽然在学校学习了c++，但总觉得对这门语言了解不深，因此我想来啃啃著名的c++ primer，并在这里同步记录我的学习笔记。由于我啃的是英文版，所以笔记是中英文夹杂的那种。另外由于已有一定的编程基础，所以这个系列不会含有太基础的知识，想入门的朋友最好自己啃书嘻嘻~

顺序容器概述

特点

  • let the programmer control the order in which the elements are stored and accessed
  • 除array外，都有flexible size

类型

  • string和vector：hold their elements in contiguous memory；支持随机存取
  • list和forward_list：the memory overhead for these containers is often substantial, when compared to vector, deque, and array；方便增删
  • deque：支持随机存取；adding or removing elements at either end of the deque is a fast operation（constant run time）, comparable to adding an element to a list or forward_list

c++ 11的新类型

  • array：和built-in的array类似，但safer, easier-to-use
  • forward_list：comparable to the best handwritten, singly linked list；没有size operation

容器的选择

  • 一般而言，用vector是最好的
  • 若有很多small elements，且space overhead很重要，则不要用list和forward_list

Container Library概述

所有container types都有的操作

specific to the sequential container的操作

头文件

  • each container is defined in a header file with the same name as the type. That is, deque is in the deque header, list in the list header, and so on.

一些限制

  • the sequential container constructor that takes a size argument uses the element type’s default constructor，所以不适用于没有默认构造函数的类
// assume noDefault is a type without a default constructor
vector<noDefault> v1(10, init); // ok: element initializer supplied
vector<noDefault> v2(10); // error: must supply an element initializer

迭代器

container iterators支持的操作

  • *iter; iter->mem; ++iter; --iter; iter1 == iter2; iter1 != iter2
    container iterators支持迭代器的以上所有操作，除了：forward_list iterators不支持--
  • iter + n; iter - n; iter += n; iter -= n; iter1 - iter2; <; <=; >; >=
    container iterators中只有string, vector, deque, and array的迭代器支持以上操作

iterator range

  • begin和end指向同一个container
  • end must not precede begin

Container Type Members

内容

  • size_type、iterator、const_iterator、reverse_iterator、const_reverse_iterator、value_type、reference、const_reference等

用法

// iter is the iterator type defined by list<string>
list<string>::iterator iter;
// count is the difference_type type defined by vector<int>
vector<int>::difference_type count;

Container的定义和初始化

概述

  • 每个容器都定义了默认构造函数，除array外，这些默认构造函数creates an empty container of the specified type、take arguments that specify the size of the container and initial values for the elements

用其他容器构造容器

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());

list initialization

// c++新特性：list initialization
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};

Size-Related Constructors（只适用于除array外的顺序容器）

vector<int> ivec(10, -1); // ten int elements, each initialized to -1
list<string> svec(10, "hi!"); // ten strings; each element is "hi!"
forward_list<int> ivec(10); // ten elements, each initialized to 0
deque<string> svec(10); // ten elements, each an empty string

PS：要求元素类型是built-in type or a class type that has a default constructor

array相关

  • the size of a library array is part of its type，所以定义和使用时必须指明size
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
  • a default-constructed array is not empty: It has as many elements as its size. These elements are default initialized
  • if the element type is a class type, the class must have a default constructor in order to permit value initialization
array<int, 10> ia1; // ten default-initialized ints
array<int, 10> ia2 = {0,1,2,3,4,5,6,7,8,9}; // list initialization
array<int, 10> ia3 = {42}; // ia3[0] is 42, remaining elements are 0
  • 与built-in的array的不同：可以copy or assign objects
int digs[10] = {0,1,2,3,4,5,6,7,8,9};
int cpy[10] = digs; // error: no copy or assignment for built-in arrays
array<int, 10> digits = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> copy = digits; // ok: so long as array types match（即大小和元素类型都match）

array<int, 10> a1 = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> a2 = {0}; // elements all have value 0
a1 = a2; // replaces elements in a1
a2 = {0}; // error: cannot assign to an array from a braced list

assignment

容器的assignment操作

PS：第一行中，c1会变为和c2含有相同元素的容器，大小也变为与c2相同；第二行中，c的大小会变为3

顺序容器（除了array）的assign

  • 与其他assignment操作的区别：上图中assign之上的assignment操作都要求左右两边的类型相同，而且会把右边容器的所有元素赋给左边容器；而顺序容器的assign lets us assign from a different but compatible type, or assign from a subsequence of a container（注意：assign operation replaces all the elements in the left-hand container）
  • 栗子
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());

list<string> slist1(1); // one element, which is the empty string
slist1.assign(10, "Hiya!"); // ten elements; each one is Hiya !
  • 注意：因为元素被replace，所以括号中的iterator不能指向调用assign的对象

swap

作用

  • exchanges the contents of two containers of the same type

特点

  • 除了array外，其他容器使用swap非常快：elements themselves are not swapped; internal data structures are swapped，因此run in constant time
  • 除了string和array外，iterators, references, and pointers into the containers are not invalidated（因为元素并没有移动）
  • array swap后，pointers, references, and iterators remain bound to the same element they denoted before the swap. Of course, the value of that element has been swapped with the corresponding element in the other array

c++ 11新特性

  • 加入了nonmember version of swap，最好使用它而不是member version

栗子

vector<string> svec1(10); // vector with ten elements
vector<string> svec2(24); // vector with 24 elements
swap(svec1, svec2); // svec1 contains 24 string elements and svec2 contains ten
// had iter denoted the string at position svec1 [3] before the swap, it will denote the element at position svec2[3] after the swap

container的size相关操作

  • size：返回元素个数
  • empty
  • max_size：returns a number that is greater than or equal to the number of elements a container of that type can contain
    PS：forward_list没有size操作，只有empty和max_size

container的关系运算符

特点

  • 左右两个容器必须是包含相同类型元素的相同类型容器
  • 与字典序比较字符串类似
  • 能比较的前提是元素可比较，因为容器的Relational Operators Use Their Element’s Relational Operator

==和!=

  • 每个容器都有

>, >=, <, <=

  • 除了unordered associative containers都有

栗子

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

顺序容器独有的操作

注意

  • When we use an object to initialize a container, or insert an object into a
    container, a copy of that object’s value is placed in the container, not the
    object itself

增加元素

  • 操作一览
  • push_back
    • 除了array和forward_list外，顺序容器都支持
    • size++
  • push_front
    • list, forward_list, and deque可以使用
  • insert
    • vector, deque, list, and string可以使用
    • 注意：用一对iter插入多个元素时，它们不能指向要插入的容器
    • c++ 11新特性：插入单个元素时，新旧版本都会返回指向被插入元素的迭代器，但插入多个元素时，新版本会返回an iterator to the first element that was inserted【若range是空的，则返回第一个参数（比如下面这段代码中，若v.end() - 2, v.end()是空的，则返回slist.begin()）】，旧版本是返回void的
    • 栗子
    // insert单个元素
c.insert(iter, x); // insert x just before iter
// insert多个元素：前闭后开
vector<string> svec;
list<string> slist;
vector<string> v = {"quasi", "simba", "frollo", "scar"};
svec.insert(svec.end(), 10, "Anna");
slist.insert(slist.begin(), v.end() - 2, v.end());
slist.insert(slist.end(), {"these", "words", "will", "go", "at", "the", "end"});
// error：用一对iter插入多个元素时，它们不能指向要插入的容器
slist.insert(slist.begin(), slist.begin(), slist.end());
  • emplace
    • 操作：emplace_front、emplace、emplace_back
    • 作用：分别对应push_front、insert、push_back
    • 区别：When we call a push or insert member, we pass objects of the element type and those objects are copied into the container. When we call an emplace member, we pass arguments to a constructor for the element type. The emplace members use those arguments to construct an element directly in space managed by the container. 或者说 In the call to emplace_back, that object is created directly in space managed by the container. The call to push_back creates a local temporary object that is pushed onto the container.
    • 栗子
    // 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));
c.emplace_back(); // uses the Sales_data default constructor
c.emplace(iter, "999-999999999"); // uses Sales_data(string)

访问元素

  • 操作一览
  • 注意：访问元素操作返回的是引用
if (!c.empty()) {
c.front() = 42; // assigns 42 to the first element in c
auto &v = c.back(); // get a reference to the last element
v = 1024; // changes the element in c
auto v2 = c.back(); // v2 is not a reference; it's a copy of c.back()
v2 = 0; // no change to the element in c
}

删除元素

  • 操作一览
  • 注意：删除元素操作并不会检查元素是否存在，需要程序员检查
  • erase
    • 会返回指向最后一个被删除元素后元素的迭代器
    • 栗子
    it = lst.erase(it);
// erase多个元素：前闭后开
elem1 = slist.erase(elem1, elem2); // after the call elem1 == elem2
slist.erase(slist.begin(), slist.end());

forward_list的专属添加/删除元素操作

  • 因为forward_list是一个单链表，所以添加/删除元素的操作与其他容器不同，必须提供要改变的位置之前的那个元素
  • 操作一览

改变容器大小

  • 操作一览
  • 栗子
list<int> ilist(10, 42); // ten ints: each has value 42
ilist.resize(15); // adds five elements of value 0 to the back of ilist
ilist.resize(25, -1); // adds ten elements of value -1 to the back of ilist
ilist.resize(5); // erases 20 elements from the back of ilist
  • 注意
    • If the container holds elements of a class type and resize adds elements, we must supply an initializer or the element type must have a default constructor
    • resize不会改变capacity

对顺序容器的操作可能Invalidate Iterators

增加元素

  • vector or string
    • 若container reallocated（比如vector的reallocated：在内存中是顺序存储的，长度增加时若当前块的内存不够，vector就要重新申请一块新的更大的内存，把之前的数据复制过来，再插入新的数据）：iterators, pointers, and references全部失效
    • 若container未reallocated：iterators, pointers, and references to elements before(after) the insertion remain valid(invalid)
  • deque
    • 若不在头/尾增加元素：iterators, pointers, and references全部失效
    • 若在头/尾增加元素：iterators are invalidated, but references and pointers to existing elements are not
  • list or forward_list
    • iterators, pointers, and references (including the off-the-end and the before-the-beginning iterators) 仍然有效

删除元素

  • list or forward_list
    • iterators, pointers, and references (including the off-the-end and the before-the-beginning iterators) 仍然有效（除了指向被删除的那个元素的）
  • deque
    • 若不在头/尾删除元素：iterators, pointers, and references全部失效
    • 若在头/尾删除元素：If we remove elements at the back of the deque, the off-the-end iterator is invalidated but other iterators, references, and pointers are unaffected（除了指向被删除的那个元素的）; they are also unaffected if we remove from the front（除了指向被删除的那个元素的）
  • vector or string
    • iterators, pointers, and references to elements before(after) the removal remain valid(invalid)

vector和string的reallocation策略

概述

  • When they have to get new memory, vector and string implementations typically allocate capacity beyond what is immediately needed
  • 实际上，由于设计良好的策略，a vector usually grows more efficiently than a list or a deque
  • 很多vector implementation appears to follow a strategy of doubling
    the current capacity each time it has to allocate new storage
  • 若no operation exceeds the vector’s capacity, the vector must not reallocate its elements

管理capacity

  • 操作一览
  • reserve
    • 若requested capacity不大于当前capacity，无动作
    • 若requested capacity大于当前capacity，allocates at least as much as (and may allocate more than) the requested amount
  • shrink_to_fit
    • 是c++ 11的新特性
    • the implementation is free to ignore this request；no guarantee that a call to shrink_to_fit will return memory

string的专属用法

constructor

  • 除了和其他容器相同的constructor，string独有这些：
const char *cp = "Hello World!!!"; // null-terminated array
char noNull[] = {'H', 'i'}; // not null terminated
string s1(cp); // copy up to the null in cp; s1 == "Hello World!!!"
string s2(noNull,2); // copy two characters from no_null; s2 == "Hi"
string s3(noNull); // undefined: noNull not null terminated
string s4(cp + 6, 5);// copy 5 characters starting at cp[6]; s4 == "World"
string s5(s1, 6, 5); // copy 5 characters starting at s1[6]; s5 == "World"
string s6(s1, 6); // copy from s1 [6] to end of s1; s6 == "World!!!"
string s7(s1,6,20); // ok, copies only to end of s1; s7 == "World!!!"
string s8(s1, 16); // throws an out_of_range exception

substr

  • 注意：If the position plus the count is greater than the size, the count is adjusted to copy only up to the end of the string
  • 栗子
string s("hello world");
string s2 = s.substr(0, 5); // s2 = hello
string s3 = s.substr(6); // s3 = world
string s4 = s.substr(6, 11); // s3 = world
string s5 = s.substr(12); // throws an out_of_range exception

查找

  • 注意
    • 以下所有操作都会返回string::size_type，含义是index of where the match occurred
    • 若there is no match, the function returns a static member named string::npos
    • string::npos 是一个const string::size_type initialized with the value -1（因为npos是一个无符号数，所以this initializer means npos is equal to the largest possible size any string could have）
  • 操作一览

compare

  • s.compare()的参数可以是：

转换为数字

  • 是c++ 11新特性
  • 由string转换为数字时，the first non-whitespace character in the string we convert to numeric value must be a character that can appear in a number
  • 若string无法转换为数字，相应的函数会throw an invalid_argument exception
  • 若string转换为数字后generates a value that can’t be represented, they throw out_of_range
  • 操作一览
  • 栗子
string s2 = "pi = 3.14";
// convert the first substring in s that starts with a digit, d = 3.14
d = stod(s2.substr(s2.find_first_of("+-.0123456789")));

其他操作

  • 操作一览
  • 栗子
s.insert(s.size(), 5, '!'); // insert five exclamation points at the end of s
s.erase(s.size() - 5, 5); // erase the last five characters from s

const char *cp = "Stately, plump Buck";
s.assign(cp, 7); // s == "Stately"
s.insert(s.size(), cp + 7); // s == "Stately, plump Buck"

string s = "some string", s2 = "some other string";
s.insert(0, s2); // insert a copy of s2 before position 0 in s
// insert s2.size() characters from s2 starting at s2[0] before s[0]
s.insert(0, s2, 0, s2.size());

// 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
s.replace(11, 3, "Fifth"); // s == "C++ Primer Fifth Ed."

Container Adaptors

概述

  • A container adaptor takes an existing container type and makes it act like a different type
  • sequential container adaptors: stack, queue, and priority_queue
  • 我们只能使用adaptor自己的操作，不能使用该adaptor built on的容器的操作

Operations and Types Common to Container Adaptors

定义一个adaptor

  • 每个adaptor都定义了两个constructor：①默认constructor：creates an empty object；②以一个container为参数，并initializes the adaptor by copying the given container
stack<int> stk(deq); // copies elements from deq into stk
  • 默认情况下，stack and queue are implemented in terms of deque；priority_queue is implemented on a vector；但我们可以override the default container type by naming a sequential container as a second type argument 
    // 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);
    PS：但是there are constraints on which containers can be used for a given adaptor：①不能用array，因为adaptor需要增删元素的能力；②不能用forward_list，因为adaptor require operations that add, remove, or access the last element；③queue adaptor只能built on ist or deque but not on vector，因为它需要back, push_back, front, and push_front；④stack adaptor可以built on vector, list, deque，因为它需要push_back, pop_back, and back；⑤priority_queue只能built on vector or deque but not on list，因为它需要random access, front, push_back, and pop_back

Stack Adaptor

  • 定义在头文件stack中
  • 操作一览（+Operations and Types Common to Container Adaptors）

queue and priority_queue Adaptors

  • 定义在头文件queue中
  • 操作一览（+Operations and Types Common to Container Adaptors）
  • 关于priority_queue
    • lets us establish a priority among the elements held in the queue：Newly added elements are placed ahead of all the elements with a lower priority
    • 实例：restaurant that seats people according to their reservation time, regardless of when they arrive
    • 默认情况下，the library uses the < operator on the element type to determine relative priorities
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 199,393评论 5赞 467
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 83,790评论 2赞 376
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 146,391评论 0赞 330
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 53,703评论 1赞 270
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 62,613评论 5赞 359
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,003评论 1赞 275
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,507评论 3赞 390
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,158评论 0赞 254
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,300评论 1赞 294
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,256评论 2赞 317
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,274评论 1赞 328
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,984评论 3赞 316
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,569评论 3赞 303
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,662评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,899评论 1赞 255
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,268评论 2赞 345
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 41,840评论 2赞 339