容器

目录

 

1.容器和迭代器

2.容器的适配器allocator.

容器的空间适配器

容器和迭代器的自定义

3.迭代器失效的问题

4.两个不同类型的迭代器能否进行比较

5，Vector总结

---

1.容器和迭代器

平常我们用的string ，char buf[]等都是一些近容器。标准的容器一般都有迭代器和容器适配器。

2.容器的适配器allocator.

目的：把对象的内存开辟和对象的构造分开，把对象的析构和内存释放分开。

construct:构造  如何在一个已经存在的内存上构造对象。

destory:析构    如何只调用对象的析构函数。

allocate:分配内存   malloc

deallocate:释放内存  freee

容器的空间适配器

//容器的空间适配器
template<typename T>
class Allocator
{
public:
	T* allocate(size_t size) // 开辟内存
	{
		return (T*)malloc(size);
	}
	void deallocate(void *ptr) // 释放内存
	{
		free(ptr);
	}
	void construct(T *ptr, const T &val) // 构造
	{
		new (ptr) T(val);//在已经存在的ptr上构造新的对象。
	}
	void destroy(T *ptr) // 析构
	{
		ptr->~T();
	}
};

容器和迭代器的自定义

template<typename T,typename allocator = Allocator<T>>
class Vector
{
    public:
        Vector(int size = 0)
	{
		if (size == 0)
		{
			first._ptr = nullptr;
			last._ptr = nullptr;
			end._ptr = nullptr;
		}
		else
		{
			first._ptr = mAllocator.allocate(size * sizeof(T));
			last._ptr = first._ptr;
			end._ptr = first._ptr + size;
		}
	}
	Vector(int size, const T &val)
	{
		if (size == 0)
		{
			first._ptr = nullptr;
			last._ptr = nullptr;
			end._ptr = nullptr;
		}
		else
		{
			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;		
                }
	}
	Vector(T *_first, T *_last)
	{
		first._ptr = mAllocator.allocate(_last - _first);
		int i = 0;
		for (; i < _last - _first; ++i)
		{
			mAllocator.construct(first._ptr + i, *(_first + i));
		}
		last._ptr = end._ptr = first._ptr + (_last - _first);

	}

	// 从末尾添加元素
	void push_back(const T &val)
	{
		if (full())
			resize();
		//mpVec[mCur++] = val;
		mAllocator.construct(last._ptr++, val);

	}
	// 从末尾删除元素
	void pop_back()
	{
		if (empty())
			return;
		--last._ptr;
		mAllocator.destroy(last._ptr);
		
	}
	bool full()const { return last._ptr == end._ptr; }
	bool empty()const { return last._ptr == first._ptr; }
	// 返回容器元素的个数
	int size()const { return (last -first)/sizeof(T); }
        class iterator
        {
	public:
		iterator(T *p = nullptr) :_ptr(p) {}
		bool operator!=(const iterator &it)
		{
			return _ptr != it._ptr;
		}
		void operator++() { _ptr++; }
		T& operator*() { return *_ptr; }
	private:
		T *_ptr;
        };
        iterator _begin() { return iterator(first._ptr); }
	iterator _end() { return iterator(last._ptr); }
	iterator insert(iterator it, const T &val)
	{
		//first last end 
		if (last._ptr == end._ptr)
		{
			int offset = it._ptr - first._ptr;
			resize();
			it._ptr = first._ptr + offset;
		}
		T *tmp = last._ptr;//最后一个元素的后继地址
		while (tmp != it._ptr)
		{
			mAllocator.construct(tmp._ptr, *(tmp._ptr - 1));
			--tmp._ptr;
			mAllocator.destory(tmp._ptr);

		}
		mAllocator.construct(tmp._ptr, val);
		++last.ptr;
	}
	iterator erase(iterator it)
	{
		T *tmp = it._ptr;
		while (tmp != last._ptr)
		{
			mAllocator.destory(tmp._ptr);
			++tmp._ptr;
			mAllocator.construct(tmp._ptr - 1, *(tmp._ptr));

		}
		mAllocator.destory(tmp._ptr);
		--last.ptr;

		return it;

	}

    private:
	/*T *mpVec;
	int mCur;
	int mSize;*/
	iterator first;
	iterator last;
	iterator end;
	allocator mAllocator; 
        void resize()
	{
		if (first._ptr==nullptr)
		{
			first._ptr = mAllocator.allocate(sizeof(T));
			last._ptr = first._ptr;
			end._ptr = first._ptr + 1;
		}
		else
		{
			int offset = end._ptr - first._ptr;
			T *newdata = mAllocator.allocate((end - first) * 2);
			int i = 0;
			while (first._ptr != end._ptr)
			{
				mAllocator.construct(newdata + i, *(first._ptr));
				++i;
				mAllocator.destory(first._ptr);
				++first._ptr;
			}
			
					mAllocator.deallocate(first._ptr);
			first._ptr = newdata;
			last._ptr = first._ptr +offset;
                        end._ptr = first._ptr +2*offset;
		}
	}
};

3.迭代器失效的问题

插入操作：扩容之后迭代器发生变化。

删除操作：size变化

4.两个不同类型的迭代器能否进行比较

在创建迭代器的时候将当前的地址传入，所以不同容器的迭代器是不能进行比较的，此时会认为迭代器失效。

需要判断：

1）是否是同一个元素。

2）迭代的容器的长度是否一样，迭代过程中，容器元素进行改动，一定要及时更新迭代器。

5，Vector总结

1）底层是2倍扩容的数组。

2）内存扩容的方式是：0-》1-》2-》4.......也可以指定内存的大小

3）添加元素：O(n)，随机访问：O(1)，搜索O(n)。

4）有序的vector 插入 : insert O(n),push_back O(1)

    删除：pop_back O(1) erase O(n)

5)查询：迭代器遍历vector

6）默认的迭代器底层不分配空间

7）reverse() //反转容器

8）reserve()//预留空间  reserve(size),预留size 空间，不添加元素

9）resize(size)  预留size空间，添加元素

10）vec1.swap(vec2) 容器交换，效率很高，只交换first、last等，前提是这两个容器的空间适配器是一样的。