C++ STL容器学习

11-20-2020 04-14-2021 7 minutes read (About 1001 words)

$Date:\ Nov\ 20\ 2020$
Tag: Code

C++ STL容器学习笔记

P.S.不过与其说是学习，倒不如说是手动换原吧!~~因为早就学过应用了~~

[$Vector$]：

优秀的动态数组，支持动态修改大小。

实现原理:

开辟一块连续的内存，不断加入元素。
当内存不足时，申请更大的一块连续内存，复制旧内存区域的元素至新开辟的内存区域，释放旧内存
通常这个扩大的内存大小为原本的1.5倍，保证了不会平凡发生内存二次分配，保证运行效率。

具体维护方法：
记录 _$first$ 指针指向首地址。
记录 $\ \space$ _$last$ 指针指向最后一个元素的下一位。
记录 $\ \space$ _$end$ 指针指向当前申请内存的尾地址的下一位。

故$size() = $ _$last - $ _$first$ ， $capacity() = $ _$end - $ _$first$。
P.S. $Hexo$ 渲染$LaTeX$下划线有$bug$,我傻了
核心函数：

1 2	bool reserve(size_t _count) {} // 二次分配内存，大小为_count

More about reserve

bool reserve(size_t _count) { // 申请 _count 长度的存储空间
  if (capacity() < _count) {
    _Tp *_ptr = _Buy(_count);
    if (_ptr == NULL) return (true);
    if (_Allocate(_ptr, _count))
      return (true);
    if (_first != 0)
      _Tidy(_first);
    _end = _ptr + _count;
    _last = _ptr + size();
    _first = _ptr;
  }
  return (false);
}

$reserve$ 实现:

_$count \le capacity()$ 内存足够，不做任何事。
_$count \lt capacity()$ 触发二次分配:
1. 申请 _$count$ 大小的内存, 记录首指针为 $ ^*$ _$ptr$。
2. 复制 _$first \to $ _$last$ 内容至 _$ptr$。
3. 清理并释放 _$first \to$ _$end$ 的内存区域。
4. 将 _$first$, _$last$, _$end$ 指向新位置。

Code：


#include <bits/stdc++.h>
/*
  Nov. 20th 2020
  File   my_vector.h
  Author wangyx1107
  下一步用迭代器代替 _Tp*
*/
#ifndef _MY_VECTOR_H
#define _MY_VECTOR_H 1
template<class _Tp>
class vector {
  static std::string runtime_error;
 protected:
  _Tp *_first = 0; // 首地址
  _Tp *_last = 0; // 当前存在元素最后一个地址
  _Tp *_end = 0; // 最后一个可用内存地址
 private:
  static bool _Fill(_Tp *_dest, _Tp *_begin_src, _Tp *_end_src) { // 复制元素 scr 到 dest
    for (_Tp *it = _begin_src; it < _end_src; ++it, ++_dest)
      *(_dest) = *(it);
    return (false);
  }
  static bool _Fill(_Tp *_begin, _Tp *_end, _Tp _init) { // 以 _init 填充 _begin to _end
    for (_Tp *it = _begin; it < _end; ++it)
      *(it) = _init;
    return (false);
  }
  _Tp* _Buy(size_t _count) { // 申请内存
    if (!_count) return (NULL);
    else {
      _Tp *_ptr = new _Tp[_count];
      return _ptr;
    }
  }
  bool _Allocate (_Tp* _ptr, size_t _count) { // 转移元素
    if (size() > _count) return (true);
    if (_Fill(_ptr, _first, _last))
      return (true);
    return (false);
  }
  bool _Tidy(_Tp *_first) { delete [] _first; return (false); } // 清理内存
  bool _Destory(_Tp *_begin, _Tp *_end) { // 清空内容
    for (_Tp *it = _begin; it < _end; ++it)
      (*it).~_Tp();
    return (false);
  }
 public:
  class iterator { // 迭代器
    _Tp *it;
   public:
    iterator(_Tp* _init_it = 0) { it = _init_it; }
    _Tp& operator* () { if (!it) throw runtime_error; return *it; }
    iterator& operator++ () { ++it; return *(this); }
    iterator operator+ (const size_t _plus) { return it + _plus; }
    iterator operator- (const size_t _dec) { return it - _dec; }
    bool operator== (const iterator _other) { return it == _other.it; }
    bool operator!= (const iterator _other) { return it != _other.it; }
    bool operator< (const iterator _other) { return it < _other.it; }
    bool operator> (const iterator _other) { return it > _other.it; }
    bool operator<= (const iterator _other) { return *(this) > _other || *(this) == _other; }
    bool operator>= (const iterator _other) { return *(this) < _other || *(this) == _other; }
  };
  bool reserve(size_t _count) { // 申请 _count 长度的存储空间
    if (capacity() < _count) {
      _Tp *_ptr = _Buy(_count);
      if (_ptr == NULL) return (true);
      if (_Allocate(_ptr, _count))
        return (true);
      if (_first != 0)
        _Tidy(_first);
      _end = _ptr + _count;
      _last = _ptr + size();
      _first = _ptr;
    }
    return (false);
  }
  bool resize(size_t _count, _Tp _init = _Tp()) { // 改变以存储序列打小，若元素不足则填充 _init
    if (_count == size()) return (false);
    if (_count < size()) {
      _Destory(_first + _count, _last);
      _last = _first + _count;
      return (false);
    } else {
      if (_count > capacity() && reserve(_count)) 
        return (true); // 若capacity不足， 重新申请
      _Fill(_last, _first + _count, _init);
      _last = _first + _count;
      return (false);
    }
  }
  bool push_back(const _Tp val) {
    if (size() < capacity()) { // 内存足够
      *_last = val;
      _last++;
      return (false);
    }
    else {
      if (!capacity() && reserve(2)) return true; // 第一次申请;
      else 
        if (reserve(capacity() + capacity() / 2)) // 扩大50%
          return (true);
      *_last = val;
      _last++;
      return (false);
    }
  }
  bool pop_back() {
    if (!size()) {
      throw runtime_error;
      return true;
    } else {
      _Destory(_last - 1, _last);
      _last--;
      return false;
    }
  }
  size_t capacity() { return _end - _first; }
  size_t size() { return _last - _first; }
  iterator begin() { return iterator(_first); }
  iterator end() { return iterator(_last); }
  _Tp& operator[] (const int& p) {
    if (p >= size()) throw runtime_error;
    return *(_first + p);
  }
  void clear() {
    _Destory(_first, _last, _end);
    if (_first) _Tidy(_first); 
    _first = 0, _last = 0, _end = 0;
  }
  vector(size_t _capacity = 0) { reserve(_capacity); }
  ~vector() { if (_first) _Tidy(_first); }
};
template<class _Tp>
std::string vector<_Tp>::runtime_error = "runtime_error";
#endif

暂时没有好的代码块折叠方法，先这样。。。

先写到这，下次更新随缘

$Nov.\ 20th\ 18:31$

Code

C++ STL容器学习