C_stl_notes1

**侯捷老师的C++笔记1--STL**

p1. Basics

  • OOP vs. GP
    • OOP: 将datamethods关联起来,
    • GP: 将datamethods分开来
      • Containers and Algorithms 可以各自闭门造車,中间以iterator连通
      • Algorithms通过Iterators确定操作范围,来取Container的数据
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        // default comparator
        template<class T>
        inline const T& max(const T& a, const T& b) {
        return a < b ? b : a;
        }
        // comparator as one argument
        template<class T>
        inline const T& max(const T& a, const T& b, Compare comp) {
        return comp(a, b) ? b : a;
        }
        // new comparator
        bool strLonger(const string& s1, const string& s2) {
        return s1.size() < s2.size();
        }
        // test
        cout << "max of zoo and hello: "
        << max(string("zoo"), string("hello")) << endl; // zoo
        cout << "max of zoo and hello: "
        << max(string("zoo"), string("hello"), strLonger) << endl; // hello
  • C++ Standard Library > Standard Template Library (STL - Generic programming)
  • 重要网站:
  • 书籍:
    • The C++ standard Library
    • STL源码剖析
  • STL六大部件(Components):
    • 容器(containers)
    • 分配器(allocator)
    • 算法(algorithms)
    • 迭代器(iterators)
    • 适配器(adapters)
    • 仿函数(functors)
      avatar
  • 前闭后开区间:end指向最后一个元素的下一个,地址不一定是连续的
    avatar
    1
    2
    3
    4
    5
    Container<T> c;
    ...
    Container<T>::iterator ite = c.begin();
    for (; ite != c.end(); ++ite)
    ...
  • range-based for statement (since C++11)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // e.g.1
    for (int i : {1, 3, 2, 4}) {
    std::cout << i << std::endl;
    }
    // e.g.2
    std::vector<double> vec;
    ...
    //不改变值
    for (auto elem: vec) {
    std::cout << ekem << std::endl;
    }
    // 改变值
    for (auto& elem: vec) {
    elem *= 3;
    }
  • Specialization(特化): 对指定的类型有不一样的操作
  • Partial Specialization(偏特化):
    • 两个模板参数变成一个
    • 范围: 是指针,或者const

ALLocators

  • VC6 or BC5 or G2.9allocator只是以::operator new –> malloc()::operator delete –> free()来完成allocate()deallocate(),没有其他特殊的设计, 会有很多的overhead,每一个数据都需要多余的空间
  • G2.9的容器用的是另一个分配器(alloc)
    • 根据数据的大小来分配内存块,按照block来分配
    • malloc()会直接去拿一个block,所以只带一份overhead
    • 在G4.9中,变成了_pool_alloc

Container(容器)

  • 分类
    • avatar
    • Composition的关系,并非inheritance
      C++11中,slist –> forward_list
      hash_set, hash_map –> unordered_set, unordered_map, hash_multiset, hash_multimap –> unordered_multiset, unordered_multimap
    • avatar

List (双向环状链表)

  • 不能用::sort()来排序,因为要randomAccessIterator, 而list不属于

  • iteratorend()指向一个空白节点
    avatar

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    // G2.9
    template <class T>
    struct __list_node {
    typedef void* void_pointer;
    void_pointer prev; // 需要后期转型, 在G4.9有所改变
    void_pointer next;
    T data;
    };
    // list's iterators
    template<class T, class Ref, class Ptr> // 多余了,只需要传一个即可
    struct __list_iterator {
    // Iterator必须提供的5种associated types
    typedef __list_iterator<T, Ref, Ptr> self;
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef __list_node<T>* link_type;
    typedef ptrdiff_t difference_type;

    link_type node;
    reference operator*() const { return (*node).data; }
    pointer operator->() const { return &(operator*()); }
    // prefix add, ++i, return reference
    self& operator++()
    {
    node = (link_type)((*node).next); // node是迭代器的指针
    return *this; //return by reference
    }
    // postfix add, i++, with an int argument, return value
    self operator++(int)
    {
    self tmp = *this; // 先唤起copy ctor,所以不会唤起operator*
    ++*this; // 不会唤起operator*, 因为*this会作为++()的参数
    return tmp; // return by value, 唤起copy ctor
    }
    ...
    };

    vector :

  • 当空间不够时,会扩充为原来大小的二倍,需要将原来的数据拷贝到新的地址

  • 连续空间,iterator可以用单纯的指针来表示

    • const size_type len = old_size != 0 ? 2 * old_size : 1;
  • vector’s iterator:

    • vector<int> vec;
      vector<int>::iterator ite = vec.begin();
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      template <class T, class Alloc = alloc>
      class vector {
      public:
      typedef T value_type;
      typedef value_type* iterator; // T*
      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(finish() - begin());}
      size_type capacity() const
      {return size_type(end_of_storage - begin());}
      // 不直接使用begin和finish是以防之后设计的变化
      bool empty() const {return begin() == end();}
      // []重载
      reference operator[](size_type n)
      {return *(begin() + n);}
      reference front() {return *begin();}
      reference back() {return (*end() - 1);}
      };

    Array

  • 固定数量的数组,没有ctor也没有dtor

  • 连续空间存储

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    template<typename _Tp, std::size_t _Nm>
    struct array
    {
    typedef _Tp value_type;
    typedef _Tp* pointer;
    typedef value_type* iterator;
    // support for zero-sized arrays mandatory
    value_type _M_instance[_Nm ? _Nm : 1];
    iterator begin()
    {return iterator(&_M_instance[0]);}
    iterator end()
    {return iterator(&_M_instance[_Nm]);}
    ...
    };

    forwar_list: 单向链表

  • 类似于双向链表

0%