您的位置: 首页  >  文章  >  向量容器

向量容器

分类: 文章 • 2024-12-25 22:01:22

容器（container）

容器是用来存储数据的，数据可以是用户自定义类型（对象），也可以是内置类型。

容器的分类

  • 顺序容器 vector(向量容器) deque(双端队列容器) list(双向链表)

  • 关联容器 set(单重集合) multiset(双重集合) map(单重映射表) multimap(多重映射表)

  • 容器适配器 stack(栈) queue(队列) prority_queue(优先级队列)

向量容器（vector）

定义：向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）
简单的认为，向量是一个能够存放任意类型的动态数组。

特点：

  • 在内存中是一片连续的存储区域，初始化的时候，可以指定容量，比如如果定义容量50 的容器存储 60个string对象，由于初始容量不足60，容器将会重新定义一个容量是原来的2倍新容器，然后构造原容器的对象到新容器，再把原容器的对象进行析构。

  • 读取速度快，插入删除效率低.如果仅仅在容器头或尾部进行增删改，推荐使用deque，专门提供了对首尾的操作。

  • 容器使用一个内存分配器对象来动态地处理它的存储需求。

库中有关顺序容器的函数
1.push_back 在数组的最后添加一个数据
2.pop_back 去掉数组的最后一个数据
3. at 得到编号位置的数据
4.begin 得到数组头的指针
5.end 得到数组的最后一个单元+1的指针
6．front 得到数组头的引用
7.back 得到数组的最后一个单元的引用
8.max_size 得到vector最大可以是多大
9.capacity 当前vector分配的大小
10.size 当前使用数据的大小
11.resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值
12.reserve 改变当前vecotr所分配空间的大小
13.erase 删除指针指向的数据项
14.clear 清空当前的vector
15.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty 判断vector是否为空
18.swap 与另一个vector交换数据

自己实现的顺序容器

容器配置器

  • 将内存的开辟和对象的构造分离开
  • 将内存的释放的对象的析构分离开
template<typename T>
class Allocator
{
public:
	T* allocate(size_t size) // 开辟size大小的内存
	{
		return (T*)malloc(size);
	}
	void deallocate(void *ptr) // 释放内存
	{
		free(ptr);
	}
	void construct(T *ptr, const T &val) // 构造
	{
		new (ptr) T(val);//在已经开辟好的内存上进行构造
	}
	void destroy(T *ptr) // 析构
	{
		ptr->~T();
	}
};

vector实现

template<typename T, typename allocator = Allocator<T>>
class Vector
{
public:
	// 按指定size进行构造，size个空间，没有元素(只分配空间不初始化)
	Vector(int size = 0)
	{
		if (size == 0)
		{
			_first._ptr = _last._ptr = _end._ptr = nullptr;//当size为0不开辟空间
		}
		else
		{
			_first._ptr = mAllocator.allocate(size * sizeof(T));
			_last._ptr = _first._ptr;//没有元素
			_end._ptr = _first._ptr + size;
		}
	}
	// 按指定size进行构造,添加size个元素，元素值是val
	Vector(int size, const T &val)
	{
		_first._ptr = mAllocator.allocate(size * sizeof(T));//先分配空间
		for (int i = 0; i < size; ++i)
		{
			mAllocator.construct(_first._ptr+i, val);//在每一个位置上进行构造
		}
		_last._ptr = _end._ptr = _first._ptr + size;//对空间上的每个元素进行构造
	}
	// 按[first, last)区间的元素来构造Vector
	Vector(T *first, T *last)
	{
		int size = last - first;
		_first._ptr = mAllocator.allocate(size * sizeof(T));
		for (int i=0; first < last; ++first,++i)
		{
			mAllocator.construct(_first._ptr + i, *first);
		}
		_last._ptr = _end._ptr = _first._ptr + size;
	}
	~Vector() 
	{ 
		// 析构有效的对象
		for (T *p=_first._ptr; p < _last._ptr; ++p)
		{
			mAllocator.destroy(p);
		}
		// 释放内存
		mAllocator.deallocate(_first._ptr);
	}
	// 从末尾添加元素
	void push_back(const T &val)
	{
		if (full())
			resize();
		mAllocator.construct(_last._ptr, val);
		_last._ptr++;
	}
	// 从末尾删除元素（保留空间，只对要删除的元素进行析构）
	void pop_back()
	{
		if (empty())
			return;
		--_last._ptr;
		mAllocator.destroy(_last._ptr);
	}
	bool full()const { return _last == _end; }
	bool empty()const { return _last == _first; }
	// 返回容器元素的个数
	int size()const { return _last - _first; }
	




    // Vector的迭代器
	class iterator//作为嵌套类
	{
	public:
		// 定义友元类 
		friend class Vector<T>;

		iterator(T *p = nullptr) :_ptr(p) {}
		bool operator!=(const iterator &it)const
		{
			return _ptr != it._ptr;
		}
		bool operator==(const iterator &it)const
		{
			return _ptr == it._ptr;
		}
		int operator-(const iterator &it)const
		{
			return _ptr - it._ptr;
		}
		void operator++() { _ptr++; }
		void operator--() { _ptr--; }
		T& operator*() { return *_ptr; }
	private:
		T *_ptr; 
	};


//容器的一系列操作


