首页 > 其他分享 >STL复习-序列式容器和容器适配器部分

STL复习-序列式容器和容器适配器部分

时间：2024-07-07 21:56:40浏览次数：19  
标签：容器 iterator STL 适配器 list pos str size

STL复习

1. 常见的容器

如何介绍这些容器，分别从常见接口，迭代器类型，底层实现

在这里插入图片描述

序列式容器

string

string严格来说不属于stl，它是属于C++标准库

**底层实现：**string本质是char类型的顺序表，因为不同编译器下的具体实现不同，这里只提供一个我的简答框架

class string
{
public:
    typedef char* iterator;
    typedef const char* const_iterator; 
private:
    char* _str; 		// 堆上开辟的顺序表空间
    size_t _size; 		// 有效字符个数
    size_t _capacity; 	// _str的空间大小

    static const size_t npos; // 最大字符串大小
};

const size_t string::npos = -1;

实际在VS系列下，string是包含一个指针，一个联合体（一个数组和一个指针，如果字符串长度小于16就会使用提前开辟好的数组，如果大于16字节再去堆上申请空间使用指针指向），size和capacity

在g++下string只包含一个指针，指向堆上的一段空间，包含一个指针指向为字符串开辟的空间，引用计数，size和capacity，这个引用计数可以让赋值拷贝这些对象只需要浅拷贝增加引用计数即可

迭代器类型： 随机访问迭代器

常用接口：

函数名功能
size / length返回字符串有效字符个数
clear / reserver / resize清空有效字符 / 预留空间 / 将有效字符的个数该成n个，多出的空间用字符c填充
operator[]返回pos位置的字符
push_back / append / operator+=在字符串后尾插字符c / 字符串 / 字符串
c_str返回C格式字符串
find / rfind + npos从字符串pos位置开始往(后 / 前)找字符c，返回该字符在字符串中的位置，没有返回npos
substr在str中从pos位置开始，截取n个字符，然后将其返回
operator<< / operator>> / getline从iostream中写 / 读 （空格/回车），getline可自定义分隔符
// 剪去报头 length\r\n*******\r\nlength\r
std::string Decode(std::string& str)
{
	// 判断条件是否满足，不满足返回空串
	size_t pos = str.find(SEP);
	if (pos == std::string::npos)
		return "";
	size_t lenght = atoi(str.substr(0, pos).c_str());

	if (lenght > str.size() - pos - SEP_LEN * 2)
		return "";

	str.erase(0, pos + SEP_LEN);
	std::string ret = str.substr(0, lenght);
	str.erase(0, lenght + SEP_LEN);
	return ret;
}

// 简单实现

class string
{
	friend std::ostream& operator<<(std::ostream& out, const string& str);
	//friend istream& operator>>(istream& in, const string& str);
public:
	string() : _str(nullptr), _size(0), _capacity(0)
	{}

	string(const char* str) :string()
	{
		size_t sz = strlen(str);
		_str = new char[sz + 1] {0};
		strcpy(_str, str);
		_size = sz;
		_capacity = sz + 1;
	}

	string(const string& str)
		: string(str.c_str())
	{}

	string& operator==(string str)
	{
		if(this != &str)
			swap(str);
		return *this;
	}

	~string()
	{
		delete[] _str;
	}

	string& operator+=(const string& str)
	{
		size_t sz = str._size;
		if (sz + _size + 1 > _capacity)
		{
			reserve(sz > _capacity ? _capacity + sz : 2 * _capacity);
		}
		strcpy(_str + _size, str.c_str());
		_size += sz;
		return *this;
	}

	char& operator[](size_t pos)
	{
		return *(_str + pos);
	}

	void reserve(size_t newsize)
	{
		if (newsize > _capacity)
		{
			char* str = new char[newsize] {0};
			strcpy(str, _str);
			delete[] _str;
			_str = str;
			_capacity = newsize;
		}
	}

	void swap(string& str)
	{
		std::swap(_str, str._str);
		std::swap(_size, str._size);
		std::swap(_capacity, str._capacity);
	}

	const char* c_str() const 
	{
		return _str;
	}

	size_t size() const
	{
		return _size;
	}

private:
	char* _str;
	size_t _size;
	size_t _capacity;

	static size_t npos;
};

size_t string::npos = -1;

std::ostream& operator << (std::ostream& out, const string& d)
{
	out << d.c_str();
	return out;
}
vector

底层实现：

