C++ STL - vector/list解说及迭代器失效

vector 利用

vector 是一个动态数组.
构造/拷贝构造/赋值重载函数

1. int main()
2. {
3.   // 是一个模板, 在实例化的时候, 需要指明类型
4.   std::vector<int> first; // 一个空的数组
5.   std::vector<int> second (4,100); // 设置初始空间大小为 4 个int, 全部初始化为 100
6.   std::vector<int> third (second.begin(),second.end()); // 通过迭代器构造
7.   std::vector<int> fourth (third); // 直接复制 third, 拷贝构造
8.   std::vector<int> fifth;
9.   fifth = fourth;  // 复制重载
10.   return 0;
11. }

复制代码

空间函数

1. size/capacity

   size: 返回 vector 当前存储的元素数量
capacity: 返回 vector 最大存储元素数量

1. size_type size() const noexcept;
2. size_type capacity() const noexcept;
4. int main()
5. {
6.     vector<int> v1(10, 1);
7.     cout << v1.size() << " " << v1.capacity() << endl;
8.     return 0;
9. }

复制代码

2. resize/reserve

   resize: 修改 vector 对象的 size
  reserve: 修改 vector 的容量 capacity

1. void resize (size_type n);
2. void resize (size_type n, const value_type& val);
4. void reserve (size_type n);
6. int main()
7. {
8.     vector<int> v1;
9.     v1.resize(10, 0);
10.     // n < size 则数据丢失, n > capacity 则发生扩容, 用 val 填充扩容的空间
11.     v1.reserve(20);
12.     // 如果当前容量小于 n，vector 会重新分配内存以增加容量。
13.     // 如果当前容量已经大于或等于 n，则 reserve() 不会改变容量。
14.     return 0;
15. }

复制代码

 reserve修改的只是capacity, 而不是size, 这是由区别的.

1. int main()
2. {
3.     vector<int> v1;
4.     v1.reserve(10);
5.     v1[1] = 10; // 这是错误的, reserve(10) 只是开辟了 10 个空间, 这 10 个空间还没有给我们使用
6.     v1.resize(10);
7.     v1[1] = 10; // 设置size = 10, 让v1分配了 10 个空间使用权给我们
8. }

复制代码

3. empty

   empty: 检查 vector 是否为空, 为空返回 true, 否者返回 false

1. bool empty() const noexcept;
3. int main()
4. {
5.     vector<int> v1;
6.     if(v1.empty)
7.     {
8.         cout << "数组为空" << endl;
9.     }
10.     else
11.     {
12.         cout << "数组不为空" << endl;
13.     }
14. }

复制代码

访问 

1. operator[] / at

这两个函数都是用于访问 vector 中指定索引的元素

1. int main()
2. {
3.     vector<int> v1(10);
4.     for(int i = 0; i < 10; i++)
5.     {
6.         v1[i] = i;
7.     }
8.     v1.at(5) = 50;
9.     cout << v1[2] << endl;
10.     cour << v1.at(5) << endl;
11. }

复制代码

  区别: operator[] 不会进行边界检查, 如果访问位置超出范围, 行为是未定义的
           at 则会进行边界检查, 访问位置超出范围, 则抛出非常
  2. front / back

   front: 返回数组头部的元素
  back: 返回数组末端的谁人元素

1. int main()
2. {
3.     vector<int> v1(10);
4.     for(int i = 0; i < 10; i++)
5.     {
6.         v1[i] = i;
7.     }
8.     cout << v1.front() << endl;
9.     cout << v1.back() << endl;
10.     return 0;
11. }

复制代码

3. data

   data: 返回一个指向 vector 内部数组的指针, 允许直接访问底层数组

1. int main()
2. {
3.     vector<int> v1(10);
4.     for(int i = 0; i < 10; i++)
5.     {
6.         v1[i] = i;
7.     }
8.     int* arr = v1.data();
9.     cour << arr[5] << endl;
10.     return 0;
11. }

复制代码

修改

1. push_back / pop_back

   push_back: 向 vector 的末端插入一个元素
  pop_back: 删除 vector 末端的一个元素

1. int main()
2. {
3.     vector<int> v1;
4.     v1.push_back(2);
5.     cout << v1
6.     return 0;
7. }

复制代码

2. insert / erase

   insert: 向指定的位置 (位置是一个迭代器) 后面插入一个元素, 并返回指向插入元素的迭代器
  erase: 删除指定位置的元素, 返回删除位置的后一个元素的迭代器

1. #include <iostream>
2. #include <vector>
4. int main ()
5. {
6.     std::vector<int> myvector (3,100);
7.     std::vector<int>::iterator it;
9.     it = myvector.begin();
10.     it = myvector.insert ( it , 200 );
11.     cout << *it << endl;
12.         it = myvector.erase(it);
13.         std::cout << *it << std::endl;
14.     return 0;
15. }

复制代码

3. swap / clear

   swap: 互换两个 vector 的值
  clear: 清空 vector 中的元素

1. int main()
2. {
3.     vector<int> v1(3, 200);
4.     vector<int> v2(5, 100);
5.     v1.swap(v2);
6.     cout << v1[1] << endl;
7.     v1.clear();
8.     if(v1.empty())
9.     {
10.         cout << "v1为空" << endl;
11.     }
12.     return 0;
13. }

复制代码

list 利用

list 底层是一个双向链表, 链表擅长的就是插入删除操纵.
构造list

1. int main()
2. {
3.     std::list<int> first;                                // empty list of ints
4.     std::list<int> second (4,100);                       // four ints with value 100
5.     std::list<int> third (second.begin(),second.end());  // iterating through second
6.     std::list<int> fourth (third);
7.     return 0;
8. }

