【C++】Vector和String详解
vector和string详解，爆肝万字文只为说明白vector和sting的暧昧关系，以及vector与list之间的分分合合，看完保证你会爱上我！文章涉及容器模拟实现、迭代器失效、深浅拷贝、写时拷贝等多个知识点。
文章共13,592字 · 阅读需要大约46分钟
前言：
没错，我又更新了，即使没人看，上一篇文章介绍了有关双向链表的容器list，那问题来了，数组和字符串这种使用频率非常高的数据结构，在STL模板中会不会有让人眼前一亮的实现呢。
很明显，有！ vector和string就是这两种数据结构相对应的容器。
文章有点长，别骂我，不是废话重数的，保证是国产精品。
1、Vector
1.1vector介绍
1.1.1关联
vector是表示大小可变数组的序列容器，vector本质上是是由块连续的内存空间组成，类似于普通数组，我们可以通过像访问普通数组一样，通过下标数字对他进行访问。
1.1.2区别
vector是一种动态数组，它通过在堆上分配空间，因此它更具灵活性，当新元素插入时，这个数组需要重新分配大小，当然数组不能像链表那样，直接放入一个节点，而是要重新给他分配一个新的数组空间，将原来的数组拷贝到新的数组中，对于每次新插入数据，并不是每次都要去新分配一个新空间，而是说只有在我们超过数组空间时才会去分配一个新的数组空间,具体的分配规则下面有关函数使用会说到。
1.1.3优点
与其它动态序列容器相比， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。
1.2vecter使用
仅针对部分接口进行详细介绍
1.2.1构造
| (constructor)构造函数声明 | 接口说明 |
|---|---|
| vector() | 无参构造 |
| vector（size_type n, const value_type& val = value_type()） | 构造并初始化n个val |
| vector (const vector& x); | 拷贝构造 |
| vector (InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
1.
vector<int>ar;
2.
vector<int>al(9,1);
3.
vector<int>arr = { 1,2,3,4 };
vector<int>as(arr);
4.
int ae[] = { 1,2,3,4,5,6 };
int n = sizeof(ae) / sizeof(int);
vector<int> br(ae, ae + n);
针对拷贝构造可以去看看之前的这篇回味一下：拷贝构造函数
1.2.2迭代器
| iterator的使用 | 接口说明 |
|---|---|
| begin + end | 获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator |
| rbegin + rend | 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator |
begin它们四个返回值类型是iterator，即为迭代器，很多场景都可以用到这四个接口。
vector<int> as = { 1,2,3,4,5,6,7,8,9 };
vector<int>::reverse_iterator rit = as.rbegin();;
auto it1 = arr.rend();
cout << "as";
while (rit != as.rend()); {
cout << *rit << " ";
++rit;
}
while (it1 != arr.rbegin()); {
cout << *it1 << " ";
++it1;
}
这里就是一个例子
1.2.3空间增长问题
| 容量空间 | 接口说明 |
|---|---|
| szie | 获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
| resize | 改变vectorsize |
| reserve | 改变vector放入capacity |
size、capacity、empty这仨兄弟老生长谈了，所见即所得，不过这里要注意以下capacity。
这里刚好就是开头1.2中所说的分配规则问题，在不同的环境下，编译器对于空间扩容分配规则不同。
vector扩容的原理是，在已有空间的基础上，当这个空间被填满时或剩余空间不能装下接下来要存入的数据时，会对它进行扩容，扩大的空间并不是随便扩大的，而是将原空间乘以一个系数，得到的结果即是要重新创建的数组空间。
用下面这个代码测试一下
#include<vector>
#include<iostream>
using namespace std;
void main() {
vector<int>a;
cout << a.capacity() << endl;
int s = a.capacity();
for (int i = 0; i < 100; i++) {
a.push_back(i);
if (s != a.capacity()) {
s = a.capacity();
cout << "capacity" << a.capacity() << endl;
}
}
}
| g++ | vc6.0 |
|---|---|
- |  |
vs2022
很明显不同开发环境下，动态增长的倍数不同，vs2022是1.5倍，g++和vc6.0是2倍
相比于三兄弟，resize，reserve是空间问题的重点
resize
resize在开辟空间的同时还会初始化，影响size。
reserve
reserve只负责开辟空间，不负责缩容、释放。
1.2.4增删查改
| push_back | 尾插 |
|---|---|
| pop_back | 㞑删 |
| find | 查找（注意这个是算法模块实现，不是vector的成员接口） |
| insert | 在position之前插入val |
| erase | 删除position位置的数据 |
| swap | 交换两个vector的数据空间 |
| operator[] | 像数组一样访问（与at()区别） |
问：为什么没有头插尾插？
因为STL标准模板库要完成的使命就是高效通用，而vector作为数组，对其进行头插头删，要移动的数据太多，效率低，比较麻烦，如果业务场景必须要用到头插头删，也可以用insert、erase来实现。
问：为什么find是算法，不是vector内部函数？
STL六大组件：容器、算法、迭代器、空间配置器、配接器、仿函数
对于容器的使用一般是要配合算法，而find是模板的函数，他可以使用于各种容器。
问：[]是一种什么访问方式？at.()也是按下标访问，它们有什么区别？
对于[]的重载，是一种模仿数组的形式实现的，正因为他是模仿数组的实现逻辑，at.()和[]最大的区别是会不会进行越界检查。
对于 [] 操作符，由于它不会进行越界检查，所以当索引值超出容器可访问的范围时，你得到的是一个未定义的结果。这可能会导致程序崩溃或输出错误的数据。
| 没有越界检查程序崩溃 | 越界检查报错 |
|---|---|
 |  |
1.3vector模拟实现
以下代码为个人实现，与源码会有出入
namespace mvector{
template <class _Ty>
class vector {
public:
typedef _Ty* iterator;
typedef size_t size_type;
typedef _Ty value_type;
typedef _Ty* pointer;
typedef _Ty& reference;
typedef const _Ty& const_reference;
public:
vector() :start(nullptr), finish(nullptr), end(nullptr) {
}
vector(size_type n, const _Ty& v = _Ty()) :start(nullptr), finish(nullptr), end(nullptr) {
reserve(n);
for (int i = 0; i < n; i++)
*finish++ = v;
//while (n--)
// push_back(v);
}
~vector() {
delete[]start;
start = finish = end = nullptr;
}
iterator begin() {
return start;
}
iterator Mend() {
return finish;
}
size_type size() {
return finish - start;
}
size_type capacity() {
return end - start;
}
bool empty() {
return size() == 0;
}
iterator insert(iterator it, const _Ty& x = _Ty()) {
if (size() >= capacity()) {
size_t offset = it - start;
size_t old_capacity = capacity();
size_t new_capacity = (old_capacity = 0 ? 1 : old_capacity * 2);
reserve(new_capacity);
it = start + offset;
}
iterator tmp = finish;
while (tmp != it) {
*tmp = *--tmp;
}
*it = x;
return it;
}
void reserve(size_t n) {
if (n > capacity()) {
pointer b = new _Ty[n];
size_t old_size = size();
//memcpy(b, start, sizeof(value_type) * old_size);
for (int i = 0; i < old_size; i++)
b[i] = start[i];
delete[]start;
start = b;
end = start + n;
finish = b + old_size;
}
}
void push_back(_Ty x) {
insert(Mend());
}
void resize(size_t n, _Ty x = _Ty()) {
if (n > capacity()) {
reserve(n);
}
if (n < size()) {
finish = start + n;
return;
}
int offset = n - size();
for (int i = 0; i < offset; i++) {
*finish++ = x;
}
}
reference operator[](size_t pos) {
return start[pos];
}
const_reference operator[]( size_t pos)const {
return start[pos];
}
iterator erase(iterator it ) {
iterator l1 = it;
while (l1 != finish)
*l1 = *++l1;
--finish;
return it;
}
void pop_back() {
erase(finish);
}
vector<_Ty> operator=(vector<_Ty> v) {
Swap(v);
return *this;
}
void Swap(vector<_Ty>& v) {
swap(start, v.start);
swap(finish, v.finish);
swap(end, v.end);
}
private:
iterator start;
iterator end;
iterator finish;
};
2、String
2.1string介绍
在C语言中，已经有了字符串概念，但是，实际上并没有真正的字符串形式，C语言中的字符串是以数组的方式实现的。而C++引入了string类实现了字符串。
- string是表示字符串的字符串类
- 该类的接口与常规容器的接口基本相同，再添加了一些专门用来操作string的常规操作。
- string在底层实际是：basic_string模板类的别名，typedef basic_string<char, char_traits, allocator>
string; - 不能操作多字节或者变长字符的序列。
2.2string使用
在使用string类时，必须包含#include头文件以及using namespace std;
2.2.1构造
| (constructor)函数名称 | 功能说明 |
|---|---|
| string() | 构造空的string类对象，即空字符串 |
| string(const char* s) | 用C-string来构造string类对象 |
| string(size_t n, char c) | string类对象中包含n个字符c |
| string(const string&s) | 拷贝构造函数 |
2.2.2容量操作
| 函数名称 | 功能说明 |
|---|---|
| size | 返回字符串有效字符长度 |
| length | 返回字符串有效字符长度 |
| capacity | 返回空间总大小 |
| empty | 检测字符串释放为空串，是返回true，否则返回false |
| clear | 清空有效字符 |
| reserve | 为字符串预留空间** |
| resize | 将有效字符的个数该成n个，多出的空间用字符c填充 |
2.2.3迭代器和遍历
| 函数名称 | 功能说明 |
|---|---|
| operator[] | 返回pos位置的字符，const string类对象调用 |
| begin+ end begin | 获取一个字符的迭代器 + end获取最后一个字符下一个位置的迭 |
代器
rbegin + rend begin|获取一个字符的迭代器 + end获取最后一个字符下一个位置的迭
代器
范围for |C++11支持更简洁的范围for的新遍历方式
string s("abc");
for (auto& r : s)
cout << r << " ";
s表示的是s这个对象，auto自动给r分配为s的迭代器，其值从begin开始，这句表示在s这个对象范围内，输出r，r迭代++。
2.2.4修改操作
| 函数名称 | 功能说明 |
|---|---|
| push_back | 在字符串后尾插字符c |
| append | 在字符串后追加一个字符串 |
| operator+= | 在字符串后追加字符串str |
| c_str | 返回C格式字符串 |
| find + npos | 从字符串pos位置开始往后找字符c，返回该字符在字符串中的位置 |
| rfind | 从字符串pos位置开始往前找字符c，返回该字符在字符串中的位置 |
| substr | 在str中从pos位置开始，截取n个字符，然后将其返回 |
push_back和append、+=
在 C++ 中，单引号（’）用来括起一个字符字面量，而双引号（"）则用来括起一个字符串字面量。
具体来说，当使用单引号包围一个字符时，编译器会将其解释为该字符对应的 ASCII 码或者 Unicode 字符编码。
例如：charc1 = ‘A’; // 此处的 ‘A’ 表示字符 ‘A’ 的 ASCII 码 65
charc2 = ‘0’; //此处的 ‘0’ 表示字符 ‘0’ 的 ASCII 码 48
charc3 = ‘\n’; // 此处的 ‘\n’ 表示换行符的ASCII 码 10
另外，如果想要表示一个字符的可读形式（如制表符、回车符等），可以使用转义字符。例如，’\t’ 表示制表符，’\r’
表示回车符，’\b’ 表示退格键符，’\a’ 表示响铃符等等。
而当使用双引号包围一组字符时，则表示一个字符串字面量。一个字符串可以理解为是多个字符组成的字符数组，末尾自动添加一个 null 终止符。例如：constchar* str = “Hello, world!”; // 这是一个字符串字面量，包含 13 个字符和一个 null 终止符
在使用字符串时，可以使用许多标准库函数和操作符对它们进行处理和操作。需要注意的是，在 C++11 中引入了原始字符串字面量（即用 R"(…)" 表示的字符串字面量），它们可以含有多行文本和特殊字符而无需使用转义字符，这种方式实现了更加便捷和可读性更好的字符串处理。
实例：
void main() {
string s("abcdef");
string a("abcd");
/*cout << s.length() << endl;
cout << s.size() << endl;*/
s.push_back('abcd');
cout << s << endl;
s.append("abcd");//+=
cout << s << endl;
s.append(a, 1,3);
strlen(s.c_str());strlen参数是一个指针 而s是一个对象 这是就需要c_str这个函数了（转换出来是const常量）
cout << s << endl;
a.assign("ab");
cout << a << endl;
}
2.2.5接口了解
| 函数 | 功能说明 |
|---|---|
| operator+ | 尽量少用，因为传值返回，导致深拷贝效率 operator+ 低 |
| operator>> | 输入运算符重载 |
| operator<< | 输出运算符重载 |
| getline | 获取一行字符串 |
| relational operators | 大小比较 |
OJ题常用到
2.3string模拟实现
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;
namespace my {
class string {
friend ostream& operator<<(ostream& _cout, const my::string& s);
friend istream& operator>>(istream& _cin, my::string& s);
public:
typedef char* iterator;
public:
/*string() :_str(nullptr), _size(0), _capacity(0) {
}*/
string(const char* str = "") {
size_t size = strlen(str);
reserve(size );
//char* s = new char[size + 1];
_size = size;
strcpy(_str, str);
//_str = str;
}
string(const string& s) {
resize(s._size);
strcpy(_str, s._str);
_size = s._size;
_capacity = s._capacity;
}
/*string(const string& s):_str(nullptr) {
string a(s._str);
swap(_str, a._str);
}*/
~string() {
delete[]_str;
_str = nullptr;
}
public:
void reserve(size_t n) {
if (n >= _capacity) {
char* new_capacity = new char[n + 1];
if (_capacity) {
strcpy(new_capacity, _str);
delete[]_str;
}
_capacity = n;
_str = new_capacity;
}
}
void resize(size_t n, char c = '\0') {
_size = n;
if (n >= _capacity) {
reserve(n);
}
for (int i = 0; i < n - _size; i++) {
_str[_size + i] = c;
}
}
string& operator=(const string& s) {
if (*this != s) {
char* new_str = new char[s._size + 1];
strcpy(new_str, s._str);
delete[]_str;
_str = new_str;
_size = s._size;
_capacity = s._capacity;
}
return *this;
}
iterator begin() {
return _str;
}
iterator end() {
return _str + _size;
}
void push_back(char c) {
if (_size >= _capacity) {
size_t new_size = _size;
new_size = 0 ? 1 : _capacity * 2;
_capacity *= 2;
reserve(new_size);
}
_size++;
_str[_size] = c;
}
string& operator+=(char c) {
push_back(c);
return *this;
}
void append(const char* str) {
size_t size = strlen(str);
size_t new_size = size + _size;
if (new_size > _capacity) {
reserve(new_size * 2);
}
_size = new_size;
_capacity = (2 * new_size - 1);
}
string& operator+=(const char* str) {
append(str);
return *this;
}
void clear() {
delete[]_str;
_size = 0;
}
void swap(string& s) {
string tmp(s);
s._str = _str;
s._size = _size;
s._capacity = _capacity;
//*this = tmp;
_size = tmp._size;
_str = tmp._str;
_capacity = tmp._capacity;
}
const char* c_str()const {
return _str;
}
size_t size()const {
return _size;
}
size_t capacity()const {
return _capacity;
}
bool empty() {
return _size == 0;
}
char& operator[](size_t index) {
assert(index < _size);
return _str[index];
}
const char& operator[](size_t index)const {
assert(index < _size);
return _str[index];
}
bool operator<(const string& s) {
if (strcmp(_str, s._str) < 0)
return true;
return false;
}
bool operator<=(const string& s) {
if (strcmp(_str, s._str) <= 0)
return true;
return false;
}
bool operator>(const string& s) {
if (strcmp(_str, s._str) > 0)
return true;
return false;
}
bool operator>=(const string& s) {
if (strcmp(_str, s._str) >= 0)
return true;
return false;
}
bool operator==(const string& s) {
if (strcmp(_str, s._str) == 0)
return true;
return false;
}
bool operator!=(const string& s) {
if (strcmp(_str, s._str) != 0)
return true;
return false;
}
size_t find(char c, size_t pos = 0)const {
iterator a = _str + pos;
while (a != _str + _size) {
if (*a == c)
return pos;
pos++;
++a;
}
return -1;
}
size_t find(const char* s, size_t pos = 0)const {
size_t len = strlen(s);
for (size_t i = pos; i < _size - len + 1; i++) {
if (memcmp(_str, s, len))
return i;
}
return -1;
}
string& insert(size_t pos, char c) {
assert(c);
if (_size >= _capacity) {
_capacity *= 2;
reserve(_capacity);
}
_size++;
for (size_t i = _size; i >= pos; i--) {
_str[i] = _str[i - 1];
}
_str[pos] = c;
}
string& insert(size_t pos, const char* str) {
assert(str);
if (_size >= _capacity) {
_capacity *= 2;
reserve(_capacity);
}
size_t len = strlen(str);
_size += len;
for (size_t i = _size; i >= pos; i--) {
_str[i] = _str[i - 1];
}
for (size_t i = pos; i <= pos + len;i++) {
_str[i] = str[i-pos];
}
}
string& erase(size_t pos, size_t len) {
assert(_str);
if ((pos + len) > _size) {
for (int i = pos; i < _size; i++)
_str[pos] = '\0';
}
int i = pos;
for (i; i < _size - len; i++) {
_str[i] = _str[i + 1];
}
for (i; i < _size; i++)
_str[i] = '\0';
_size -= len;
return *this;
}
private:
char* _str;
size_t _size;
size_t _capacity;
};
ostream& operator<<(ostream& _cout, const my::string& s) {
if (s._size > 0) {
_cout << s._str;
}
return _cout;
}
istream& operator>>(istream& _cin, my::string& s) {
char* buf = (char*)malloc(sizeof(char) * 1024);
if (buf == nullptr) {
perror("malloc");
}
_cin.getline(buf, 1024);
const size_t size = strlen(buf);
char* str = new char[size + 1];
strcpy(str, buf);
delete[]s._str;
s._str = str;
free(buf);
s._size = size;
return _cin;
}
}
纯手搓、没参考源码嗷
2.4.深浅拷贝问题（写时拷贝）
首先说一下什么是浅拷贝
浅拷贝：也称位拷贝，编译器只是将对象中的值拷贝过来。如果对象中管理资源，最后就会导致多个对象共享同一份资源，当一个对象销毁时就会将该资源释放掉，而此时另一些对象不知道该资源已经被释放，以为还有效，所以当继续对资源进项操作时，就会发生发生了访问违规。要解决浅拷贝问题，C++中引入了深拷贝。
对于深拷贝的实现实际有两种思路，一种是在发生拷贝是便给对象分配一块新的空间，但是我们在实际实用中，经常会遇到我虽然拷贝构造了对象，但是我并没有要对这个对象进行修改，也就说我给他重新分配一个空间并没有任何意义，于是有另一种思路，最开始拷贝构造对象后，我并不急着给他配置空间，直到他要修改数据时，才给他分配新的空间，也就是先浅拷贝，再深拷贝。
实际上不同编译器，他们的分配规则不同，下面有请我们的两位老朋友
vs2022
vc6.0
针对上面的深浅拷贝延伸出了一个新问题，假如当前业务情景是有多个由一个对象构造出来的对象，难道我要给他们都分配一个空间吗，这显然很浪费空间，那我把他们都放到一个空间要怎么实现哪？
下图的引用计数很好的解决了这个问题。
四个对象bcde均通过a拷贝构造，count定义为静态变量，a本身count为1，每增加一个对象，便++，反之则–，这样解决了问题，但是。。。。。。就拿对象b举例吧，如果突然改变他的值，也就是说接下来我要对他重新分配空间了，对b来说他有了新空间，可是count是一个静态变量，我得让他有一个自己静态变量，也就是说把对象封装起来，用一个指针来指向它，好，秒杀！
class String_Ser {
public:
friend class String;
friend ostream& operator<<(ostream& _cout, const String& a);
public:
String_Ser (const char* str="") {
m_date = new char[strlen(str) + 1];
strcpy(m_date, str);
}
String_Ser(const String_Ser& s) {
String_Ser tmp(s.m_date);
strcpy(m_date, tmp.m_date);
m_count++;
}
String_Ser& operator=(const String_Ser& s) {
if (&s != this) {
String_Ser tmp(s);
swap(m_date, tmp.m_date);
}
return *this;
}
~String_Ser() {
if (--m_count == 0) {
delete[]m_date;
m_date = nullptr;
}
}
void Increment() {
m_count++;
}
void Decrement() {
if (--m_count == 0)
delete this;
}
private:
char* m_date;
int m_count;
};
class String {
public:
friend ostream& operator<<(ostream& _cout, const String& a);
public:
String(const char* a=""): req(new String_Ser(a)){
req->Increment();
}
String(const String& s ):req(s.req){
req -> Increment();
}
String& operator=(const String& s) {
if (req != s.req) {
req->Decrement();
req = s.req;
req->Increment();
}
return *this;
}
~String() {
req->Decrement();
}
void upper() {
String_Ser* new_req = new String_Ser(req->m_date);
req->Decrement();
req = new_req;
req->Increment();
char* it = req->m_date;
while (*it != '\0') {
if (*it >= 'a' && *it <= 'z')
*it -= 32;
++it;
}
}
private:
String_Ser* req;
};
//int String::m_count = 0;
ostream& operator<<(ostream& _cout, const String& a) {
_cout << a.req->m_date;
return _cout;
}
事实上这就是所谓的写时拷贝，我把它叫做懒*拷贝
写时拷贝就是一种拖延症，是在浅拷贝的基础之上增加了引用计数的方式来实现的。引用计数：用来记录资源使用者的个数。在构造时，将资源的计数给成1，每增加一个对象使用该资源，就给计数增加1，当某个对象被销毁时，先给该计数减1，然后再检查是否需要释放资源，如果计数为1，说明该对象时资源的最后一个使用者，将该资源释放；否则就不能释放，因为还有其他对象在使用该资源。
（终于写到这了，大声哔哔）
3、迭代器失效问题
vector和list两种容器都存在迭代器失效问题，它们的失效原理不同
vector
增加元素而导致的扩容必会导致迭代器失效。
数组A空间为4，已满，此时向A中插入数据1，很明显要扩容，扩容导致对象要指向一个新的空间，原释放，但是IL指向的还是原空间，致使其失效。
至于list可以参考上一篇文章：list详解，文章末尾有提到
vector和list
这里对list和vector进行一个总结对比
| vector | list | |
|---|---|---|
| 底 层 结 构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随 机 访 问 | 支持随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某个元素效率O(N) |
| 插 入 和 删 除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1) |
| 空 间 利 用 率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭 代 器 | 原生态指针 | 对原生态指针(节点指针)进行封装 |
| 迭 代 器 失 效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使 用 场 景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关心随机访问 |
肝完了，如果你觉得这篇文章有点东西，麻烦点个赞鼓励一下俺吧
另外
我还会继续更下去！
后续还会把STL剩余内容更完
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
28
0- 0
已为社区贡献2条内容
所有评论(0)