vector本质是模板类型的顺序表，对于底层数据结构是顺序表类型的容器在每次增容都需要极大的代价，需要开辟更大空间，并对之前的数据进行拷贝，，vs下capacity是按1.5倍增长的，g++是按2倍增长的

reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解string和vector增容的代价缺陷问题

与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list 统一的迭代器和引用更好

template<class T>
class vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;
private:
	iterator _start = nullptr;
	iterator _finish = nullptr;
	iterator _end_of_storage = nullptr;
};

迭代器类型： 随机访问迭代器

常用接口：

函数名功能
size / capacity / empty数据个数 / 容量大小 / 是否为空
reserve / resize / clear改变vector的capacity / size / 清空
push_back / pop_back尾插 / 尾删
find + v.end() （不常用）查找，注意这个是算法模块实现，不是vector的成员接口
insert / erase在pos位置插入删除
emplace / empalce_back构造和插入
operator[]返回pos位置的对象

深拷贝问题，在拷贝构造时如果对像是自定义类型，就会调用自定义类型的拷贝构造

// 简单实现

template<class T>
class vector
{
	typedef T* iterator;
public:
	iterator begain() { return _start; }
	iterator end() { return _finish; }

	vector():_start(nullptr), _finish(nullptr), _end(nullptr)
	{}

	vector(size_t n, T val = T()) :vector()
	{
		reserve(n);
		for (size_t i = 0; i < n; ++i)
		{
			_start[i] = val;
		}
		_finish = _start + n;
	}

	vector(const vector& v) :vector()
	{
		reserve(v.size());
		_finish = _start + v.size();
		for (size_t i = 0; i < v.size(); ++i)
		{
			operator[](i) = v[i];
		}
	}

	~vector(){delete[] _start; }

	void push_back(T val) {insert(_finish, val); }

	void pop_back() {erase(_finish - 1); }

	void insert(iterator pos, T val = T())
	{
		assert(pos >= _start && pos <= _finish);
		if (_finish + 1 > _end)
		{
			size_t pos_size = pos - _start;
			reserve(size() + 1);
			pos = _start + pos_size;
		}
		iterator cur = _finish;
		while (cur != pos)
		{
			*cur = *(cur - 1);
			--cur;
		}
		*pos = val;
		_finish += 1;
	}

	iterator erase(iterator pos)
	{
		assert(pos >= _start && pos < _finish);

		iterator cur = pos;
		while (cur != _finish)
		{
			*cur = *(cur + 1);
			++cur;
		}
		_finish -= 1;
		return pos;
	}

	T& operator[](size_t pos)
	{
		assert(pos < size());
		return _start[pos];
	}

	const T& operator[](size_t pos) const 
	{
		assert(pos < size());
		return _start[pos];
	}

	void reserve(size_t newcapacity)
	{
		size_t capacity = _end - _start;
		size_t size = _finish - _start;
		if (capacity < newcapacity)
		{
			newcapacity = newcapacity < 2 * capacity ? 2 * capacity : newcapacity;
			T* newv = new T[newcapacity];
			if(_start)
				memcpy(newv, _start, size * sizeof(T));
			delete[] _start;
			_start = newv;
			_end = newv + newcapacity;
			_finish = _start + size;
		}
	}

	size_t size() const { return _finish - _start; }
	size_t capacity() const { return _end - _start; }


private:
	iterator _start;
	iterator _finish;
	iterator _end;
};
list

底层实现：

list的底层是带头双向循环链表结构，链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素

与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好

最大的缺陷是不支持任意位置的随机访问，list还需要一些额外的空间，以保存每个节点的相关联信息

template<class T>
struct list_node
{
	typedef list_node<T> node;
	node* _next;
	node* _prev;
	T _date;
};

template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef list_node<T> node;
	typedef __list_iterator<T, Ref, Ptr> self;
	node* _it;
};

template<class T>
class list
{
	typedef list_node<T> node;
public:
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;
private:
	node* _head;
};

迭代器类型： 双向访问迭代器

常用接口：

函数名功能
empty / size判空 / 返回节点个数
front / back返回最后 / 最前节点值的引用
push_front / pop_front头插 / 头删
push_front / pop_back尾插 / 尾删
insert / erase插入 / 删除
emplace / emplace_front / emplace_back构造 + 插入
sort链表的排序
template<class T>
struct list_node
{
	list_node* _prev;
	list_node* _next;
	T _val;

	list_node(T val = T()) :_prev(nullptr), _next(nullptr), _val(val)
	{}
};

