STL六大组件-容器篇
·
文章目录
容器
string
深浅拷贝
C++类型语言：
- 值类型：实际上直接存储信息，在大多数语言中，int都是芷蕾西
- 引用类型：存储对信息的引用，在C++中，类的实例几乎总是引用类型
将记忆想象成 URL 和网站。
如果您想访问某些内存，计算机会检查 URL，该 URL 会将您带到一个网站，该网站包含计算机想要的数据。
浅拷贝就像复制 URL。如果你访问该 URL，你就会得到该 URL 指向的任何数据。网站内容可能已经改变，也可能没有改变。
深度复制就像访问 URL 并复制网站的 HTML，然后将其保存到另一个 URL 下。这样，即使原始 URL 对应的网站发生变化，深度复制后的内容仍将与最初复制时保持一致。
string(const string& s)
:_str(new char[strlen(s._str)+ 1])
{
strcpy(_str, s._str);
} //深拷贝的构造
string& operator =(const string& s) {
if (this != &s) {
char* tmp = new char[strlen(s._str) +1];//加入'\0'
strcpy(tmp,s._str);
delete[] _str; //防止内存泄漏
_str = tmp;
return *this;
}//深拷贝的复制
string对象中存储指针，指针指向的数组中存储字符，字符最后必须保留\0;
注意点：
_size和_capacity区别：
_size:已经有多少个有效字符
_capacity:能存多少个有效字符’\0’不算有效字符
String的实现
test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include "string.h"
int main() {
clz::test_string2();
clz::test_string1();
clz::test_string3();
clz::test_string4();
clz::test_string5();
string s2;
string s1("hello"); //hello在常量区，不可被修改
/*for (size_t i = 0; i < s1.size(); ++i) {
s1[i] += 1;
cout << s1[i] << " ";
}*/
//cout << endl;
}
string.h
#define _CRT_SECURE_NO_WARNINGS
#pragma
#include<assert.h>
namespace clz {
//实现一个string -> 深浅拷贝的问题
//实现一个支持增删查改的string
class string {
public:
typedef char* iterator;
iterator begin()
{
return _str; //返回首地址
}
iterator end()
{
return _str + _size;
}
/*string()
: _str(new char[1])
{
_str[0] = '\0';
}
string(const char* str)
:_str(new char[strlen(str)+ 1])
{
strcpy(_str, str);
}
size_t size() {
return strlen(_str);
}*/
string(const char* str = "")
: _size(strlen(str))
, _str(new char[strlen(str) + 1])
,_capacity(_size)
{
strcpy(_str, str);
}
~string() {
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
//const char& operator[](size_t i)const {
//return _str[i];
//}
string(const string& s)
:_str(new char[strlen(s._str)+ 1])
{
strcpy(_str, s._str);
} //深拷贝的构造
string& operator =(const string& s) {
if (this != &s) {
char* tmp = new char[strlen(s._str) +1];
strcpy(tmp,s._str);
delete[] _str;
_str = tmp;
return *this;
}
} //深拷贝的赋值
/*~string() {
delete[] _str;
_str = nullptr;
}*/
size_t size() const{
return _size;
}
size_t capacity() const {
return _capacity;
}
/*char& operator[](size_t i) {
return _str[i];
}*/
/*const char* c_str() {
return _str;
}*/
char& operator[](size_t i) {
assert(i < _size);
return _str[i];
}
const char& operator[](size_t i)const
{
assert(i < _size);
return _str[i];
}
const char* c_str() {
return _str;
}
void reserve(size_t n) {
if (n > _capacity) {
char* newstr = new char[n + 1];//开空间多开一个给\0
strcpy(newstr, _str);
delete[] _str;
_str = newstr;
_capacity = n;
}//将容量扩展到n
}
void resize(size_t n, char ch = '\0') {
if (n < _size) {
_str[n] = '\0';
_size = n;
}
else {
if (n > _capacity) {
reserve(n);
}
for (size_t i = _size; i < n; i++) {
_str[i] = ch;
}
_size = n;
_str[_size] = '\0';
}
}
void push_back(char ch) {
//空间满了进行增容
if (_size == _capacity) {
size_t newcapacity = _capacity == 0 ? 2 : _capacity * 2;
reserve(newcapacity);
/*char* newstr = new char[newcapacity + 1];//开空间多开一个给\0
strcpy(newstr, _str);
delete[] _str;
_str = newstr;
_capacity = newcapacity;*/
}
_str[_size] = ch;
++_size;
_str[_size] = '\0'; //内存问题一般是构造函数冲突或者不能正确终止
}
void append(const char* str) {
size_t len = strlen(str);
if (_size + len > _capacity) {
reserve(_size + len);
/*size_t newcapacity = _size + len;
char* newstr = new char[newcapacity + 1];
strcpy(newstr, _str);
delete[] _str;
_str = newstr;
_capacity = newcapacity;
*/
}
strcpy(_str + _size, str);
_size += len;
_str[_size] = '\0';
}
//减少逻辑重复代码，使用接口
//strcat
void insert(size_t pos, char ch) {
assert(pos < _size);
if (_size == _capacity)
{
size_t newcapacity = _capacity == 0 ? 2 : _capacity * 2;
reserve(newcapacity);
}
int end = _size;
while (end >= pos) {
_str[end + 1] = _str[end];
--end;
}
_str[pos] = ch;
++_size;
}
string& insert(size_t pos, const char* str) {
assert(pos < _size);
size_t len = strlen(str);
if (_size + len > _capacity) {
reserve(_size + len);
}
int end = _size;
while (end >= pos) {
_str[end + len] = _str[end];
end--;
}
for (size_t i = 0; i < len; i++) {
_str[pos++] = str[i++];
}
strncpy(_str + pos, str,len); //遇见0结束//memorycopy
_size += len;
//_str[_size] = '\0';
return *this;
}
void erase(size_t pos, size_t len = npos) {
assert(pos < _size);
if (len >= pos + _size) {
_str[pos] = '\0';
}
else {
size_t i = pos + len;
while (i <= _size) {
_str[i - len] = _str[i];
++i; //_str[pos++] = _str[i++];
}
_size -= len;
_str[_size] = '\0';
}
}
size_t find(char ch, size_t pos = 0) {
for (size_t i = pos; i < _size; ++i) {
if (_str[i] == ch) {
return i;
}
}
return npos;
}
size_t find(const char* str, size_t pos = 0) {
char* p = strstr(_str, str);
if (p == nullptr) {
return npos;
}
return p - _str;
}
bool operator<(const string& s) {
int ret = strcmp(_str, s._str);
return ret < 0;
}
bool operator>(const string& s) {
return !(*this < s);
}
bool operator==(const string& s){
int ret = strcmp(_str, s._str);
return ret == 0;
}
bool operator>=(const string& s) {
return *this > s || *this == 0;
}
bool operator<=(const string& s) {
return !(*this > s);
}
bool operator!=(const string& s) {
return !(*this == s);
}
string& operator += (char ch) {
this->push_back(ch);
return *this;
}
string& operator +=(const char* str) {
this->append(str);
return *this;
}
private:
char* _str;
size_t _size; //已经有多少个有效字符
size_t _capacity; //能存多少个有效字符,\0不是有效字符
static size_t npos;
};
size_t string::npos = -1;
ostream& operator<<(ostream& out, const string& s)
{
for (size_t i = 0; i < s.size(); ++i) {
out << s[i] ;
}
return out;
}
//getline 接受空格
istream& operator>>(iostream& in, string& s)
{
while (1) {
char ch;
ch = in.get();//in >> ch;可以接收到换行
if (ch == '\n' || ch == ' ') {
break;
}
else {
s += ch;
}
}
return in;
}
/*void test_string1() {
string s1("hello"); //hello在常量区，不可被修改
string s2;
for (size_t i = 0; i < s1.size(); ++i) {
s1[i] += 1;
cout << s1[i] << " ";
}
cout << endl;
for (size_t i = 0; i < s2.size(); ++i) {
s2[i] += 1;
cout << s2[i] << " ";
}
cout << endl;
}
*/
void test_string2() {
/*string s1("hello");
string s2(s1);
string s3("world");
s1= s3;
cout << s1.c_str() << endl;
cout << s2.c_str() << endl;
cout << s3.c_str() << endl;*/
string s1;
string s2("hello");
//cout << s1 << endl;
//cout << s2 << endl;
//cout << s1.c_str() << endl;
//cout << s2.c_str() << endl;
for (size_t i = 0; i < s2.size(); ++i) {
s2[i] += 1;
//cout << s2[i] << " ";
}
cout << endl;
string::iterator it2 = s2.begin();
while (it2 != s2.end()) {
*it2 -= 1;
cout << *it2 << " ";
++it2;
}
cout << endl;
//范围for是由迭代器支持的，会被编译器替换成迭代器
for (auto e : s2)
{
cout << e << " ";
}
cout << endl;
}
void test_string1() {
string s1("hello");
s1.push_back(' ');
s1.push_back('w');
s1.push_back('0');
s1.append("rid xxxxxxxxxxxxxxxxx");
string s2;
s2 += "hello";
s2 += "hello";
s2 += "hello";
s2 += "hello";
//cout << s1 << endl;
//cout << s2 << endl;
}
void test_string3() {
string s1("hello");
s1.insert(1, 'x');
s1.insert(1, "xyz");
cout << s1 << endl;
}
void test_string4() {
string s2("hello");
s2.resize(8, 'x');
cout << s2 << endl;
cout << s2.size() << endl;
cout << s2.capacity() << endl;
s2.resize(18, 'a');
cout << s2 << endl;
cout << s2.size() << endl;
cout << s2.capacity() << endl;
s2.resize(2);
cout << s2 << endl;
cout << s2.size() << endl;
cout << s2.capacity() << endl;
}
void test_string5() {
string s1 = ("helloworld");
s1.erase(5, 2);
cout << s1 << endl;
s1.erase(5, 5);
cout << s1 << endl;
size_t pos = s1.find("he");
cout << pos << endl;
}
}
//插入字符串，空间不够怎么办，怎么扩容
//string对象中存储指针，指针指向的数组中存储字符，字符最后必须保留\0;
//拷贝构造和赋值
namespace copy {
class string {
public:
string(const char* str = " ")
:_str(new char[strlen(str) + 1]) {
strcpy(_str, str);
}
string(const string& s)
:_str(nullptr)
{
string tmp(s._str);
swap(_str, tmp._str);
}
string& operator = (const string s) {
if (this != &s) {
string tmp(s);
swap(_str, tmp._str);
}
return *this;
}
private:
char* _str;
};
}
vector
vector接口
assign:
- assign(size,value)
- v.assign(v1.begin(),v1.end())
- assign(str.begin(),str.end())
- assign(++str.begin(),–str.end());
void test_vector3(){
vector<int>v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
for(auto e:v){
cout << e << " ";
}
cout << endl;
v.assign(10,1);
for(auto e:v){
cout << e <<" ";
}
cout << endl;
vector<int>v1;
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);
v.assign(v1.begin(),v1.end());
for(auto e:v){
cout << e <<" ";
}
cout << endl;
string str("hello world");
v.assign(str.begin(),str.end());
for(auto e:v){
cout << e <<" ";
}
cout << endl;
v.assign(++str.begin(),--str.end());
for(auto e:v){
cout << e <<" ";
}
cout << endl;
}
Insert elements
该函数在指定位置的元素之前插入新元素，从而通过插入的元素数量有效地增加了容器大小。
返回值：
该函数返回一个迭代器，该迭代器指向新插入的元素。
swap 和 find
find
InputIterator find (InputIterator first, InputIterator last, const T& val)
swap
成员函数：
void swap (vector& x);
std::swap
template <class T> void swap (T& a, T& b) noexcept (is_nothrow_move_constructible<T>::value && is_nothrow_move_assignable<T>::value);
template <class T, size_t N> void swap(T (&a)[N], T (&b)[N]) noexcept (noexcept(swap(*a,*b)));
示例：
void test_vector4(){
vector<int>v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.insert(v.begin(),4);
v.insert(v.begin()+2,4);
vector<int>::iterator it = find(v.begin(),v.end(),3);
if(it != v.end()){
v.insert(it,30);
}
for(auto e : v){
cout << e << " ";
}
cout << endl;
vector<int> v1;
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);
v1.swap(v);
for(auto e : v){
cout << e << " ";
}
cout << endl;
swap(v1,v);
for(auto e : v){
cout << e << " ";
}
cout << endl;
}
clear
从向量中移除所有元素（这些元素将被销毁），使容器的大小为 0。
void clear() noexcept;
resize()和reserve()
resize()
resize()调整vector 的size()，使其包含 n 个元素。
如果 n 小于vector 的size()，内容将被缩减为前 n 个元素，超出的元素将被移除（并销毁）。
如果 n 大于当前vector 的size()，内容将通过在末尾插入所需数量的元素进行扩展，以达到 n 的大小。如果指定了 val，新元素将被初始化为 val 的副本，否则将进行值初始化。
如果 n 也大于当前vector的capacity()，将自动重新分配分配的存储空间。请注意，此函数通过插入或删除元素来改变vector的实际内容。
void resize (size_type n);
void resize (size_type n, const value_type& val);
reserve()
请求vector capacity()至少设置为可以容纳 n 个元素。
如果 n 大于当前向量容量，该函数会导致容器重新分配(reallocate)其存储，将capacity()增加到 n（或更大）。
在所有其他情况下，函数调用不会导致重新分配，并且capacity()不会受到影响。
该函数不会影响vector size()，也无法更改其元素。
void reserve (size_type n);
shrink_to_fit()
请求vector减少其capacity以适应其大小。该请求是非约束性的，容器实现可以自由进行其他优化，并且可以使vector的capacity大于其大小。这可能会导致reallocation，但不会影响vector的size，也不会改变其元素。
void shrink_to_fit();
注意：
reserve()后，capacity明显大于size时，请求更易同意，resize后不易发生
如果想强制缩容
推荐：
vector<int>(v).swap(v);
- 注：clear():清空使用量/元素（size），并不清除内存占用量
erase
返回值
一个指向上一个被函数调用删除的元素之后的新位置的迭代器。如果操作删除了序列中的最后一个元素，则返回容器的末尾。
通过这个解决迭代器失效
void test_vector6(){
vector<int>v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
vector<int>::iterator it = v.begin();
while(it != v.end()){
if(*it % 2 == 0){
it = v.erase(it);
}
else{
++it;
}
}
}
new
尝试分配和初始化指定或占位符类型的对象的对象或数组，并返回对象（或数组的初始对象）的适当类型化非零指针。
Default allocation functions (single-object form).
(1) 分配size大小字节的存储空间，适当对齐以表示该大小的任何对象，并返回指向该块第一个字节的非空指针。
(2) 与(1)相同，只是在失败时返回空指针而不是抛出异常。
注：如果被替换，（1）和（2）都将返回具有相同属性的指针。
(3)简单地返回 ptr (没有分配存储空间). 请注意，如果函数被 new-expression 调用，将执行适当的初始化 (对于类对象，这包括调用其默认构造函数)。
void* operator new (std::size_t size) throw (std::bad_alloc); //T* p = new T;delete p;
void* operator new (std::size_t size, const std::nothrow_t& nothrow_value) throw(); //T* p = new T[10];delete[] p;
void* operator new (std::size_t size, void* ptr) throw();
new与malloc区别:
new会调用构造函数+malloc
placement new在原地址空间调用构造函数
memcpy
将数字字节值从源指向的位置直接复制到目标指向的内存块。
源指针和目标指针指向的对象的基本类型与此函数无关；结果是数据的二进制副本。
函数不会检查源代码中是否存在任何终止 null 字符 —— 它总是精确地复制 num 字节。
为了避免溢出，目标和源参数指向的数组大小应至少为数字字节，且不应重叠 (对于重叠的内存块，memove 是一种更安全的方法)。
void * memcpy ( void * destination, const void * source, size_t num );
注意：与memmove区分
memmove：对于重叠地址的拷贝更加安全（滑动窗口）
mem系列函数按字节处理，memset只适合初始化为0
示例：
void reserve(const T& x){
if(n>capacity()){
T*tmp=new T[n];
size_t sz = size();
if(_start){
memcpy(tmp,_start,sizeof(T)*sz());
delete[] _start;
}
_start = tmp;
_finish = tmp+sz;//_finish = tmp+size();避免使用之前已经释放的指针与现在的指针求size()和capacity()
_endofstorage = tmp + n;//_endofstorage = tmp+cpacity();
}
}
vector的实现
test.cpp
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#include "vector.h"
void test_vector1() {
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
vector<int> v2(v1);
for (size_t i = 0; i < v1.size(); ++i) {
cout << v1[i] << " ";
}
cout << endl;
vector<int> v3;
v3.push_back(10);
v3.push_back(20);
v3.push_back(30);
v3.push_back(40);
v1 = v3;
for (size_t i = 0; i < v1.size(); ++i) {
cout << v1[i] << " ";
}
cout << endl;
}
void test_vector2() {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
//遍历修改数据
for (size_t i = 0; i < v.size(); ++i) {
cout << v[i] << " ";
}
//迭代器
vector<int>::iterator it = v.begin();
while(it != v.end()){
cout << *it << " ";
++it;
}
cout << endl;
//范围for
for (auto e : v) {
cout << e << " ";
}
cout << endl;
}
/*void print_vector(const vector<int>& vt) {
vector<int>::const_iterator it = vt.begin();
while (it != vt.end()) {
cout << *it << " ";
it++;
}
cout << endl;
}*/
//三种类型的迭代器
void test_vector3() {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
//普通正向迭代器，可读可写
vector<int>::iterator it = v.begin();
while (it != v.end()) {
cout << *it << " ";
++it;
}
cout << endl;
// print_vector(v);
//只读，const迭代器
/*vector<int>::const_iterator it1 = v.begin();
while (it1 != v.end()) {
cout << *it1 << " ";
++it1;
}
cout << endl;*/
//反向迭代器 reverse逆置reserve保留
vector<int>::reverse_iterator rit = v.rbegin();
while (rit != v.rend()) {
cout << *rit << " ";
++rit;
}
cout << endl;
}
void test_vector4() {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
cout << v.size() << endl;
cout << v.capacity() << endl;
size_t sz;
std::vector<int>foo;
foo.reserve(1067);
foo.resize(1067);
//resize 可以扩容或者缩容并进行初始化·，缩容时，size（使用量）改变，capacity（容量）不变
}
void test_vector5() {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
//v[4] 终止程序v.at(4)抛异常
v.insert(v.begin(), 0);
v.insert(v.begin(), -1);
for (auto e : v) {
cout << e << " ";
}
cout << endl;
v.erase(v.begin());
for (auto e : v) {
cout << e << " ";
}
cout << endl;
}
void test_vector6() {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(40);
v.push_back(100);
v.push_back(5);
vector<int>::iterator pos = find(v.begin(), v.end(), 5);
if (pos != v.end()) {
v.erase(pos);
}
}
void test_vector8() {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
vector<int>::iterator it = v.begin();
v.push_back(6);
v.push_back(7); //扩容导致迭代器失效
while (it != v.end()) {
cout << *it << " ";
++it;
}
cout << endl;
}
void test_vector9() {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
vector<int>::iterator it = v.begin();
//要求删除容器中所有偶数
while (it != v.end()) {
if (*it % 2 == 0) {
it = v.erase(it); //v.erase(it)错误的
}
++it; //删除it之后，it就失效了，失效指it的位置不对了，++it不可以了，vs报错是编译错误，gcc下没有进行严格的检查，可能会报错，也可能个别偶数没有删除
}
for (auto& e : v) {
cout << e << " ";
}
cout << endl;
}
int main() {
//test_vector1();
//test_vector3();
//clz::test_vector1();
//clz::test_vector2();
clz::test_vector4();
return 0;
}
vector.h
#pragma once
#include <assert.h>
#include<string>
#include<algorithm>
namespace clz {
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
}
/*vector(const vector<T>& v) {
_start = new T[v.capacity()];
_finish = _start;
_endofstorage = _start + v.capacity();
for (size_t i = 0; i < v.size(); ++i) {
*_finish = v[i];
++_finish;
}
}*/
/*vector<T>& operator=(const vector<T>& v) {
if (this != &v) {
delete[] _start;
_start = new T[v.capacity()];
memcpy(_start, v._start, sizeof(T) * v.size());
}
return *this;
}*/
vector<T>& operator =(vector<T> v) {
swap(_start, v._start);
swap(_finish, v._finish);
swap(_endofstorage, v._endofstorage);
return *this;
}
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
void swap(vector<T>& v) {
::swap(_start, v._start);
::swap(_finish, v._finish);
::swap(_endofstorage, v._endofstorage);
}//涉及深拷贝，建议自己写swap函数
~vector() {
delete[] _start;
_start = _finish= _endofstorage = nullptr;
}
iterator begin() {
return _start;
}
iterator end() {
return _finish;
}
const_iterator begin()const {
return _start;
}
const_iterator end() const {
return _finish;
}
void reserve(size_t n) {
if (n > capacity()) {
size_t sz = size();
T* tmp = new T[n];
if (_start) {
// memcpy(tmp, _start, sizeof(T) * sz); //在使用string类型时，会导致深层次的深浅拷贝问题,按字节拷贝，浅拷贝
for (size_t i = 0; i < sz; i++) {
tmp[i] = start[i];//调用operator赋值，调用深拷贝
}
delete[] _start;
_start = tmp;
}
_start = tmp;
_finish = tmp + sz;
_endofstorage = tmp + n;
}
}
void push_back(const T& x) {
/*if (_finish == _endofstorage) {
size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2; //先判断capacity()是否==0，如果==0则大小为2，如果不为0，大小为2*capacity()
reserve(newcapacity);
}
*_finish = x;
++_finish;*/
insert(_finish,x);
}
size_t size() const{
return _finish - _start;
}
size_t capacity() const{
return _endofstorage - _start;
}
void pop_back() {
/*assert(_start < _finish);
--_finish;*/
erase(_finish);
}
void insert(iterator pos, const T& x) {
assert(pos <= _finish);
if (_finish == _endofstorage) {
size_t n = pos - _start;
size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;
reserve(newcapacity);
pos = _start + n; //有迭代器失效的问题，如果增容原来的pos就失效了，需要重新计算位置
}
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1);
--end;
}
*pos = x;
++_finish;
}
void resizee(size_t n,const T& val = T()) {
if (n < size()) {
_finish = _start + n;
}
else {
if (n > capacity()) {
reserve(n);
}
while (_finish < _start + n) {
*_finish = val;
++_finish;
}
}
}
iterator erase(iterator pos) {
assert(pos < _finish);
iterator it = pos;
while (it < _finish) {
*it = (*it + 1);
++it;
}
--_finish;
return pos;
}
T& operator[](size_t i) {
assert(i < size());
return _start[i];
}
const T& operator[](size_t i)const {
assert(i < size());
return _start[i];
}
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
void print_vector(const vector<int>& v) {
vector<int>::const_iterator it = v.begin();
while (it != v.end()) {
cout << *it << " ";
++it;
}
cout << endl;
}
void test_vector1() {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
print_vector(v);
for (auto& e : v) {
cout << e << " ";
}
cout << endl;
for (size_t i = 0; i < v.size(); ++i) {
cout << v[i] << " ";
}
cout << endl;
vector<int>::iterator it = v.begin();
while (it != v.end()) {
if (*it % 2 == 0) {
it = v.erase(it);
}
else {
++it;
}
}
print_vector(v);
}
void test_vector2() {
vector<int> v;
v.reserve(10);
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
v.push_back(7);
print_vector(v);
cout << v.size() << endl;
cout << v.capacity() << endl << endl;
v.resizee(4);
print_vector(v);
cout << v.size() << endl;
cout << v.capacity() << endl << endl;
v.resizee(8);
print_vector(v);
cout << v.size() << endl;
cout << v.capacity() << endl << endl;
}
void test_vector4() {
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
vector<int> v2(v1);
for (size_t i = 0; i < v1.size(); ++i) {
cout << v1[i] << " ";
}
cout << endl;
for (size_t i = 0; i < v2.size(); ++i) {
cout << v2[i] << " ";
}
cout << endl;
vector<int>v3 = v1;
for (size_t i = 0; i < v2.size(); ++i) {
cout << v3[i] << " ";
}
}
void test_vector5() {
vector<string> v;
v.push_back("11111111");
v.push_back("22222222");
v.push_back("33333333");
for (auto e : v) {
cout << e << " ";
}
cout << endl;
}
}
list
vector和list对比
vector缺点：
- 头部和中部的插入删除效率低，O(N),需要移动数据
- 插入数据空间不够增容，增容需要开空间，拷贝数据，会付出很大代价
优点：
- 支持下标的随机访问，间接的很好支持排序，二分查找，堆算法
list优点：
- list头部，中间插入不需要挪动数据，效率高，O(1)
- list插入数据是新增节点，不与要增容
缺点：
- 不支持随机访问
list和vector是相辅相成的
list实现
list.h
#pragma once
#include<iostream>
namespace clz
{
template<class T>
struct list_node{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& x)
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
};
// template<class T,class Ref,class Ptr>
// struct _list_iterator{
// typedef list_node<T> node;
// typedef _list_iterator<T,Ref,Ptr>Self;
// node* _pnode;
// _list_iterator(node* p)
// :_pnode(p)
// {}
// Ptr operator->(){
// return &_pnode->_data;
// }
// Ref operator*(){
// return _pnode->_data;
// }
// Self& operator++(){
// _pnode = _pnode->_next;
// return *this;
// }
// Self operator++(int){
// Self tmp(*this);
// _pnode = _pnode->_next;
// return tmp;
// }
// Self operator--(){
// _pnode = _pnode ->_prev;
// return *this;
// }
// Self operator--(int){
// Self tmp(*this);
// _pnode = _pnode->_prev;
// return tmp;
// }
// bool operator!=(const Self& it)const{
// return _pnode != it._pnode;
// }
// bool operator==(const Self& it)const{
// return _pnode == it._pnode;
// }
// };
template<class T>
struct _list_iterator{
typedef list_node<T> node;
node* _pnode;
_list_iterator(node* p)
:_pnode(p)
{}
T& operator*(){
return _pnode->_data;
}
T* operator->(){
return &_pnode->_data;
}
_list_iterator<T>& operator++(){
_pnode = _pnode->_next;
return *this;
}
_list_iterator<T>& operator++(int){
_list_iterator<T> tmp(*this);
++(*this);
return tmp;
}
_list_iterator<T>& operator--(){
_pnode = _pnode->_prev;
return *this;
}
_list_iterator<T>& operator--(int){
_list_iterator<T> tmp(*this);
--(*this);
return tmp;
}
bool operator!=(const _list_iterator<T>& it){
return _pnode!=it._pnode;
}
};
template<class T>
class list{
typedef list_node<T> node;
public:
typedef _list_iterator<T> iterator;
// typedef _list_iterator<T,const T&>const_iterator;
iterator begin(){
return iterator(_head->_next);
}
// const_iterator begin() const{
// return const_iterator(_head->_next);
// }
iterator end(){
return iterator(_head);
}
// const_iterator end()const{
// return const_iterator(_head);
// }
// void empty_initialize(){
// _head = new node(T());
// _head->_next = _head;
// _head->_prev = _head;
// _size = 0;
// }
// list(){
// empty_initialize();
// }
//lt2(lt1)
// list(const list<T>& lt){
// empty_initialize();
// for(const auto& e : lt){
// push_back(e);
// }
// }
// //lt1 = lt3
// list<T>& operator=(const list<T>& lt){
// if(this != <){
// clear();
// for(const auto& e : lt){
// push_back(e);
// }
// }
// return *this;
// }
// template <class InputIterator>
// list(InputIterator first,InputIterator last)
// {
// empty_initialize();
// while(first != last){
// push_back(*first);
// ++first;
// }
// }
// void swap(list<T>& lt){
// std::swap(_head,lt._head);
// std::swap(_size,lt._size);
// }
// list(const list<T>& lt){
// empty_initialize();
// list<T> tmp(lt.begin(),lt.end());
// swap(tmp);
// }
// list<T>& operator=(list<T> lt){
// swap(lt);
// return *this;
// }
// T* operator->(){
// return &_pnode->_data;
// }
// size_t size() const{
// return _size;
// }
// bool empty() const{
// return _size == 0;
// }
list(){
_head = new node(T());
_head->_next = _head;
_head->_prev = _head;
}
// list(const list<T>& lt);
// list<T>& operator(const list<T>& lt);
// ~list(){
// clear();
// delete _head;
// _head = nullptr;
// }
// void clear(){
// iterator it = begin();
// while(it != end()){
// // erase(it++);
// it = erase(it);
// }
// }
void push_back(const T& x){
node* newnode = new node(x);
node* tail = _head->_prev;
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next= _head;
_head->_prev = newnode;
// _size++;
}
void pop_back(){
// erase(--end());
}
// void push_front(const T& x){
// insert(begin(),x);
// }
void pop_front(){
// erase(begin());
}
// iterator insert(iterator pos,const T& x){
// node* newnode = new node(x);
// node* cur = pos._pnode;
// node* prev = cur->_prev;
// prev->_next = newnode;
// newnode->_prev = prev;
// newnode->_next = cur;
// cur->_prev = newnode;
// ++_size;
// return iterator(newnode);
// }
// iterator erase(iterator pos){
// assert(pos!= end());
// node* prev = pos._pnode->_prev;
// node* next = pos._pnode->_next;
// prev->_next = next;
// next->_prev = prev;
// delete pos._pnode;
// --_size;
// return iterator(next);
// }
private:
node* _head;
// size_t _size;
};
// void test_list2(){
// // std::cout<<"list 2"<<std::endl;
// list<Date> lt;
// lt.push_back(Date());
// lt.push_back(Date());
// list<Date>::iterator it = lt.begin();
// while(it != lt.end()){
// // std::cout << *it << " ";
// std::cout << it->_year<<"-"<<it->_month<<"-"<<it->_day<<" ";
// }
// std::cout << std::endl;
// }
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while(it != lt.end()){
std::cout << *it << " ";
++it;
}
std::cout << std::endl;
for(auto e:lt){
std::cout << e << " ";
}
std::cout << std::endl;
}
struct Date{
int _year = 0;
int _month =1;
int _day = 1;
};
// void test_list2(){}
void test_list2(){
list<Date> lt;
lt.push_back(Date());
lt.push_back(Date());
list<Date>::iterator it = lt.begin();
while(it != lt.end()){
// std::cout << *it << " ";
std::cout << it->_year<<"-"<<it->_month<<"-"<<it->_day<<" ";
++it;
}
std::cout << std::endl;
}
// void print_list(const list<int>& lt){
// list<int>::const_iterator it = lt.begin();
// while(it != lt.end()){
// std::cout << *it << std::endl;
// ++it;
// }
// }
void test_list3(){
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
}
}
list.h
#pragma once
#include<iostream>
namespace clz
{
template<class T>
struct list_node{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& x)
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
};
// template<class T,class Ref,class Ptr>
// struct _list_iterator{
// typedef list_node<T> node;
// typedef _list_iterator<T,Ref,Ptr>Self;
// node* _pnode;
// _list_iterator(node* p)
// :_pnode(p)
// {}
// Ptr operator->(){
// return &_pnode->_data;
// }
// Ref operator*(){
// return _pnode->_data;
// }
// Self& operator++(){
// _pnode = _pnode->_next;
// return *this;
// }
// Self operator++(int){
// Self tmp(*this);
// _pnode = _pnode->_next;
// return tmp;
// }
// Self operator--(){
// _pnode = _pnode ->_prev;
// return *this;
// }
// Self operator--(int){
// Self tmp(*this);
// _pnode = _pnode->_prev;
// return tmp;
// }
// bool operator!=(const Self& it)const{
// return _pnode != it._pnode;
// }
// bool operator==(const Self& it)const{
// return _pnode == it._pnode;
// }
// };
template<class T>
struct _list_iterator{
typedef list_node<T> node;
node* _pnode;
_list_iterator(node* p)
:_pnode(p)
{}
T& operator*(){
return _pnode->_data;
}
T* operator->(){
return &_pnode->_data;
}
_list_iterator<T>& operator++(){
_pnode = _pnode->_next;
return *this;
}
_list_iterator<T>& operator++(int){
_list_iterator<T> tmp(*this);
++(*this);
return tmp;
}
_list_iterator<T>& operator--(){
_pnode = _pnode->_prev;
return *this;
}
_list_iterator<T>& operator--(int){
_list_iterator<T> tmp(*this);
--(*this);
return tmp;
}
bool operator!=(const _list_iterator<T>& it){
return _pnode!=it._pnode;
}
};
template<class T>
class list{
typedef list_node<T> node;
public:
typedef _list_iterator<T> iterator;
// typedef _list_iterator<T,const T&>const_iterator;
iterator begin(){
return iterator(_head->_next);
}
// const_iterator begin() const{
// return const_iterator(_head->_next);
// }
iterator end(){
return iterator(_head);
}
// const_iterator end()const{
// return const_iterator(_head);
// }
// void empty_initialize(){
// _head = new node(T());
// _head->_next = _head;
// _head->_prev = _head;
// _size = 0;
// }
// list(){
// empty_initialize();
// }
//lt2(lt1)
// list(const list<T>& lt){
// empty_initialize();
// for(const auto& e : lt){
// push_back(e);
// }
// }
// //lt1 = lt3
// list<T>& operator=(const list<T>& lt){
// if(this != <){
// clear();
// for(const auto& e : lt){
// push_back(e);
// }
// }
// return *this;
// }
// template <class InputIterator>
// list(InputIterator first,InputIterator last)
// {
// empty_initialize();
// while(first != last){
// push_back(*first);
// ++first;
// }
// }
// void swap(list<T>& lt){
// std::swap(_head,lt._head);
// std::swap(_size,lt._size);
// }
// list(const list<T>& lt){
// empty_initialize();
// list<T> tmp(lt.begin(),lt.end());
// swap(tmp);
// }
// list<T>& operator=(list<T> lt){
// swap(lt);
// return *this;
// }
// T* operator->(){
// return &_pnode->_data;
// }
// size_t size() const{
// return _size;
// }
// bool empty() const{
// return _size == 0;
// }
list(){
_head = new node(T());
_head->_next = _head;
_head->_prev = _head;
}
// list(const list<T>& lt);
// list<T>& operator(const list<T>& lt);
// ~list(){
// clear();
// delete _head;
// _head = nullptr;
// }
// void clear(){
// iterator it = begin();
// while(it != end()){
// // erase(it++);
// it = erase(it);
// }
// }
void push_back(const T& x){
node* newnode = new node(x);
node* tail = _head->_prev;
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next= _head;
_head->_prev = newnode;
// _size++;
}
void pop_back(){
// erase(--end());
}
// void push_front(const T& x){
// insert(begin(),x);
// }
void pop_front(){
// erase(begin());
}
// iterator insert(iterator pos,const T& x){
// node* newnode = new node(x);
// node* cur = pos._pnode;
// node* prev = cur->_prev;
// prev->_next = newnode;
// newnode->_prev = prev;
// newnode->_next = cur;
// cur->_prev = newnode;
// ++_size;
// return iterator(newnode);
// }
// iterator erase(iterator pos){
// assert(pos!= end());
// node* prev = pos._pnode->_prev;
// node* next = pos._pnode->_next;
// prev->_next = next;
// next->_prev = prev;
// delete pos._pnode;
// --_size;
// return iterator(next);
// }
private:
node* _head;
// size_t _size;
};
// void test_list2(){
// // std::cout<<"list 2"<<std::endl;
// list<Date> lt;
// lt.push_back(Date());
// lt.push_back(Date());
// list<Date>::iterator it = lt.begin();
// while(it != lt.end()){
// // std::cout << *it << " ";
// std::cout << it->_year<<"-"<<it->_month<<"-"<<it->_day<<" ";
// }
// std::cout << std::endl;
// }
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while(it != lt.end()){
std::cout << *it << " ";
++it;
}
std::cout << std::endl;
for(auto e:lt){
std::cout << e << " ";
}
std::cout << std::endl;
}
struct Date{
int _year = 0;
int _month =1;
int _day = 1;
};
// void test_list2(){}
void test_list2(){
list<Date> lt;
lt.push_back(Date());
lt.push_back(Date());
list<Date>::iterator it = lt.begin();
while(it != lt.end()){
// std::cout << *it << " ";
std::cout << it->_year<<"-"<<it->_month<<"-"<<it->_day<<" ";
++it;
}
std::cout << std::endl;
}
// void print_list(const list<int>& lt){
// list<int>::const_iterator it = lt.begin();
// while(it != lt.end()){
// std::cout << *it << std::endl;
// ++it;
// }
// }
void test_list3(){
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
}
}
deque简易原理
deque 容器存储数据的空间是由一段一段等长的连续空间构成，各段空间之间并不一定是连续的，可以位于在内存的不同区域。
为了管理这些连续空间，deque 容器用数组（数组名假设为 map）存储着各个连续空间的首地址。
也就是说，map 数组中存储的都是指针，指向那些真正用来存储数据的各个连续空间
当 deque 容器需要在头部或尾部增加存储空间时，它会申请一段新的连续空间，同时在 map 数组的开头或结尾添加指向该空间的指针，由此该空间就串接到了 deque 容器的头部或尾部。
码道开发者社区，聚焦华为云码道 CodeArts 代码智能体，沉淀 Agent、Skill、鸿蒙开发实战内容，供开发者查阅资料、交流技术、分享工程实践
更多推荐
29
0- 0
已为社区贡献1条内容
所有评论(0)