重写

quene

这里主要重写new delete操作, 创建对象池

#include<iostream>



/*
这里一个有头节点链表的que
即表示_first是头节点它的下一个才是第一个元素
_rear是指向最后一个进队节点的指针

下面我需要创建一个对象池 已减少new delete的操作
*/
template<typename T>
class Quene{

public:
    Quene(){
        _front = _rear = new QueneNode();
    }
    ~Quene(){
        auto *cur = _front;
        while(cur!=nullptr){
            _front = _front->_next;
            delete cur;
            cur = _front;
        }
    }

    void push(const T &val){
        // auto *temp = new QueneNode(val);
        // _rear->_next = temp;
        // _rear = temp;

        // new 返回的是指针
        _rear->_next = new QueneNode(val);
        _rear = _rear->_next;
    }
    void pop(){
        if(empty())
            throw "quene empty";
        auto *first = _front->_next;
        _front->_next = first->_next;
        if (_front->_next == nullptr){
            _rear = _front;
        }
        delete first;
    }

    bool empty() const{
        return _front == _rear;
    }
    T front() const{
        if (empty())
            throw "quene empty";
        return _front->_next->_data;
    }
private:
    struct QueneNode
    {
        QueneNode(T data = T(), QueneNode *next=nullptr) :_data(data),_next(next){}
        ~QueneNode(){}
        // 下面这样写就会死循环了
        // 在析构函数内部，并不会自动调用operator delete。
        // 析构函数只负责销毁对象管理的资源，而不会销毁对象本身的内存。对象本身的内存是由operator delete来释放的。
        // ~QueneNode(){
        //     std::cout << "~QueneNode" << std::endl;
        //     delete this;
        // }
        // 这里没有处理内存泄漏问题，后面可以加上智能指针实现
        void *operator new(size_t size){
            // 在这里我需要看看我的对象池是否为空
            if (_node_pool == nullptr){
                // 为空就分配内存
                std::cout << "::operator new" << std::endl;
                _node_pool = (QueneNode*)::operator new(POOL_SIZE*sizeof(QueneNode));
                // 空间创建完成之后需要初始化链表，即要把这些空间给链起来
                auto *p = _node_pool;
                // -1是因为最后位置是nullptr
                while(p < _node_pool+POOL_SIZE-1){
                    p->_next = p+1;
                    p = p+1;
                }
                p->_next = nullptr;
            }
            // 不为空就从对象池中分配内存
            // 分配的方式是拿一个结点出来
            QueneNode *node = _node_pool;
            _node_pool = _node_pool->_next;
            return node;
        }

        // 重写delete
        void operator delete(void* ptr){
            // delete 就是把对象还给对象池
            QueneNode *p = (QueneNode*)ptr;

            // 这里调用析构是为了析构T，如果T里面有指针就会发生内存泄漏
            p->~QueneNode();
            p->_next = _node_pool;
            _node_pool = p;
        }
        T _data;
        QueneNode *_next;
        static QueneNode *_node_pool;
        static const int POOL_SIZE = 1e5;
    };

    QueneNode *_front; // 头节点 （头出尾进）
    QueneNode *_rear; // 尾节点
};

template<typename T>
typename Quene<T>::QueneNode* Quene<T>::QueneNode::_node_pool = nullptr;


int main(){
    Quene<int> que;
    for (int i=1;i<100;i++){
        que.push(i);
        // std::cout << que.front() << std::endl;
        que.pop();
    }
    // std::cout << que.front() << std::endl;

}

stack

这里主要把Stack模板化

#include<iostream>

template<typename T>
class Stack{
public:
    Stack(size_t size):_size(size),_top(-1){
        _data = new T[size];
    }

    ~Stack(){
        delete[] _data;
    }

    Stack(const Stack& other)
        :_top(other._top)
        , _size(other._size)
    {
        _data = new T[_size];
        for (size_t i = 0; i <= _top; ++i){
            _data[i] = other._data[i];
        }
    }
    Stack& operator=(const Stack& other);

    void push(const T& item){
        if (_top + 1 >= _size){
            this->expand();
        }
        _data[++_top] = item;
    }

    void pop(){
        if (_top < 0){
            throw "Stack underflow";
        }
        --_top;
    }

    T top() const{
        if (_top < 0){
            throw "Stack is empty";
        }
        return _data[_top];
    }

    bool isEmpty() const{
        return _top == -1;
    }
    bool isFull() const{
        return _top + 1 == _size;
    }
private:
    T *_data;
    int _top;
    int _size;

