自学内容网 自学内容网
自学内容网 > 正文

STL容器之vector类

🕗 发布于 2024-03-01 16:11 c++  开发语言  

文章目录


img

STL容器之vector类

1、vector的介绍

  1. vector是表示可变大小数组的序列容器。

  2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

  3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。

  4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。

  5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

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

使用STL的三个境界：能用，明理，能扩展。

2、vector的使用

2.1、vector的常见构造

(constructor)函数名称接口说明
vector ()（重点）无参构造
vector (size_type n, const value_type& val = value_type())构造并初始化n个val
vector (InputIterator first, InputIterator last)（重点）使用迭代器进行初始化构造
vector (const vector& x)（重点）拷贝构造
#include <iostream>
#include <vector>
#include <list>

using namespace std;

void test_vector1() {
   vector<int> v;
   v.push_back(1);
   v.push_back(2);
   v.push_back(3);
   v.push_back(4);
   for (int e: v) {
       cout << e << " ";
   }
   cout << endl;
}

void test_vector2() {
   vector<int> v1;
   v1.push_back(1);
   v1.push_back(2);
   v1.push_back(3);
   v1.push_back(4);
   for (int e: v1) {
       cout << e << " ";
   }
   cout << endl;

   //用顺序表v1构造v2
   vector<int> v2(v1);
   for (int e: v2) {
       cout << e << " ";
   }
   cout << endl;

   //用顺序表v1的迭代区间构造v3
   vector<int> v3(v1.begin(), v1.end());
   for (int e: v3) {
       cout << e << " ";
   }
   cout << endl;

   //构造长度为10并且各元素为1的顺序表
   vector<int> v4(10, 1);
   for (int e: v4) {
       cout << e << " ";
   }
   cout << endl;
}

void test_vector3() {
   vector<int> v1;
   v1.push_back(1);
   v1.push_back(2);
   v1.push_back(3);
   v1.push_back(4);

   v1.insert(v1.begin(), 10);
   for (int e: v1) {
       cout << e << " ";
   }
   cout << endl;
   vector<int>::iterator pos = find(v1.begin(), v1.end(), 4);//find是函数模版
   v1.insert(pos, 40);
   for (int e: v1) {
       cout << e << " ";
   }

   cout << endl;
   list<int> lt;
   lt.push_back(5);
   lt.push_back(6);
   lt.push_back(7);
   lt.push_back(8);
   for (int e: lt) {
       cout << e << " ";
   }
   cout << endl;

   vector<int> v3(lt.begin(), lt.end());
   for (int e: v3) {
       cout << e << " ";
   }
   cout << endl;
   

}

//vector使用
int main() {
//    test_vector1();
//    test_vector2();
   test_vector3();
   return 0;
}

2.2、vector的iterator的使用

函数名称接口说明
begin()+end()（重点）获取第一个元素位置的iterator/const_iterator和获取最后一个元素的后一个位置的iterator/const_iterator
rbegin()+rend()获取最后一个元素位置的reverse_iterator/const_reverse_iterator和获取第一个元素的后一个位置的reverse_iterator/const_reverse_iterator
void test_vector5() {
   vector<int> v1;
   v1.push_back(1);
   v1.push_back(2);
   v1.push_back(3);
   v1.push_back(4);

   vector<int>::iterator it1 = v1.begin();
   while (it1 != v1.end()) {
       cout << *it1 << " ";
       ++it1;
   }
   cout << endl;

   vector<int>::const_iterator it2 = v1.begin();
   while (it2 != v1.end()) {
       cout << *it2 << " ";
       ++it2;
   }
   cout << endl;

}

void test_vector6() {
   vector<int> v1;
   v1.push_back(1);
   v1.push_back(2);
   v1.push_back(3);
   v1.push_back(4);

   vector<int>::reverse_iterator it1 = v1.rbegin();
   while (it1 != v1.rend()) {
       cout << *it1 << " ";
       ++it1;
   }
   cout << endl;
}

int main() {
 
   test_vector5();
   test_vector6();
 
   return 0;
}

2.3、vector空间增长问题