template<class T, class Ref, class Ptr>
struct list_iterator
{
	typedef list_node<T> node;
	typedef list_iterator<T, Ref, Ptr> Self;
	node* _it;

	list_iterator(node* it) :_it(it) 
	{}

	list_iterator(const list_iterator<T, T&, T*>& iterator) :_it(iterator._it)
	{}

	Ptr operator->() {return &(_it->_val);}
	Ref operator*() {return _it->_val; }
	Self operator++() {return _it = _it->_next; }
	Self operator--() {return _it = _it->_prev; }
	bool operator!=(const Self& iterator) const {return _it != iterator._it; }
};

template<class T>
struct list
{
	typedef list_node<T> node;
	typedef list_iterator<T, T&, T*> iterator;
	typedef list_iterator<T, const T&, const T*> const_iterator;
public:
	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); }

	list():_head(new node)
	{
		_head->_next = _head;
		_head->_prev = _head;
	}

	~list()
	{
		while (!empty())
		{
			pop_front();
		}
		delete _head;
	}

	void insert(iterator pos, const T& val)
	{
		node* next = pos._it;
		node* prev = next->_prev;
		node* newnode = new node(val);
		prev->_next = newnode;
		newnode->_prev = prev;
		newnode->_next = next;
		next->_prev = newnode;

		_size++;
	}

	void erase(iterator pos)
	{
		assert(pos._it != _head);
		node* next = pos._it->_next;
		node* prev = pos._it->_prev;
		delete pos._it;
		next->_prev = prev;
		prev->_next = next;

		_size--;
	}

	void push_back(const T& val) { insert(end(), val);  }
	void push_front(const T& val) { insert(begin(), val); }

	void pop_back(){erase(_head->_prev); }
	void pop_front(){erase(begin()); }

	bool empty() const
	{
		return _size == 0;
	}
private:
	list_node<T>* _head;
	size_t _size = 0;
};
deque

底层实现：

双端队列由一个指针数组和多个相同长度的定长数组组成

在这里插入图片描述

双端队列，头插尾插，头删尾删效率高，这点比vector要好，但是不如list在任意位置都可以O(1)时间复杂度插入删除（增删）

通过迭代器支持operator[]随机访问，在随机访问上比list要好，但是不如vector（查改）

因为头尾的插入删除效率高，所以他就非常适合stack和queue

迭代器类型： 随机访问迭代器

常用接口：

函数名功能
size / resize / empty大小 / 改变大小 / 判空
operator[] / front / back读数据
push_front / pop_front头插 / 头删
push_front / pop_back尾插 / 尾删
insert / erase插入 / 删除

关联式容器

map/set
unordered_map/unordered_set
bitset

容器适配器

stack

stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。

stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

  • empty：判空操作
  • back：获取尾部元素操作
  • push_back：尾部插入元素操作
  • pop_back：尾部删除元素操作

标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器， 默认情况下使用deque

在这里插入图片描述

函数名功能
stack()构造空的栈
empty检测stack是否为空
size返回stack中元素的个数
top返回栈顶元素的引用
push将元素val压入stack中
pop将stack中尾部的元素弹出
queue

队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。

队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

  • empty：检测队列是否为空
  • size：返回队列中有效元素的个数
  • front：返回队头元素的引用
  • back：返回队尾元素的引用
  • push_back：在队列尾部入队列
  • pop_front：在队列头部出队列

标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque

在这里插入图片描述

函数名功能
queue()构造空的队列
empty检测queue是否为空
size返回queue中元素的个数
front返回queue顶元素的引用
back返回queue尾元素的引用
push将元素val压入queue中
pop将queue中尾部的元素弹出
priority_queue

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)

优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

  • empty()：检测容器是否为空
  • size()：返回容器中有效元素个数
  • front()：返回容器中第一个元素的引用
  • push_back()：在容器尾部插入元素
  • pop_back()：删除容器尾部元素

标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指 定容器类，则使用vector（模板参数第二位）

需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap 来自动完成此操作

默认情况下priority_queue是大堆，使用less（模板参数第三位）

在这里插入图片描述

一句话，少的点挪动的次数多 时间复杂度约等于 T(N)

在这里插入图片描述

多的点挪动次数多 时间复杂度 T(N*LogN)

若是pop n次用来排序，时间复杂度 T(N*LogN)

优先级队列，使用迭代器建堆，比遍历push，要好