    void expand(){
        std::cout << "Expanding stack from size " << _size << " to size " << _size * 2 << std::endl;
        T *new_data = new T[_size * 2];
        for (size_t i = 0; i < _size * 2; ++i){
            new_data[i] = _data[i];
        }
        delete[] _data;
        _data = new_data;
        _size *= 2;
    }
};

template<typename T>
Stack<T>& Stack<T>::operator=(const Stack& other)
    {
            if (this != &other){
                _top = other._top;
                _size = other._size;
                delete[] _data;
                _data = new T[_size];
                for (size_t i = 0; i <= _top; ++i){
                    _data[i] = other._data[i];
                }
            }
            return *this;
    }  



int main() {
    Stack<int> s(2);
    s.push(1);
    s.push(2);
    s.push(3); // Trigger expansion
    std::cout << s.top() << std::endl; // Should print 3
    s.pop();
    std::cout << s.top() << std::endl; // Should print 2
    return 0;
}   

vector

Vector很重要，里面有空间配置器和迭代器的实现，比较麻烦
这里还添加了迭代器的失效处理，STL的vector是没有失效处理的

#define _CRTDBG_MAP_ALLOC
#include <cstdlib>
#include <crtdbg.h>


#include<iostream>
#include<vector>


// 新的vector的实现，采用三个指针，已经allocator，符合C++17标准。
template<typename T>
struct Allocator{
public:
    T* allocate(size_t n){
        return static_cast<T*>(::operator new(n * sizeof(T)));
    }

    void deallocate(T* p){
        ::operator delete(p);
    }

    void construct(T* p, const T& value){
        // 在已分配的内存上构造对象
        // 调用T的拷贝构造函数
        new (p) T(value); 
    }

    void destroy(T* p){
        p->~T();
    }
};


template<typename T, typename Alloc = Allocator<T>>
class Vector{
public:
    // temllate Allocator 的作用在这里得到了体现，从而我们可以自定义内存分配策略
    Vector(const size_t initial_capacity=10, const Alloc& alloc = Alloc());
    Vector(const Vector& other);
    Vector& operator=(const Vector& other);
    ~Vector();
    void push_back(const T& item);
    void pop_back();
    inline size_t size() const{ return static_cast<size_t>(_last - _first);}
    T& operator[](size_t index) const;
    
    /****************************这里需要大大的修改**************************/
    /*
    1. 首先加入当前容器对象，判断两个迭代器是否是在一个容器内
    不然std::distance(it1, it2)等等函数会失效
    若两个迭代器属于不同容器，比较它们的 “前后位置”（如it1 < it2）是无意义的

    2. 需要开一个链表来存储用户开的迭代器
    如果发生删除和插入操作，需要将用户开的迭代器置空（这里就对应了iterator中参数_vec的作用，如果置空了用户还在使用直接抛出异常）
    所以需要定义一个函数，去处理迭代器链表空间，判断是否需要置空
    */
   
    class iterator{
    public:
        iterator(Vector<T, Alloc>* vec=nullptr, T* ptr = nullptr):_ptr(ptr),  _vec(vec) {
            // create一个就add到迭代器链表中
            IteratorNode* temp = new IteratorNode(this, _vec->_iter_head->_next);
            _vec->_iter_head->_next = temp;
        }
        ~iterator() {}
        iterator& operator++() {
            ++_ptr;
            return *this;
        }
        bool operator!=(const iterator& other) const {
            if (_vec==nullptr or other._vec != _vec)
                throw "iterator incompatible";
            return _ptr != other._ptr;
        }
        // 这里返回引用的原因为了支持迭代器可以修改值
        T& operator*() {
            if(_vec==nullptr){
                throw "iterator invalid";
            }
            return *_ptr;
        }
    private:
        T* _ptr;
        Vector<T, Alloc>* _vec;

        friend class Vector<T, Alloc>;
    };
    

    inline iterator begin() {return iterator(this, _first);}
    inline iterator end() {return iterator(this, _last);}

private:
    T* _first;
    T* _last;
    T* _end;
    Alloc _alloc;
    struct IteratorNode
    {
        IteratorNode(iterator* cur=nullptr, IteratorNode* next=nullptr): _cur(cur), _next(next) {}
        iterator* _cur;
        IteratorNode* _next;
    };
    // 如果不给IteratorNode指针实例化就是裸指针，在其上操作会导致一直报错，找了半天的bug
    // 这样的话析构的地方又要释放这块的空间，不然会导致内存泄漏
    IteratorNode* _iter_head = new IteratorNode();
    void expand();
    