函数名称接口说明
size获取数据个数
resize（重点）改变vector的size
capacity获取数据的容量大小
empty判断vector是否为空
reserve（重点）改变vector的capacity
void test_vector7() {
    vector<int> v1;
    cout << v1.size() << " " << v1.capacity() << endl;

    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);

    cout << v1.size() << " " << v1.capacity() << endl;
    v1.resize(10);
    cout << v1.size() << " " << v1.capacity() << endl;
    v1.reserve(11);
    cout << v1.size() << " " << v1.capacity() << endl;
    v1.resize(5);
    cout << v1.size() << " " << v1.capacity() << endl;

    cout << v1.empty() << endl;
    v1.resize(0);
    cout << v1.empty() << endl;

}

int main() {
  
    test_vector7();
  
    return 0;
}
  • capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，CLion和g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
  • reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
  • resize在开空间的同时还会进行初始化，影响size。
// 测试vector的默认扩容机制 -- 这里CLion是2倍扩容，VS是1.5倍扩容
void TestVectorExpand() {
    size_t sz;
    vector<int> v;
    sz = v.capacity();
    cout << "making v grow:\n";
    for (int i = 0; i < 100; ++i) {
        v.push_back(i);
        if (sz != v.capacity()) {
            sz = v.capacity();
            cout << "capacity changed: " << sz << '\n';
        }
    }
}

/*
vs：运行结果：vs下使用的STL基本是按照1.5倍方式扩容
  making foo grow:
  capacity changed: 1
  capacity changed: 2
  capacity changed: 3
  capacity changed: 4
  capacity changed: 6
  capacity changed: 9
  capacity changed: 13
  capacity changed: 19
  capacity changed: 28
  capacity changed: 42
  capacity changed: 63
  capacity changed: 94
  capacity changed: 141
  
  g++运行结果：linux下使用的STL基本是按照2倍方式扩容
  making foo grow:
  capacity changed: 1
  capacity changed: 2
  capacity changed: 4
  capacity changed: 8
  capacity changed: 16
  capacity changed: 32
  capacity changed: 64
  capacity changed: 128
*/

// 如果已经确定vector中要存储元素大概个数，可以提前将空间设置足够
// 就可以避免边插入边扩容导致效率低下的问题了
void TestVectorExpand() {
    size_t sz;
    vector<int> v;
    sz = v.capacity();
    v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容
    cout << "making v grow:\n";
    for (int i = 0; i < 100; ++i) {
        v.push_back(i);
        if (sz != v.capacity()) {
            sz = v.capacity();
            cout << "capacity changed: " << sz << '\n';
        }
    }
}

2.4、vector的增删查改

函数名称接口说明
push_back（重点）尾插
pop_back（重点）尾删
insert在position之前插入val
erase删除position位置的数据
swap交换两个vector的数据
operator[]（重点）返回position位置的数据
find查找迭代区间在first到last之间的val，注意，这是函数模版
void test_vector8() {
   vector<int> v1;
   v1.push_back(1);
   v1.push_back(2);
   v1.push_back(3);
   v1.push_back(4);

   for (int e: v1) {
       cout << e << " ";
   }
   cout << endl;
   v1.pop_back();
   for (int e: v1) {
       cout << e << " ";
   }
   cout << endl;

   cout << v1[0] << endl;
   v1.insert(v1.begin(), 10);
   for (int e: v1) {
       cout << e << " ";
   }
   cout << endl;

   vector<int>::iterator it = find(v1.begin(), v1.end(), 3);
   v1.erase(it);
   for (int e: v1) {
       cout << e << " ";
   }
   cout << endl;

   cout << "-----------------------" << endl;
   vector<int> v2;
   v2.push_back(10);
   v2.push_back(20);
   v2.push_back(30);
   v2.push_back(40);
   v2.push_back(50);
   v2.push_back(60);
   for (int e: v2) {
       cout << e << " ";
   }
   cout << endl;
   cout << "-----------------------" << endl;
   
   swap(v1, v2);
   for (int e: v1) {
       cout << e << " ";
   }
   cout << endl;
   for (int e: v2) {
       cout << e << " ";
   }
   cout << endl;

}

int main() {

test_vector8();

return 0;
}

2.5、vector迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装（如list，后面会讲）。

比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。解决办法是不使用insert和erase等后的原迭代器，或者使用insert和erase等后返回的迭代器。

  • 对于vector可能会导致其迭代器失效的操作有：

    1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。

      #include <iostream>

using namespace std;

#include <vector>