复制代码

容量

empty / size

和上面 vector 中的函数作用相同
STL 容器中的函数名称非常相似, 功能也相似, 认识完 vector 之后, list 利用也很简单
   empty: 判断 list 是否为空
  size: 返回链表的长度.

1. int main()
2. {
3.     list<int> l1(3, 10);
4.     cout << "l1 的长度为: " << l1.size() << endl;
5.     if(l1.empty())
6.     {
7.         cout << "l1 为空" << endl;
8.     }
9.     return 0;
10. }

复制代码

修改

list 提供了非常多的插入删除操纵, 由于相比于 vector, 双向链表插入删除效率更高
push_back / push_front / pop_back / pop_front

   push_back: 在 list 尾部插入一个元素
  push_front: 在 list 头部插入一个元素
  pop_back: 在 list 尾部删除一个元素
  pop_front: 在 list 头部删除一个元素

1. int main()
2. {
3.     list<int> l1(2, 10);
4.     l1.push_back(20);
5.     l1.push_frong(5);
6.     // 在 string 中说过, 迭代器的使用方法和指针差不多
7.     std::list<int>::iterator it = l1.begin(); // 获取 l1 首元素的迭代器
8.     while(it != l2.end())
9.     {
10.         cout << *it << " ";
11.     }
12.     l1.pop_back();
13.     l1.pop_front();
14.     while(it != l2.end())
15.     {
16.         cout << *it << " ";
17.     }
18.     return 0;
19. }

复制代码

insert / erase

   insert: 向指定的位置 (位置是一个迭代器) 的前面插入一个元素, 并返回指向插入元素的迭代器
  erase: 删除指定位置的元素, 返回删除位置的后一个元素的迭代器

1. int main ()
2. {
3.     std::list<int> mylist;
4.     std::list<int>::iterator it;
6.     // set some initial values:
7.     for (int i=1; i<=5; ++i) mylist.push_back(i); // 1 2 3 4 5
9.     it = mylist.begin();
10.     ++it;       // it points now to number 2           ^
12.     mylist.insert (it,10);                        // 1 10 2 3 4 5
14.     // "it" still points to number 2                      ^
15.     mylist.insert (it,2,20);                      // 1 10 20 20 2 3 4 5
18.     mylist.erase(it);
20.     it = mylist.begin();
21.     while(it != mylist.end())
22.     {
23.         cout << *it << " ";
24.     }
25. }

复制代码

迭代器失效题目

   迭代器失效: 指的是由于容器（如std::vector、std::list等）的某些操纵导致之前获取的迭代器不再指向容器中的有效元素，或者不再指向任何元素，从而不能被安全利用的征象。
  可以明白为迭代器就是指针, 那么指针什么时间会失效: 所指向的空间是错误的, 那么哪些操纵会导致指针指向的空间发生变革.
vector 迭代器失效情况

在 vector 中, 有以下情况会导致迭代器失效

• 插入操纵：当利用 push_back 或 insert 插入元素时，如果 vector 的容量不敷以容纳新元素，它大概会重新分配内存，这会导致全部迭代器失效。即使不重新分配内存，insert 操纵也会使插入点之后的迭代器失效。
  
• 删除操纵：利用 erase 或 pop_back 删除元素时，指向被删除元素的迭代器会失效，同时，指向被删除元素之后的全部迭代器也会失效。
  
• 容量调解：调用 resize 或 reserve 调解容量时，如果新容量大于当前容量，大概会导致重新分配内存，从而使全部迭代器失效
  

 再看这段代码

1. int main()
2. {
3.     vector<int> v1 = {2, 3, 4, 4, 5};
4.     std::vector<int>::iterator it = v1.begin();
5.     while(it != v1.end())
6.     {
7.         if(*it % 2 == 0)
8.         {
9.             v1.erase(it);
10.         }
11.         ++it;
12.     }
13.    
14.     return 0;
15. }

复制代码

看似每次检查完当前元素之后, it 向后走一步, 检查下一个.
实际上, 由于进行了删除操纵, 数据进行了挪动,
导致后面的元素顺序发生变革, it 所指向的内容就酿成了未定义行为.
解决方法

1. int main()
2. {
3.     vector<int> v1 = {2, 3, 4, 4, 5};
4.     std::vector<int>::iterator it = v1.begin();
5.     while(it != v1.end())
6.     {
7.         if(*it % 2 == 0)
8.         {
9.             it = v1.erase(it);
10.         }
11.     }
12.    
13.     return 0;
14. }

复制代码

上面介绍 erase 和 insert 的时间说了: 这两个函数会返回一个迭代器.
此时返回的迭代器是有效的. 我们利用返回的迭代器代替已经失效的迭代器.
list 迭代器失效

list 迭代器失效: 
删除操纵：利用 erase 删除元素时，只有指向被删除元素的迭代器会失效。其他迭代器，包括指向被删除元素之前和之后的元素的迭代器，仍然有效。

1. int main()
2. {
3.     std::list<int> lst = {1, 2, 3, 4, 5};
4.     std::list<int>::iterator it = lst.begin(); // it 指向第一个元素
5.     lst.erase(it); // 仅 it 失效，lst.begin() 之后的迭代器仍然有效
6.     ++it; // 未定义行为，it 已经失效
7.     // it = lst.erase(it);  应该将 it 进行更新
8. }

复制代码

所以当指向了大概导致迭代器失效的操纵后, 就不要再利用谁人旧的迭代器了.
需要更新当前的迭代器.



免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。