C#和.Net框架

vector实现原理

(新手向)谈谈C++中的萃取
侯捷C++课程笔记03: STL标准库与泛型编程

• 容器vector的代码如下:

template<class T, class Alloc= alloc>
class vector {
public:
    typedef T value_type;
    typedef value_type* iterator;
    typedef value_type& reference;
    typedef size_t size_type;
protected:
    iterator start;
    iterator finish;
    iterator end_of_storage;
public:
    iterator begin() { return start; }
    iterator end() { return finish; }
    size_type size() const { return size_type(end() - begin()); }
    size_type capacity() const { return size_type(end_of_storage - begin()); }
    bool empty() const { return begin() == end(); }
    reference operator[](size_type n) { return *(begin() + n); }
    reference front() { return *begin(); }
    reference back() { return *(end() - 1); }
};

容器vector的迭代器start指向第一个元素,迭代器finish指向最后一个元素的下一个元素,这两个迭代器对应begin()和end()的返回值,维持了前闭后开的特性.

vector对使用者是连续的,因此重载了[]运算符.

vector的实现也是连续的,因此使用指针类型做迭代器(即迭代器vector<T>::iterator的实际类型是原生指针T*).

内存满了怎么办（push_back）

• vector::push_back方法先判断内存空间是否满,若内存空间不满则直接插入;若内存空间满则调用insert_aux函数先扩容两倍再插入元素.

void push_back(const T &x) {
    if (finish != end_of_storage) { // 尚有备用空间,则直接插入,并调整finish迭代器
        construct(finish, x);        
        ++finish;                    
    } else                             // 已无备用空间则调用 insert_aux 先扩容再插入元素
        insert_aux(end(), x);
}

• insert_aux被设计用于在容器任意位置插入元素,在容器内存空间不足会现将原有容器扩容.

template<class T, class Alloc>
void vector<T, Alloc>::insert_ux(iterator position, const T &x) {
    if (finish != end_of_storage) {     // 尚有备用空间,则将插入点后元素后移一位并插入元素，因为这个函数还会被其他函数调用，比如insert之类的所以还是要检查
        construct(finish, *(finish - 1));   // 以vector最后一个元素值为新节点的初值
        ++finish;
        T x_copy = x;
        copy_backward(position, finish - 2, finish - 1);
        *position = x_copy;
    } else {
        // 已无备用空间,则先扩容,再插入
        const size_type old_size = size();
        const size_type len = old_size != 0 ?: 2 * old_size:1;  // 扩容后长度为原长度的两倍

        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;
        try {
            new_finish = uninitialized_copy(start, position, new_start);    // 拷贝插入点前的元素
            construct(new_finish, x);                                       // 插入新元素并调整水位
            ++new_finish;
            new_finish = uninitialized_copy(position, finish, new_finish);  // 拷贝插入点后的元素()，还是比如说insert函数，这种情况就要把后面的元素进行拷贝
        }
        catch (...) {
            // 插入失败则回滚,释放内存并抛出错误
            destroy(new_start, new_finish) :
            data_allocator::deallocate(new_start, len);
            throw;
        }
        // 释放原容器所占内存
        destroy(begin(), end());
        deallocate();
        // 调整迭代器
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
    }
};

map实现原理

红黑树

hash表

• 复杂度O(1)

构造方法

• 直接定址法

H(key) = key 或 H(Key) = a * key + b

• 除留余数法

H(key) = key % p(p <=m , m = 散列表长)

• 数字分析法

  • 如果关键字是r进行数，取数码分布比较均价的若干位作为key

• 平法取中法

  • 将关键字平法取中间几位

处理冲突

开放定址法

• 空闲地址既可以存放同义词也可以存放非同义词

线性探测法

平方探测法

再散列法

伪随机序列

---

• 开放定址法不能删除已有元素

拉链法

将同义词存放在一个线性表中