int main() {
    vector<int> v{1, 2, 3, 4, 5, 6};

    auto it = v.begin();

    // 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容
     v.resize(100, 8);

    // reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变
    // v.reserve(100);

    // 插入元素期间，可能会引起扩容，而导致原空间被释放
    // v.insert(v.begin(), 0);
    // v.push_back(8);

    // 给vector重新赋值，可能会引起底层容量改变
//    v.assign(100, 8);

    /*
    出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，
   而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的
   空间，而引起代码运行时崩溃。
    解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新
   赋值即可。
    */
    
    it = v.begin();//解决办法
    while (it != v.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    return 0;
}

    2. 指定位置元素的删除操作(erase)

      #include <iostream>

using namespace std;

#include <vector>

int main() {
    int a[] = {1, 2, 3, 4};
    vector<int> v(a, a + sizeof(a) / sizeof(int));
    // 使用find查找3所在位置的iterator
    vector<int>::iterator pos = find(v.begin(), v.end(), 3);
    // 删除pos位置的数据，导致pos迭代器失效。
    v.erase(pos);
    cout << *pos << endl; // 此处会导致非法访问，解决办法：不再访问pos

    v.push_back(5);
    v.push_back(6);
    v.push_back(6);
    v.push_back(5);
    v.push_back(8);

    for (auto e: v) {
        cout << e << " ";
    }
    cout << endl;

    //删除v里所有偶数
    vector<int>::iterator it = v.begin();
    while (it != v.end()) {
        if (*it % 2 == 0) {
//            v.erase(it);//这里最好不再用it
            it = v.erase(it);//解决办法
        } else {
            ++it;
        }
    }
    for (auto e: v) {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

    3. 与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效。

      #include <string>
          
using namespace std;
          
int main() {
          
    string s("hello");
    string::iterator sit = s.begin();
          
    // 这里resize过后，会扩容，之前等sit的位置会改变
    s.resize(100, 'w');
          
    // 解决办法，给sit重新赋值
    sit = s.begin();
    while (sit != s.end()) {
        cout << *sit << " ";
        ++sit;
    }
    cout << endl;
          
    sit = s.begin();
    while (sit != s.end()) {
        sit = s.erase(sit);//这里s.erase(sit)后的sit位置是之前sit的后一个位置
        ++sit;//说明是隔一个元素删除
    }
              
    for (char e: s) {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

3.vector的模拟实现

  1. vector核心框架接口的模拟实现

  • vector.h文件

      //
  // Created by 徐鹏 on 2023/12/10.
  //
    
  #include <cstdio>
  #include <cstring>
  #include <list>
    
  using namespace std;
    
  #ifndef DEMO_01_VECTOR_H
  #define DEMO_01_VECTOR_H
    
  #endif //DEMO_01_VECTOR_H
    
  namespace xp {
      template<typename T>
      class vector {
      public:
          typedef T *iterator;
          typedef const T *const_iterator;
    
          vector() : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}
    
  //        vector(const vector<T> &v) {
  //            _start = new T[v.capacity()];
  //            memcpy(_start, v._start, v.size() * sizeof(T));
  //            _finish = _start + v.size();
  //            _end_of_storage = _start + capacity();
  //        }
    
          //拷贝构造函数
          vector(const vector<T> &v) {
              reserve(v.capacity());
              for (const auto &e: v) {
                  push_back(e);
              }
          }
    
          template<class InputIterator>
          //构造迭代器区间
          vector(InputIterator first, InputIterator last) {
              while (first != last) {
                  push_back(*first);
                  ++first;
              }
          }
    
          vector(size_t n, const T &val = T()) {
              resize(n, val);
          }
    
          //防止和上面迭代器区间搞混
          vector(int n, const T &val = T()) {
              resize(n, val);
          }
    
          //赋值 ,这里vector<T> v在传值的时候就已经有拷贝构造了
          vector<T> &operator=(vector<T> v) {
              swap(v);
              return *this;
          }
    
          T &operator[](size_t n) {
              return *(_start + n);
          }
    
          const T &operator[](size_t n) const {
              return *(_start + n);
          }
    
          ~vector() {
              if (_start) {
                  delete[] _start;
                  _start = _finish = _end_of_storage = nullptr;
              }
          }
    
          void swap(vector<T> v) {
              std::swap(_start, v._start);
              std::swap(_finish, v._finish);
              std::swap(_end_of_storage, v._end_of_storage);
          }
    
          void reserve(size_t n) {
              if (n > capacity()) {
                  //开辟新空间
                  size_t old_size = size();
                  iterator tmp = new T[n];
                  //start不为空，在复制完内容需要释放空间
                  if (_start) {
  //                    //对于自定义类型，在进行delete[] _start 之后（自定义类型里面存在指针开辟空间问题的时候），会把原来的_start里面内容进行析构和空间释放
  //                    memcpy(tmp, _start, old_size * sizeof(T));
    
                      //  解决方案，进行深拷贝
                      for (size_t i = 0; i < old_size; ++i) {
                          tmp[i] = _start[i];
                      }
                      delete[] _start;
                  }
                  _start = tmp;
                  //这里要注意，得用之前的size，不然新size使用内联进来就是_finish = _start + _finish - _start
                  _finish = _start + old_size;
                  _end_of_storage = _start + n;
              }
          }
    
          void resize(size_t n, T val = T()) {
              if (n > capacity()) {
                  size_t fill = _start + n - _finish;
                  reserve(n);
                  //填补之前finish后面fill个数据
                  while (fill != 0) {
                      *_finish = val;
                      _finish++;
                      fill--;
                  }
              }
          }
    
          void push_back(const T &val) {
              if (_finish == _end_of_storage) {
                  size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
                  reserve(newCapacity);
              }
              *_finish = val;
              ++_finish;
          }
    
          void pop_back() {
              --_finish;
          }
    
          void insert(iterator pos, const T &val) {
              assert(pos >= _start);
              assert(pos <= _finish);
    
              if (_finish == _end_of_storage) {
                  size_t len = pos - _start;
                  size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
                  reserve(newCapacity);
                  pos = _start + len;//防止增容量后，pos位置还是之前被释放的空间
              }
              //memmove(pos + 1, pos, sizeof(T) * (_finish - pos)); //浅拷贝，扩容可能存在迭代器失效问题
              iterator end = _finish - 1;
              while (pos <= end) {
                  *(end + 1) = *end;
                  --end;
              }
              *pos = val;
              ++_finish;
          }
    
          iterator begin() {
              return _start;
          }
    
          const_iterator begin() const {
              return _start;
          }
    
          iterator end() {
              return _finish;
          }
    
          const_iterator end() const {
              return _finish;
          }


          size_t size() const {
              return _finish - _start;
          }
    
          size_t capacity() const {
              return _end_of_storage - _start;
          }
    
      private:
          iterator _start = nullptr;
          iterator _finish = nullptr;
          iterator _end_of_storage = nullptr;
      };
        
    void test_vector1() {
        vector<char> v;
        v.reserve(10);
        cout << v.size() << " " << v.capacity() << endl;
//        v.resize(100);
        v.resize(100, 'x');
        cout << v.size() << " " << v.capacity() << endl;
    
    }
    
    void test_vector2() {
        vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);
        for (auto e: v) {
            cout << e << " ";
        }
        cout << endl;
    }
    
    void test_vector3() {
        vector<string> v;
        v.push_back("hh");
        v.insert(v.begin(), "2");
        v.insert(v.begin(), "2");
        v.insert(v.begin(), "2");
        v.insert(v.begin(), "2");
        v.insert(v.begin(), "2");
        v.insert(v.begin(), "2");
        v.insert(v.begin(), "2");
        v.insert(v.begin(), "2");
        for (auto e: v) {
            cout << e << " ";
        }
        cout << endl;
    }
    
    void test_vector4() {
        vector<string> v1;
        v1.push_back("hhh");
        v1.push_back("www");
        for (auto e: v1) {
            cout << e << " ";
        }
        cout << endl;
    
        vector<string> v2;
        v2.push_back("lllll");
        v2.push_back("nnnnn");
        for (auto e: v2) {
            cout << e << " ";
        }
        cout << endl;
        cout << "----------------------" << endl;
        v1 = v2;
        for (auto e: v1) {
            cout << e << " ";
        }
        cout << endl;
        for (auto e: v2) {
            cout << e << " ";
        }
        cout << endl;
    
    }
    
    void test_vector5() {
        vector<string> v;
        v.push_back("w");
        v.push_back("s");
        v.push_back("x");
        v.push_back("p");
        cout << v[1] << endl;
    }
    
    void test_vector6() {
        vector<string> v;
        v.push_back("w");
        v.push_back("s");
        v.push_back("x");
        v.push_back("p");
        v.push_back("p");
        v.push_back("p");
        v.push_back("p");
        v.push_back("p");
        v.push_back("psdf");
        v.push_back("pdsf");
        v.push_back("pfd");
        v.push_back("pdsf");
        v.insert(v.begin(), "sdas");
        for (auto e: v) {
            cout << e << " ";
        }
        cout << endl;
    }
    
    void test_vector7() {
        vector<string> v;
        v.push_back("w");
        v.push_back("s");
        v.push_back("x");
        v.push_back("p");
        v.push_back("p");
        v.push_back("p");
        vector<string> v2(v.begin(), v.end());
        for (auto e: v2) {
            cout << e << " ";
        }
        cout << endl;
    
        int a[] = {1111, 222, 222, 3};
        vector<int> v3(a, a + 4);
        for (auto e: v3) {
            cout << e << " ";
        }
        cout << endl;
    
        list<string> lt;
        lt.push_back("hjakds");
        lt.push_back("wq");
        lt.push_back("qw");
        lt.push_back("w");
    
        vector<string> v4(lt.begin(), lt.end());
        for (auto e: v4) {
            cout << e << " ";
        }
        cout << endl;
    
        vector<int> v5(5, 5);
        for (auto e: v5) {
            cout << e << " ";
        }
        cout << endl;
    }
    
  }

  • main.h文件

    #include <iostream>
#include "vector.h"
    
//vector 模拟实现
int main() {
//    xp::test_vector1();
//    xp::test_vector2();
//    xp::test_vector3();
//    xp::test_vector4();
//    xp::test_vector5();
//    xp::test_vector6();
    xp::test_vector7();
    return 0;
}
  1. 使用memcpy拷贝问题

在reserve接口中存在扩容情况，对于内置类型，使用memcpy函数对数据进行拷贝不存在什么问题，但是对于自定义类型，如string类，在使用memcpy进行拷贝的时候，虽然将原数据拷贝到了新空间上，但是string类的成员变量存在指针_str，如果直接将该数据直接拷贝过来，那么新空间里的_str和旧空间的_str会指向同一块空间，在旧空间释放后，新空间的_str指针就变成了野指针。其实就是memcpy的浅拷贝问题，解决办法就是使用深拷贝，即直接把旧空间的数据采用赋值的方式（string赋值是深拷贝）放到新空间中。

  • 使用memcpy的代码

    void reserve(size_t n) {
            if (n > capacity()) {
                //开辟新空间
                size_t old_size = size();
                iterator tmp = new T[n];
                //start不为空，在复制完内容需要释放空间
                if (_start) {
                memcpy(tmp, _start, old_size * sizeof(T));
                    delete[] _start;
                }
                _start = tmp;
                //这里要注意，得用之前的size，不然新size使用内联进来就是_finish = _start + _finish - _start
                _finish = _start + old_size;
                _end_of_storage = _start + n;
            }
}

    这里就导致在释放完_start后，_tmp中的_str变成野指针。

  • 解决办法：使用string的赋值进行深拷贝

    void reserve(size_t n) {
            if (n > capacity()) {
                //开辟新空间
                size_t old_size = size();
                iterator tmp = new T[n];
                //start不为空，在复制完内容需要释放空间
                if (_start) {
//                    //对于自定义类型，在进行delete[] _start 之后（自定义类型里面存在指针开辟空间问题的时候），会把原来的_start里面内容进行析构和空间释放
//                    memcpy(tmp, _start, old_size * sizeof(T));
    
                    //  解决方案，进行深拷贝
                    for (size_t i = 0; i < old_size; ++i) {
                        tmp[i] = _start[i];
                    }
                    delete[] _start;
                }
                _start = tmp;
                //这里要注意，得用之前的size，不然新size使用内联进来就是_finish = _start + _finish - _start
                _finish = _start + old_size;
                _end_of_storage = _start + n;
            }
}

    结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

OKOK，C++ STL容器之vector类就到这里。如果你对Linux和C++也感兴趣的话，可以看看我的主页哦。下面是我的github主页，里面记录了我的学习代码和leetcode的一些题的题解，有兴趣的可以看看。

Xpccccc的github主页


原文地址：https://blog.csdn.net/qq_44121078/article/details/136391886

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024