    // 在会影响元素位置的地方都要使用它
    void validate(T* first, T* last){
        // 去验证_iter_head中的节点中的_cur迭代器中的_ptr是否在first和last之间
        IteratorNode* pre = _iter_head;
        IteratorNode* cur = _iter_head->_next;
        while(cur != nullptr){
            if(cur->_cur->_ptr >= first && cur->_cur->_ptr <= last){
                pre->_next = cur->_next;
                // 这里选择将容器置空，且把它从链表中删除
                // 但是可能用户还有备份
                // 所以delete的是结点而不是迭代器本身
                cur->_cur->_vec = nullptr;
                delete cur;
                cur = pre->_next;
            }else{
                pre = cur;
                cur = cur->_next;
            }
        }
    }
};

/*
这里的迭代器有问题，迭代器失效的问题没有考虑
当动态添加元素和动态删除时，代码会异常
earse和insert
iterator erase(iterator position);
iterator insert(iterator position, const T& value);  // 插入value的拷贝
在STL的实际实现在都是需要返回新的iterator
*/ 




//**********************************函数实现*************************************/

template<typename T, typename Alloc>
Vector<T, Alloc>::Vector(const size_t initial_capacity, const Alloc& alloc)
    :_alloc(alloc)
{
    _first = _alloc.allocate(initial_capacity);
    _last = _first;
    _end = _first + initial_capacity;
}



template<typename T, typename Alloc>
Vector<T, Alloc>::Vector(const Vector& other)
    :_alloc(other._alloc)
{
    size_t other_size = other._last - other._first;
    size_t other_capacity = other._end - other._first;
    _last = _first = _alloc.allocate(other_capacity);
    _end = _first + other_capacity;
    // 逐个构造元素
    for (T* p = other._first; p != other._last; ++p,++_last){
        _alloc.construct(_last, *p);
    }
}


template<typename T, typename Alloc>
Vector<T, Alloc>& Vector<T, Alloc>::operator=(const Vector& other){
    if(this==&other){
        return *this;
    }
    // 先销毁当前对象的元素
    for (T* p = _first; p != _last; ++p){
        _alloc.destroy(p);
    }
    _alloc.deallocate(_first);

    // 分配新的内存并复制元素
    size_t other_size = other._last - other._first;
    size_t other_capacity = other._end - other._first;
    _last = _first = _alloc.allocate(other_capacity);
    _end = _first + other_capacity;
    // 逐个构造元素
    for (T* p = other._first; p != other._last; ++p,++_last){
        _alloc.construct(_last, *p);
    }

    return *this;
}


template<typename T, typename Alloc>
Vector<T, Alloc>::~Vector(){
    // 销毁所有元素
    for (T* p = _first; p != _last; ++p){
        _alloc.destroy(p);
    }
    _alloc.deallocate(_first);
    // 销毁_iter_head
    IteratorNode* next;
    while(_iter_head!=nullptr){
        next = _iter_head->_next;
        delete _iter_head;
        _iter_head = next;
    }
    next = nullptr;
}


template<typename T, typename Alloc>
void Vector<T, Alloc>::expand(){
    std::cout << "Expanding vector from capacity " << (_end - _first) << " to " << (_end - _first) * 2 << std::endl;
    size_t current_capacity = static_cast<size_t>(_end - _first);
    size_t new_capacity = current_capacity * 2;
    T* new_first = _alloc.allocate(new_capacity);
    T* new_last = new_first;
    // 复制旧元素到新内存
    for (T* p = _first; p != _last; ++p, ++new_last){
        _alloc.construct(new_last, *p);
        _alloc.destroy(p); // 销毁旧元素
    }
    _alloc.deallocate(_first);

    _first = new_first;
    _last = new_last;
    _end = _first + new_capacity;
}


template<typename T, typename Alloc>
void Vector<T, Alloc>::push_back(const T& item){
    if (_last >= _end){
        expand();
    }
    _alloc.construct(_last++, item);
}   

template<typename T, typename Alloc>
void Vector<T, Alloc>::pop_back(){
    if (_last == _first){
        throw "Vector is empty";
    }
    validate(_last-1, _last);
    _alloc.destroy(--_last);
}

template<typename T, typename Alloc>
T& Vector<T, Alloc>::operator[](size_t index) const{
    if (index >= size()){
        throw "Index out of bounds";
    }
    return _first[index];
}


// ******************************函数实现结束******************************/


int main()
{
    // std::vector<int> v = {1,2};
    // auto temp = v.end();
    // std::cout << *(temp-1) << std::endl;
    // v.pop_back();
    // std::cout << *(temp-1) << std::endl;
    // // 这里输出是2 2
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
    try
    {
        Vector<int> vec(2);
        for (int i = 0; i < 3; ++i)
            vec.push_back(i);
            
        auto end = vec.end();
        vec.pop_back();
        std::cout << *end << std::endl;
    }
    catch(const char* msg)
    {
        std::cerr << msg << '\n';
    }

}

