编程杂谈

shared_ptr的一些理解

Posted on

瞎看了一点博客自认为搞懂,现在没什么时间写代码,写简单记下来。

shared_ptr的是一种“引用计数型智慧指针”(RCSP),它最核心的本质在于引用计数。
并且这个引用计数器也是一个类指针。

除开这个引用计数器以外,自然还有本重要的指针了,除此之外就没有其他的成员变量。

shared_ptr与uniqe_ptr的重要区别在于,unique_ptr只能指向一个对象,这是由它的析构函数决定的,因为析构函数必定会释放掉指针所指的内存,如果指向多个,将会多次释放,引起错误。
因此,unique_ptr的构造是不允许nullptr的。

与此相对,shared_ptr却可以,而且他默认构造就是指向nullptr,在真正构造非空对象的时候,才会将两个指针用上。
并且在赋值等操作引起计数器变为 0 的时候会立刻delete,而就算没有变为0,在最后析构的时候也会强制delete。

上面那个是我的煞笔言论,shared_ptr的delete内存只会在引用计数为0的时候调用,这就造成了循环引用导致的内存泄漏问题,进而引出了weak_ptr。

写完好像很简单的样子……

另外,shared_ptr并不是线程安全的,这个留待以后再提,而线程安全的RCSP应该有atomic_shared_ptr,应该是这个。

2018-04-04 17:05:13 星期三 更新一个简单实现

template <typename T>
class SmartPointer {
    size_t* count;
    T* pointer;

    SmartPointer()
        : pointer(nullptr)
        , count(new size_t)
    {
    }

    SmartPointer(T* p)
        : pointer(p)
        , count(new size_t)
    {
        *count = 1;
    }

    SmartPointer(const SmartPointer& sp)
        : pointer(sp.pointer)
        , count(sp.count)
    {
        *count++;
    }

    SmartPointer(SmartPointer&& sp)
        : pointer(sp.pointer)
        , count(sp.count)
    {
        ++(*count);
    }

    void operator=(SmartPointer&& sp) { SmartPointer(std::move(sp)); }

    ~SmartPointer()
    {
        if (--(*count) <= 0) {
            delete count;
            delete pointer;
            count = pointer = nullptr;
        }
    }

    T* operator->() { return pointer; }
    T* operator*() { return *pointer; }
    T* get() { return pointer; }
    size_t use_count() { return count == nullptr ? 0 : *count; }
    bool unique() { return count != nullptr and *(count) == 1; }
    void swap(SmartPointer& sp) { swap(sp, *this); }
};
红黑树

红黑树源码分享

Posted on

本人开学后花了三天终于在昨天3.10(也是本人的阳历生日)完成了红黑树的实现

自认为没有bug……

不过感觉接口设计上不是很好,觉得得学习一下stl

源码在github上,点这里

上面那个是看思路自己意淫出来的,这里有个模仿STL的版本

但是没有改好。。还有几个error……

除此之外,特别想说一个知识点,就是在模板实现上,其声明和定义是不能卸载两个文件里的,因为在编译的时候,编译器就必须知道类的大小(好吧,其实我也解释不大来……

非要写在两个文件里的话,我只知道特化,当然,这不是很可取。

完。

学习笔记

一些关于STL空间配置器的理解

Posted on

一点废话

最近终于看完了《STL源码剖析》的前三章,个人觉得前三章是这本书最重要的部分,考虑到时间问题(简历还没投啊,拖太晚了),其他的具体实现先放放也罢。

关于STL中的空间配置器(allocator),在STL的运用角度上看,空间配置器是最不需要知道的东西。而在STL的实现上,空间配置器是最必须也是最先需要知道的东西。

乱七八糟的东西

首先我们必须知道的是,在C++中通过new一个新的对象,它的实际步骤可以分为两个部分:配置内存(allocat),调用构造函数(construct)。而当我们通过delete一个对象的时候,它的实际步骤也可以分为两个部分:调用析构函数(destroy),释放内存(deallocat)。

关于构造和析构,并不是我这里讲的重点,只要会点基础的cpp就好了。
而关于对象构造前的空间配置和对象析构后的空间释放,SGI STL对此的设计哲学如下:

  • 向system heap 申请空间
  • 考虑多线程状态
  • 考虑内存不足的应变措施
  • 考虑过多的小型区块可能造成的内存碎片问题

核心部分

一些乱七八糟的东西讲完了(大概……
现在讲一下最核心的部分。

SGI STL对于内存的管理主要用到这几点措施

  • 将大内存和小内存分开处理
  • 对于小内存都会进行对齐处理,简单说就是向上取8的倍数
  • 采用了内存池

详细一点说,首先对于传入的内存申请量,判断大小,以128bytes 为界,向上为大内存,向下为小内存。
对于大内存,直接调用系统函数,malloc / realloc / free 等。若内存不够,则调用 oom 函数 (out of memory),oom函数的主要部分是不断调用new-handle函数,直到内存足够,或者异常退出。

而对于小内存,以一个二维链表维护,从8bytes ~ 128 bytes ,以8的倍数划分总共16个链表。

  1. 对于申请的内存,先进行对齐,然后看链表中是否有空闲内存,如果有直接返回。
  2. 如果没有,则向内存池中申请较多内存,一部分返回,其他大部分自己留着。
  3. 如果内存池中没有,则向系统堆空间申请两倍内存池申请量,一半给内存池,一半给二维链表。如果系统堆中还是没有,就调用oom函数。

用文字简述的话就已经到此为止了。