函数名功能
priority_queue()构造一个空的优先级队列
priority_queue(first,last)根据迭代器区间构造优先级队列
empty()检测优先级队列是否为空
top()返回优先级队列中最大(最小元素)，即堆顶元素
size()返回优先级队列里的元素个数
push(x)在优先级队列中插入元素x
pop()删除优先级队列中最大(最小)元素，即堆顶元素

杂度 T(N*LogN)

优先级队列，使用迭代器建堆，比遍历push，要好

函数名功能
priority_queue()构造一个空的优先级队列
priority_queue(first,last)根据迭代器区间构造优先级队列
empty()检测优先级队列是否为空
top()返回优先级队列中最大(最小元素)，即堆顶元素
size()返回优先级队列里的元素个数
push(x)在优先级队列中插入元素x
pop()删除优先级队列中最大(最小)元素，即堆顶元素

标签：容器,iterator,STL,适配器,list,pos,str,size
From： https://blog.csdn.net/bananawolf/article/details/140253117

相关文章

  • STL--求交集，并集，差集（set_intersection，set_union，set_difference）
    set_intersection(重要)求两个有序的序列的交集.函数声明如下:template<classInputIterator1,classInputIterator2,classOutputIterator>OutputIteratorset_intersection(InputIterator1_First1,//容器1开头InputIterator1_Last1,//容器2......
  • StarRocks 容器镜像构建
    StarRocks官方只提供了单节点运行的镜像，如果是构建可以分布式运行的StarRocks的容器镜像，那么基于基础镜像可以有两种选择，分别是：starrocks/artifacts-ubuntu和starrocks/allin1-ubuntu，这两个都是基于Ubuntu22.04的基础镜像。其中前者是其中只包含StarRocks编译好的安装文......
  • Python——习题练习 part2 数据容器
    本篇文章记录python数据容器章节的练习题。目录五，数据容器01列表1.列表的常用功能2.列表循环遍历02元组基本操作03字符串的分割04序列的切片05集合信息去重06字典五，数据容器01列表1.列表的常用功能题目如下：答案如下：#列表List的常用操作#定义列表......
  • 【C++/STL】模板进阶(非类型模板&&类模板打印&&特化&&分离编译)
    ✨                       人生便如一首绝句，平平仄仄平平仄       ......
  • 力扣—盛水最大的容器—双指针
    文章目录题目解析解题思路代码实现题目解析解题思路利用单调性控制其中一个变量，使用双指针控制另一个变量。我们知道S1(面积)=h(高度)*w(宽度)。由于高度的大小是随机的不可控，所以我们可以尝试控制宽度，定义变量left和right分别指向数组第一个元素和最后一个元素......
  • STL学习——栈，队列，set，优先队列
    栈：stack容器内元素的访问​由于栈(stack)本身就是一种后进先出的数据结构。在STL中stack中只能通过top()来访问栈顶元素栈上的基本操作栈的基本操作包括：函数名用途push(x)将x入栈top()获得栈顶元素pop()用以弹出栈顶元素empty()可以检测stack内是否为空，返回true为空，返回fa......
  • Docker容器监控之CAdvisor+InfluxDB+Granfana
    1、编写docker-compose.ymlvolumes:grafana_data:{}services:influxdb:image:tutum/influxdbrestart:alwaysenvironment:-PRE_CREATE_DB=cadvisorports:-"8083:8083"-"8086:8086"volumes:-./data/influ......
  • python数据容器（二）元组
    1.数据容器：tuple（元组）（1）定义t1=(1,"Hello",True)t2=()t3=tuple()print(f"t1的类型是：{type(t1)}，内容是：{t1}")print(f"t2的类型是：{type(t2)}，内容是：{t2}")print(f"t3的类型是：{type(t3)}，内容是：{t3}")运行结果：（2）定义单个元素的元素t1=("hel......
  • python数据容器（一）列表list
    思维导图代码1.数据容器入门2.数据容器：list（列表）name_list=['itheima','itcast','python']print(name_list)print(type(name_list))运行结果： name_list=['itheima',666,True]print(name_list)print(type(name_list))运行结果： name_l......
  • Linux容器篇-使用kubeadm搭建一个kubernetes集群
    kubernetes集群架构和组件master节点组件kube-apiserver：KubernetesAPI，集群的统一入口，各组件的协调者，以RESTfulAPI提供接口服务，所有对象资源的增删改查和监听操作都交给APIserver处理后再交给Etcd存储。kube-controller-manager：处理集群中的常规后台事务，一个资源对应......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99