string

这里主要是重载运算符

#include<iostream>
#include <cstring>
#include<string>

#include <memory>


using namespace std;    


class String 
{
public:
    String(const char* str = nullptr);
    String(const String& other);
    String& operator=(const String& other);
    ~String();

    size_t size() const;
    const char* c_str() const { return _data; }
    bool operator==(const String& other) const;
    bool operator<(const String& other) const;
    bool operator>(const String& other) const;
    const char& operator[](size_t index) const{
        if (index >= size()) {
            throw "Index out of bounds";
        }
        return _data[index];
    }

    char& operator[](size_t index){
        if (index >= size()) {
            throw "Index out of bounds";
        }
        return _data[index];
    }
    // String operator+(const String& other) const;

    friend ostream& operator<<(ostream& out, const String &str);
    friend String operator+(const String& lhs, const String& rhs);

    class iterator
    {
    public:
        iterator(char* ptr = nullptr): _ptr(ptr) {}
        ~iterator() {}
        iterator& operator++() {
            ++_ptr;
            return *this;
        }

        bool operator!=(const iterator& other) const {
            return _ptr != other._ptr;
        }

        //这里返回引用的原因为了支持迭代器可以修改值
        char& operator*() {
            return *_ptr;
        }

    private:
        char* _ptr;

    };
    
    iterator begin() {
        return iterator(_data);
    }
    iterator end() {
        return iterator(_data + size());
    }
    
private:
    char* _data;
};

String::String(const char* str)
{
    if(str !=nullptr){
        _data = new char[strlen(str) + 1];
        strcpy(_data, str);
    }else{
        _data = new char[1];
        _data[0] = '\0';
    }
}

String::String(const String& other)
{
    _data = new char[strlen(other._data) + 1];
    strcpy(_data, other._data);
}

String& String::operator=(const String& other)
{
    if(other == *this){
        return *this;
    }
    delete [] _data;
    _data = new char[strlen(other._data) + 1];
    strcpy(_data, other._data);
    return *this;
}

String::~String()
{
    delete [] _data;
}

size_t String::size() const
{
    return strlen(_data);
}


bool String::operator==(const String& other) const
{
    return strcmp(_data, other._data) == 0;
}

bool String::operator<(const String& other) const
{
    return strcmp(_data, other._data) < 0;
}

bool String::operator>(const String& other) const
{
    return strcmp(_data, other._data) > 0;
}


// String String::operator+(const String& other) const
// {
//     char* new_data = new char[strlen(_data) + strlen(other._data) + 1];
//     strcpy(new_data, _data);
//     strcat(new_data, other._data);
//     String result(new_data);
//     delete [] new_data;
//     return result;
// }


String operator+(const String& lhs, const String& rhs)
{
    String result;
    delete [] result._data;
    result._data = nullptr;
    result._data = new char[strlen(lhs._data) + strlen(rhs._data) + 1];
    strcpy(result._data, lhs._data);
    strcat(result._data, rhs._data);
    return result;
}

ostream& operator<<(ostream& out, const String &str)
{
    out << str._data;
    return out;
}

int main(){

    // string::iterator it;
    String str1("Hello, world!");

    // int i = 0;
    // for(auto it = str1.begin(); it != str1.end(); ++it, ++i){
    //     *it = 'A' + i;
    // }
    for(auto it = str1.begin(); it != str1.end(); ++it){
        cout << *it << " ";
    }
}



#if 0
int main(){
    String str1("Hello,");
    String str2("World!");
    String str3 = str1 + str2;

    cout << "str1: " << str1 + "ddd" << endl;
    cout << "str2: " << "ddd" + str2 << endl;
    cout << "str3: " << str3 << endl;

    cout << "str1 size: " << str1.size() << endl;
    cout << "str2 size: " << str2.size() << endl;
    cout << "str3 size: " << str3.size() << endl;

    cout << "str1 == str2: " << (str1 == str2) << endl;
    cout << "str1 < str2: " << (str1 < str2) << endl;
    cout << "str1 > str2: " << (str1 > str2) << endl;

    for (size_t i = 0; i < str1.size(); i++)
    {
        cout << "str1[" << i << "] = " << str1[i] << endl;
    }
    for (size_t i = 0; i < str1.size(); i++)
    {   
        str1[i] = 'A'+i;
        cout << "str1[" << i << "] = " << str1[i] << endl;
    }
    

    return 0;
}
#endif