STL源码剖析(172)

发表于   |   分类于

最近被git上一个项目打击了；想想自己c++书籍都看了十多本了，以为可以睥睨了。唉！！虽然公司编程不允许模板，但是身为程序员还是有学的必要。这本书一定要看完。

1、STL版本众多

stl版本众多，但是有些头文件有很大一长串的版权注释（以前在codeproject也发现的）。这些都是参照HP版本的。允许任何人免费使用、拷贝、修改、传播、贩卖这份文件，唯一需要遵守的是必须在所有文件加上HP版本声明。哈哈看来国外人也喜欢装逼，都希望往自己开源代码放版权声明。

2、模板中的静态变量

template <typename T>
class testclass P{
    public:
        static int _data;
};
int testclass<int>::_data = 1;
int testclass<char>::_data = 2;

testclass<int> ob1;//ob1._data 1
testclass<char> ob2;//ob2._data 2
//我想,我如果我再用一层typedef来换容的话。这代码就好看多了！

3、模板中的特殊设计

template <class i, class o>
struct dd {};//由于是模板，可以运行任何类型，要判断指针，可以用ispont的std函数

template <class T>
struct dd <T*, T*> {};

template <class T>
struct dd <const T*, T*> {};

4、模板类型可赋值

template<class T, class R, size_t Bufsize = 0>
struct deq{}
    deq() {cout <<ｂufsize;};
;

5、模板操作函数

bool operator== <> (const stack&, const stack&);

6、构造函数特例化

template <class key> struct hash {
    void operator()() {cout <<＂ｈｅｈｅ＂ << endl;}
};
template <> struct hash<char> {
    void operator()() {cout <<＂ｉｓ　ｃｈａｒ＂ << endl;}
}
hash<long> t;//hehe
hash<char> d;//is char

7、迭代器

  • vector就不讲了。
    • template
      class vector {…};
  • list环状双向链表
    • template
      class list {…};
  • deque双向开口连续空间，可头尾操作。内存结构：元素是指针，指向一个更大的连续空间map，数据就放在map中。通过参数赋值来定义map大小。
    • template
      class deque{…};
  • stack先进后出，不允许遍历行为（严格不是迭代器）
  • queue先进先出。
  • slist单向链表，空间更小，操作更快。
  • set 它的实值就是键值。自动排序 ,切不允许键值重复现象
    • template , class Alloc = alloc>
      class set {…};
  • map所有元素会根据元素键值自动排序。不允许键值重复现象
    • template , class Alloc = alloc>
      class map {…};
    • map d;

      d.insert(make_pair(2, 3));

      d.insert(map::value_type(2, 3));
  • multiset、multimap都允许键值重复现象。

8、hash

普及下hash表知识

迭代器多用于数据的存储，添加，删除，操作等；（而关联器set，map等）大多以红黑树为基础；
但是当对存储数据希望以常数时间来搜寻时，
特别是大量的无序数据，使用hash表的时间优势便有了。


hash表是通过数组记录的方式来存储，之后又有一次探测、二次探测来对同一位置记录成一链表（具体可以看stl源码）

简单表述


一个a数组有10个元素，这些元素个个是100以内的数。如果要快速记录和查询方式是：开辟一个100大小的b数组，从a数组中遍历，执行b[a[i]]++操作

这些无论什么操作都在b中执行，统计、查找等。因为b那边是常数级的。b便是hash表

当对b大小进行限制为50的时候，每个b就必须存俩个记录了，这便是探测算法需要的。

  • hash_set　
    • template , class EqualKey = equal_to, class Alloc = alloc>

      class hash_set {…};
  • hash_map
    • template , class EqualKey = equal_to, class Alloc = alloc>

      class hash_map {…};
  • hash_multiset
    • template , class EqualKey = equal_to, class Alloc = alloc>

      class hash_multiset {…};
  • hash_multimap
    • template , class EqualKey = equal_to, class Alloc = alloc>

      class hash_multimap {…};

9、组合序列

vector分别push: {a, b, c}; 那“abc”就是它的组合序列

当根据less-than(less<T>())的字典排序后，它的下一序列便是：acb、bac、bca
如175的next_permutation和prev_permutation；

// //