	iterator begin() { return iterator(_first._ptr); }//容器首元素的位置
	iterator end() { return iterator(_first._ptr + size()); }//末尾元素的下一个位置
	
     
     // 给it迭代器的位置，插入一个值为val的对象,返回插入位置的新的迭代器
	iterator insert(iterator it, const T &val)
	{
	
		if (_last == _end)//满了，需要进行扩容，迭代器要进行更新
		{
			int offset = it._ptr - _first._ptr;//旧的迭代器相对于首元素的距离
			resize();//扩容
			it._ptr = _first._ptr + offset;//新的迭代器的位置
		}

		for (T *p = _last._ptr-1; p >= it._ptr; --p)//从后往前，先构造到下一个位置，再析构
		{
			mAllocator.construct(p+1, *p);
			mAllocator.destroy(p);
		}
		++_last;//添加一个对象，_last右移
		mAllocator.construct(it._ptr, val);//在it指向的位置构造新对象
		return it;
	}


// 删除it迭代器指向的位置，返回删除位置的最新的迭代器
	iterator erase(iterator it)  // it _ptr size:10
	{
		for (T *p = it._ptr; p < _last._ptr; ++p)
		{
			mAllocator.destroy(p);//先析构，后构造
			mAllocator.construct(p, *(p+1));
		}
		--_last; // _ptr--  size--
		return it;  // 为什么it没变，要进行返回（size改变了，it实际上已经不是原来的迭代器了）
	}
private:
	iterator _first; // 指向起始位置
	iterator _last; // 最后一个元素的下一个位置
	iterator _end; // 指向末尾的下一个位置
	allocator mAllocator;  // 存储容器的空间配置器

	// 容器内存2倍扩容
	void resize()
	{
		if (_first._ptr == nullptr)//没有空间
		{
			_first._ptr = mAllocator.allocate(sizeof(T));//分配一个
			_last._ptr = _first._ptr;
			_end._ptr = _first._ptr + 1;
		}
		else
		{
			int size = _last._ptr - _first._ptr;
			T *ptmp = mAllocator.allocate(2 * sizeof(T) * size);//2倍扩容
			for (int i = 0; i < size; ++i)
			{
				mAllocator.construct(ptmp+i, _first._ptr[i]);//把原来内存上的对象构造过来
			}
			
	       for (int i = 0; i < size; ++i)
			{
				mAllocator.destroy(_first._ptr + i);//析构原来内存上的对象
			}
			mAllocator.deallocate(_first._ptr);//删除原来的内存
			
			_first._ptr = ptmp;//指向新的内存
			_last._ptr = _first._ptr + size;
			_end._ptr = _last._ptr + size;
		}
	}
};

删除元素

向量容器

添加元素

向量容器

用通用的迭代器遍历方式，遍历vec1(容器)，并打印容器中所有的元素值

	Vector<int>::iterator it1 = vec1.begin();
	for (; it1 != vec1.end(); ++it1)
	{
		cout << *it1 << " ";
	}

foreach遍历

   for (int val : vec)
	{
		cout << val << " ";
	}

CString迭代器

class CString
{
public:
	CString(const char *p = NULL)
	{
		if (p != NULL)
		{
			_pstr = new char[strlen(p) + 1];
			strcpy(_pstr, p);
		}
		else
		{
			_pstr = new char[1];
		    *_pstr = 0;
		}
	}
	~CString()
	{
		delete[]_pstr;
		_pstr = NULL;
	}
	CString(const CString &src)
	{
		_pstr = new char[strlen(src._pstr) + 1];
		strcpy(_pstr, src._pstr);
	}
	CString& operator=(const CString &src)
	{
		if (this == &src)
			return *this;

		delete[]_pstr;

		_pstr = new char[strlen(src._pstr) + 1];
		strcpy(_pstr, src._pstr);
		return *this;
	}
	bool operator>(const CString &src)const
	{
		return strcmp(_pstr, src._pstr) > 0;
	}
	bool operator<(const CString &src)const
	{
		return strcmp(_pstr, src._pstr) < 0;
	}
	bool operator==(const CString &src)const
	{
		return strcmp(_pstr, src._pstr) == 0;
	}

	int length()const { return strlen(_pstr); }
	char operator[](int index)const { return _pstr[index]; }
	const char* c_str()const { return _pstr; }



// 定义CString的迭代器类型
	class iterator
	{
	public:
		// iterator operator!=   operator++   operator*
		iterator(char *p) :_ptr(p) {}
		bool operator!=(const iterator &it)
		{
			return _ptr != it._ptr;
		}
		void operator++()
		{
			_ptr++;
		}
		char& operator*() { return *_ptr; }
	private:
		char *_ptr;
	};
    




    iterator begin() { return iterator(_pstr); } // 返回容器0号元素的迭代器
	iterator end() { return iterator(_pstr + length()); } // 返回容器最后一个元素后继位置的迭代器
private:
	char *_pstr;

	friend CString operator+(const CString &lhs, const CString &rhs);
	friend ostream& operator<<(ostream &out, const CString &str);
};
CString operator+(const CString &lhs, const CString &rhs)
{
	char *p = new char[strlen(lhs._pstr) + strlen(rhs._pstr) + 1];
	strcpy(p, lhs._pstr);
	strcat(p, rhs._pstr);
	CString tmp(p);
	delete []p;
	return tmp;
}
ostream& operator<<(ostream &out, const CString &str)
{
	out << str._pstr;
	return out;
}

相关推荐