STL—— vector（2）

分类:热门推荐日期:2024-04-10浏览:1评论:0

博主首页： 有趣的中国人

专栏首页： C++专栏

    本篇文章主要讲解 vector模拟实现的相关内容

    1. STL中vector的模式

    在STL中vector是靠三个迭代器来维护的：

    1. start
    2. finish
    3. end_of_storage

    如下图所示，其中size是现在有多少元素，而capacity是现在的空间有多少:

    因此很容易看出:

    1. size = finsih - start;

    2. capacity = end_of_storage - start;

    所以可以写出vector类中的成员变量：

    namespace d1
{templateclass vector
	{public:
		typedef T* iterator;
		typedef const T* const_iterator;
	private:
		iterator start = nullptr;
		iterator finish = nullptr;
		iterator end_of_storage = nullptr;
	};
}

      2. 插入相关操作的模拟

      2.1 push_back()

      push_back就是尾插操作，既然插入肯定要用到扩容，代码如下：

      size_t size() const
{return finish - start;
}
size_t capacity() const
{return end_of_storage - start;
}
void push_back(const T& val)
{if (end_of_storage == finish)
	{// 注意这里要记录以下原始size的大小，要不然找不到新的finish和end_of_storage的位置
		size_t old_size = size();
		size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
		T* tmp = new T[newcapacity];
		memcpy(tmp, start, old_size * sizeof(T));
		delete[] start;
		start = tmp;
		finish = start + old_size;
		end_of_storage = start + newcapacity;
	}
	*finish = val;
	++finish;
}

      这里尝试插入5个数据测试一下：

      2.2 reserve()

      reserve 相当于就是扩容操作，刚才的尾插已经涉及到，把他放到reserve中即可：

      void reserve(size_t newcapacity)
{if (newcapacity > capacity())
	{size_t old_size = size();
		T* tmp = new T[newcapacity];
		memcpy(tmp, start, old_size * sizeof(T));
		delete[] start;
		start = tmp;
		finish = start + old_size;
		end_of_storage = start + newcapacity;
	}
}

      2.3 operator[]的重载 和 迭代器

      为了更好的访问vector和测试，我们可以先实现operator[]的重载 和 iterator。

      1. operator[]的重载
      T operator[](size_t pos)
{assert(pos >= 0 && pos < size());
	return start[pos];
}
      1. iterator 和 const_iterator
      iterator begin()
{return start;
}
iterator end()
{return finish;
}
const_iterator begin() const
{return start;
}
const_iterator end() const
{return finish;
}
      1. test代码：
      void vector_test1()
{vector v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	for (size_t i = 0; i < v.size(); ++i)
	{cout << v[i] << " ";
	}
	cout << endl;
	vector::iterator it = v.begin();
	while (it != v.end())
	{cout << *it << " ";
		++it;
	}
	cout << endl;
}
      1. 我们可以按照模板函数的方法将打印写成函数：

      • 这里有一点需要特别注意，注意仔细看注释。
        templatevoid print_vector(const vector& v)
{for (size_t i = 0; i < v.size(); ++i)
	{cout << v[i] << " ";
	}
	cout << endl;
	// 注意这里：
	// 编译器会无法分清你写的vector::const_iterator是一个静态成员变量还是一个类型
	// 因为此时并没有被实例化，编译器也不会在此时实例化
	// 为了告诉编译器这里是一个类型，要在前面加上typename
	// 一般嵌套模板都要加上typename
	// vector::const_iterator it = v.begin();
	typename vector::const_iterator it = v.begin();
	while (it != v.end())
	{cout << *it << " ";
		++it;
	}
	cout << endl;
}

        2.4 insert()

        insert 允许你在任意位置插入元素，传入的是迭代器类型，这里需要注意是否需要扩容，如果需要扩容，就要更新pos的位置，模拟实现代码如下：

        void insert(iterator pos, const T& val)
{assert(pos >= begin() && pos <= finish);
	if (finish == end_of_storage)
	{size_t old_pos = pos - start;
		size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
		reserve(newcapacity);
		pos = start + old_pos;
	}
	iterator end = finish - 1;
	while (end >= pos)
	{*(end + 1)= *end;
		--end;
	}
	*pos = val;
	++finish;
}

        测试代码：

        void vector_test1()
{vector v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.insert(v.begin(), 0);
	v.insert(v.end(), 6);
	v.insert(v.begin() + 1, 10);
	print_vector(v);
}

        2.5 resize()

        resize 有三种情况：

        1. 小于size：删除数据
        2. 大于size，小于capacity：插入数据
        3. 大于capacity：扩容+插入数据
        void resize(size_t n, const T& val = T())
{if (n >= size())
	{reserve(n);
		for (size_t i = size(); i < n; ++i)
		{start[i] = val;
			++finish;
		}
	}
	else
	{finish = start + n;
	}
}

        测试代码：

        void vector_test1()
	{vector v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		v.insert(v.begin(), 0);
		v.insert(v.end(), 6);
		v.insert(v.begin() + 1, 10);
		v.insert(v.begin() + 1, 10);
		v.insert(v.begin() + 1, 10);
		v.insert(v.begin() + 1, 10);
		v.resize(20);
		print_vector(v);
	}

          3. 删除相关操作的模拟

          3.1 判空

          当start==finish时，为空：

          bool Empty()
{return start == finish;
}

          3.2 pop_back()

          尾删，直接 --finish 即可。

          void pop_back()
{assert(!Empty());
	--finish;
}

          3.3 erase()

          在任意位置删除，将后面的元素往前挪动即可，最后再--finish。

          void erase(iterator pos)
{assert(!(Empty()));
	assert(pos >= start && pos < finish);
	iterator begin = pos + 1;
	while (begin < finish)
	{*(begin - 1) = *begin;
		++begin;
	}
	--finish;
}

            4. 构造函数相关操作模拟

            4.1 拷贝构造的现代写法

            正常拷贝构造的写法：

            vector(const vector& v)
{T* tmp = new T[v.capacity()];
	memcpy(tmp, v.start, sizeof(T) * v.size());
	start = tmp;
	finish = start + v.size();
	end_of_storage = start + v.capacity();
}

            现代写法：

            1. 先开辟一块大小相同的空间；
            2. 尾插到此块空间即可。
            vector(const vector& v)
{reserve(v.capacity());
	for (auto& e : v)
	{push_back(e);
	}
}

            4.2 赋值重载现代写法

            1. 传值传参，调用拷贝构造，深拷贝一块空间；
            2. 进行交换。
            void swap(vector& v)
{std::swap(start, v.start);
	std::swap(finish, v.finish);
	std::swap(end_of_storage, v.end_of_storage);
}
vector& operator=(vector v)
{swap(v);
	return *this;
}

            4.3 迭代器区间构造

            类模板的成员函数可以是函数模板。

            迭代器区间构造就是支持用一段**其他类型的迭代器区间**来进行初始化vector。

            templatevector(InputIterator first, InputIterator last)
{while (first != last)
	{push_back(*first);
		++first;
	}
}

            测试代码：

            void vector_test4()
{vector v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	print_vector(v1);
	vector v2(v1.begin() + 1, v1.end() - 1);
	print_vector(v2);
	string str("abcd");
	vector v3(str.begin(), str.end());
	print_vector(v3);
}

            4.4 代参的构造函数

            我这里实现的是用n个数来构造vector。

            1. 首先申请一块空间；
            2. 然后对这n个数依次尾插即可。
            vector(size_t n, const T& val = T())
{reserve(n);
	for (size_t i = 0; i < n; ++i)
	{push_back(val);
	}
}

            但是当运行以下的代码时，会报错：

            void vector_test5()
{vector v1(10,1);
	print_vector(v1);
}

            他报错的位置并不是我们上面写的代码，而是跑到了迭代器区间构造那里，因为编译器认为迭代器区间构造更匹配，因为编译器认为这里的10为int类型，不是size_t类型，假如我们给10加上u（无符号整数），或者构造成char类型，就不会报错：

            void vector_test5()
{vector v1(10u,1);
	print_vector(v1);
	vector v2(10, 'a');
	print_vector(v2);
}

            为了解决这个问题，其实直接加个重载函数即可：

            vector(size_t n, const T& val = T())
{reserve(n);
	for (size_t i = 0; i < n; ++i)
	{push_back(val);
	}
}
vector(int n, const T& val = T())
{reserve(n);
	for (size_t i = 0; i < n; ++i)
	{push_back(val);
	}
}

            这样编译器在调用函数的时候会先调用int参数的这个重载函数，因为这个最匹配。

              5. initializer_list

              在C语言中我们构造数组通常是这样的：

              int a[] = { 0 };

              但是在C++中，倘若我们右大括号来定义一个变量，那么它的类型将不是数组，而是initializer_list，我们可以测试一下：

              void vector_test6()
{auto x = { 1,2,3,4,5 };
	cout << typeid(x).name() << endl;
}

              那么initializer_list 究竟是什么呢？

              • initializer_list是C++中的一种容器，用于初始化同一类型的元素列表。它是C++11引入的一个特性，旨在简化初始化容器的过程。

              • 我们知道单参数类型的构造函数支持隐式类型转换，例如： 
                void vector_test6()
{// 构造 + 拷贝构造 -> 优化 直接构造
	string str1 = "11111";
	// 这里加引用引用的是"2222"临时拷贝出来的空间，临时变量具有常性，因此要加const
	const string& str2 = "22222";
	vector v;
	v.push_back(str1);
	v.push_back(str2);
	// 甚至可以用匿名对象进行隐式类型转换
	v.push_back(string("hello"));
	// 也能这样
	v.push_back("world");
	print_vector(v);
}
                • 了解了以上内容，那我们就可以用这个来初始化我们的vector，因为initializer_list会隐式类型转换成vector类型： 
                  void vector_test6()
{/*auto x = { 1,2,3,4,5 };
	cout << typeid(x).name() << endl;*/
	std::vector v = { 1,2,3,4,5,6 };
}
                  • 也可以直接构造： 
                    vector v2({ 10,20,30,40 });

                      6. 有关memcpy的问题

                      我们尝试运行以下这段代码：

                      void vector_test7()
{vector v;
	v.push_back("11111");
	v.push_back("22222");
	v.push_back("33333");
	v.push_back("44444");
	v.push_back("55555");
	v.push_back("66666");
	v.push_back("77777");
	v.push_back("88888");
	v.push_back("99999");
	for (auto& e : v)
	{cout << e << " ";
	}
	cout << endl;
}

                      为什么会发生运行错误呢？我们可以调试一下：

                      • 如果我们尝试传入string类型，在扩容的时候用memcpy来拷贝一个自定义类型，实际上也是把string原来的地址传过去了，相当于虽然vector类型是深拷贝，但是string类型是浅拷贝，下图是存储示意图。

                        拷贝后：

                        • 因此我们要用for循环来取代memcpy就可以完美的解决这个问题： 
                          void reserve(size_t newcapacity)
{if (newcapacity > capacity())
	{size_t old_size = size();
		T* tmp = new T[newcapacity];
		//memcpy(tmp, start, old_size * sizeof(T));
		for (size_t i = 0; i < size(); ++i)
		{// 这里对于string这样的类型进行的是赋值重载，也是深拷贝。
			tmp[i] = start[i];
		}
		delete[] start;
		start = tmp;
		finish = start + old_size;
		end_of_storage = start + newcapacity;
	}
}

                            7. 迭代器失效问题

                            • 迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。
                            • 带有扩容的操作都可能导致迭代器失效，例如push_back()，例如： 
                              void vector_test8()
{vector v1;
	vector::iterator it = v1.begin();
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	v1.push_back(6);
	v1.push_back(7);
	v1.push_back(8);
	print_vector(v1);
	v1.insert(it, 40);
	print_vector(v1);
}
                              • 这里插入八个数据空间已经满了，这时候再插入数据就会扩容，v1.begin()的地址就会变，但是迭代器是在开头定义的，他不会变，所以一般在insert以后，不建议使用迭代器。

                                以下示例也会导致迭代器失效：

                                void vector_test9()
{vector v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(4);
	v1.push_back(5);
	//v1.push_back(4);
	// 删除偶数 -- 迭代器失效以后，不要直接使用，如果要使用按规则重新更新后使用
	//std::vector::iterator it = v1.begin();
	vector::iterator it = v1.begin();
	while (it != v1.end())
	{if (*it % 2 == 0)
		{it = v1.erase(it);
		}
		else
		{++it;
		}
	}
	//print_vector(v1);
	for (auto e : v1)
	{cout << e << " ";
	}
	cout << endl;
}

                相关推荐

                关于我们常见问题广告服务免责声明联系我们
                Powered By Z-BlogPHP 1.7.3 Theme By 优美主题
                Copyright Your WebSite.Some Rights Reserved. 浙ICP备2023018783号