刘芷溢

最近更新

C++-顺序容器

6分钟阅读

顺序容器

概述

  • vector, deque在内存中连续保存；list不支持<运算
  • 通常，使用vector是最好的选择
  • 随机访问元素，用vector或deque
  • 容器中间插入或删除，用list或forward_list
  • 头尾插入或删除，用deque

容器库

  • 顺序容器几乎可以保存任意类型的元素；也可以保存容器的容器

    // noDefault是一个没有默认构造函数的类型
vector<noDefault> v1(20, init);	// 提供元素初始化器
vector<noDefault> v2(10);		// 必须提供一个元素初始化器

容器操作

迭代器

  • 迭代器范围由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或者是尾元素之后的位置；左闭合区间

    [begin, end)

  • str.size()的类型就是size_type

begin & end

  • begin, end成员都被重载过；一个是const成员，返回容器的const_iterator类型，另一个是非常量成员，返回容器的iterator类型

  • 不需要写访问时，使用cbegin和cend

auto it7 = a.begin();	// if a is const, it7 is const_iterator
auto it8 = a.cbegin();	// it8 is const_iterator

容器定义和初始化

  • 容器初始化为另一个容器的拷贝：直接拷贝整个容器；拷贝由一个迭代器对指定的元素范围（类型相容即可）

  • 拷贝时，两个容器的容器类型和元素类型必须相同（const char*可以转换成string）

  • 只有顺序容器的构造函数接收大小参数，关联容器不支持

array具有固定大小

array<int, 42>
array<string, 10>
  • 内置数组不允许进行拷贝或对象赋值操作，但是array可以

赋值和swap

  • array右边运算对象的大小可能和左边大小不同，array不支持assign，也不允许用花括号包围的值列表进行赋值

assign

  • 赋值要求运算对象有相同的类型；assign允许从一个不同但相容的类型赋值
  • 旧元素被替换，传递给assign的迭代器不能指向调用assign的容器
list<string> names;
vector<const char*> oldstyle;
names = oldstyle;	// 错误，容器类型不匹配
names.assign(oldsyle.cbegin(), oldstyle.cend());

swap

  • swap操作交换两个相同类型容器的内容；两个容器的元素会交换
  • 除array外，元素本身未交换，只是交换了两个容器的内部数据结构
  • 除string外，iterator, reference, pointer均不会失效

容器大小操作

  • 关系运算符两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素
  • 比较两个容器实际上是进行元素的逐对比较
    • 相同大小且元素相等，则相等
    • 两个容器大小不同，但较小容器的每个元素都等于较大容器的元素，较小容器小于较大容器
    • 两个容器都不是另一个容器的前缀子序列，比较结果取决于第一个不相等元素的比较结果

顺序容器操作

添加元素

  • 容器元素是拷贝；用一个对象初始化容器或插入容器时，实际上放入到容器中的是对象值的一个拷贝
vector<string> svec;
list<string> slist;
 
// euqal to slist.push_front("Hello!")
slist.insert(slist.begin(), "Hello!");
 
// 插入到vector末尾之外的任何位置都可能很慢
svec.insert(svec.begin(), "Hello!");

emplace

  • 不拷贝元素而是直接将元素放置在容器头部，任意位置，尾部
  • 将元素传递给元素类型的构造函数；在容器管理的内存空间中直接构造函数
c.emplace_back();	// default constructor
c.emplace(iter, "999");	// Sales_data(string)
c.emplace_front("999", 25, 15.99);

访问元素

  • 访问元素返回的是引用

删除元素

特殊的forward_list操作

改变容器大小

容器操作可能使迭代器失效

  • 保证每次改变容器的操作之后都正确地重新定位迭代器
while(begin != v.end()) {	// after adding or deleting, recompute end of vector
    ++begin;
    begin = v.insert(begin, 42);
    ++begin;
}

vector对象增长

  • 容器中元素连续存储，且容器大小可变
  • 当不得不获取新的内存空间时，vector和string的实现通常会分配比新的空间需求更大的内存空间

  • reverse仅仅影响vector预先分配多大的内存空间
  • size是容器中实际元素个数；capacity是容器最多容纳个数

额外的string操作

  • substr(pos, n)：返回一个string，包含s中从pos开始的n个字符拷贝

修改string

string搜索操作

  • find函数完成最简单的搜索；若找到，返回第一个匹配位置的下标，否则返回npos

compare

数值转换

容器适配器

  • stack, queue, priority_queue

关系图谱