Andy Niu �����ĵ�

1、标准STL序列容器：vector、string、list和deque
2、标准STL关联容器：set、multiset、map和multimap
3、vector和string是基于连续内存，list、set和map是基于节点。
    而deque是二者的结合，deque内部是一块一块的，块与块之间是基于节点，块内部基于连续内存。
4、对比vector，deque是双向开口。

1、为什么？
    从逻辑结构上，容器分为序列容器和关联容器。
    从物理结构上，容器分为基于连续内存的容器和基于节点的容器。
2、对于不同的容器，支持的方法不一样（也就是暴露出来的接口不一样）。
    相同方法名内部做的事情是不一样，迭代器、指针和引用无效的规则是不同的。

1、容器保存的对象，并不是你提供给容器的对象，而是这些对象的副本。
2、保存对象的时候，调用copy构造，创建出副本。
    这里特别注意：子类对象保存到父类容器中会存在对象切割。
3、因为是整体拷贝，为了高效，可以使用指针。但是指针带来问题，需要管理动态内存，可以使用智能指针解决这个问题。
    但是千万不能是auto_ptr，因为这玩意的拥有权会转移。
4、为了避免不必要的拷贝，对于vector可以使用reserve提前把内存分配好，这个时候并没有调用构造方法创建对象。

1、二者的作用是一样的，结果也是等价的。就是判断集合是否为空。
2、二者是等价的，为什么强调使用empty，因为empty效率更高。
3、在STL中，对于一般的集合，empty和size都是常数时间。但是对于list，empty是常数时间，size是线性时间；考虑为什么？
    考虑增删操作，对于一般的集合，增删是线性时间，因为涉及到元素的移动，增删的同时也就更新了元素个数。
    但是对list增删，是常数时间，不会更新节点个数。
    因此，对于一般的集合，size是实时更新的，empty与size可认为是等价的。
    但是对于list：对于empty，只需要检查head是否为end就可以了，为常数时间。对于size，必须遍历，为线性时间。

1、考虑一个包含int的文件，复制到list，如下：
    ifstream dataFile("ints.bat");
    list<int> data(istream_iterator<int>(dataFile),istream_iterator<int>());
2、上面的代码不是预期的行为。
3、先从最简单开始，声明方法 int f(double d); 等价的写法有 int f (double (d)); int f (double);
    也就是说，形参名称可以使用括号括起来，形参名称也可以省略，只保留形参的类型。
4、考虑int g(double (*pf) ()); 形参是一个方法指针，等价的写法有 int g(double pf ()); 
    我们省略形参名称，就变成了 int g(double ());
5、现在考虑list<int> data(istream_iterator<int>(dataFile),istream_iterator<int>()); C++编译器会认为这个一个方法声明，
    第一个形参是：形参类型是istream_iterator<int>，形参名称是 dataFile，只不过使用括号括起来了，
    第二个形参是：形参类型是一个方法指针，指向的方法是返回istream_iterator<int>，接受形参void，省略了形参名称。
6、C++中有一条规律，语句优先解释成 方法声明。当这个解释失败，才进行其他解释。最常见的如下：
    Student s; // OK
    Print(s);
    
    Student s = Student(); // OK
    Print(s);
    
    Print(Student()); // OK
    
    Student* s = new Student(); // OK
    Print(*s);
    
    Student* s = new Student; // OK
    Print(*s);
    
    Student s(); // Error
    Print(s);
    因为C++会把Student s();当成一个方法声明。
7、怎么解决上面的问题？
    两种办法：
    办法一，对于方法调用，实参可以使用括号括起来，而对于方法声明，把整个形参（包括形参类型和形参名称）括起来是错误的，
    因此可以如下：
    list<int> data( (istream_iterator<int>(dataFile) ),istream_iterator<int>());
    办法二：不使用匿名对象，使用具名对象，如下：
    istream_iterator<int> begin(dataFile);
    istream_iterator<int> end;
    list<int> data(begin,end);

1、使用new动态分配内存，必须承担如下责任：
    a、使用delete释放内存
    b、确保使用了正确的形式，delete与new的形式要匹配
    c、不能重复delete
2、使用vector和string可以消除以上的负担。每当要动态分配一个数组时，都要考虑使用vector和string替代。
    如果元素是字符char，使用string。否则使用vector。注意：有一种特殊情况，使用vector<char>更合理。
3、vector和string的元素分配在堆上，它们内部维护一个指针，指向堆上的元素。vector和string是深拷贝，会把元素逐个拷贝。
4、vector和string，它们自己管理内存，内存会自动增长，当它们析构时，会对每个元素逐个析构。
5、vector和string是功能完全的STL序列容器，可以使用很多STL功能。而数组只支持部分STL算法，
    没有begin，end，size这样的成员方法，也没有iterator这样的嵌套类型，因此STL更好用。
6、为了支持旧的代码，将vector和string转化为数组很简单。
7、有一种特殊情况，需要考虑。string是如此常用，它的使用效率很重要。因此，STL中的string有可能是基于引用计数来实现的。
    这在多线程中，会出现冲突问题。如果string不是引用计数，而是整体拷贝，多线程就不会有问题，因为每个线程修改自己的副本。
8、对于基于引用计数的string，又运行在多线程环境下，有三种可行的选择：
    a、禁止引用计数，这种做法不可移植
    b、寻找一个不使用引用计数的string
    c、考虑vector<char>，代替string
    注意：VS2010中的STL，string没有使用引用计数。

1、尽量使用vector和string替换数组，但是老的代码还是使用数组。如果老的接口期望是数组，怎么办？
    需要把vector和string，暴露出数组接口，也就是第一个元素的地址。
2、考虑方法DoSomething(const int* pInt,size_t size)，对于vector<int> vec，调用如下：
    DoSomething(&vec[0], v.size());
    这里有个问题，vec的大小可能为0，更安全的做法是：
    if(!vec.empty())
    {
    　　DoSomething(&vec[0], v.size());
    }
3、考虑，能不能使用begin()替换&vec[0]？
    我们知道，begin返回迭代器，是对指针的封装，类似于指针。
    但是，不能把迭代器当成指针使用，可以使用&*begin()，这种方式与&vec[0]等价，显然&vec[0]更直观。
4、考虑DoSomething(const char* pa); 对于string str，调用如下：
　　DoSomething(str.c_str());
　　c_str返回一个char指针，指向字符串值，尾部再加一个空字符。str长度可以为0，返回空字符，内部也可以包含空字符。
    但是，DoSomething的处理是以第一个空字符作为结束。
5、vector暴露出指针，调用端修改元素的值，通常没有问题。但是不能增加新元素。
    因为在外部增加新元素，vector不知道，不去更新size，size产生不正确的结果。如果大小和容量相等，增加元素就会踩内存了。
    注意：对于排序的vector，修改vector的元素值，也会产生问题。因为修改元素值后，导致vector无序。
6、考虑C API数组初始化vector，很简单。如果C API数组初始化string呢？
    可以先初始化vector<char>，vector<char>再去初始化string。当然，还可以解决更一般化的问题。
    先把C API数组写到vector，再把vector写到期望的STL容器中。对于逆向的转化，同样道理。先把STL容器的元素写到vector，再把vector传递给C API数组。
    也就是说，vector是一个适配器。

1、考虑下面的需求，对于vec开始的时候有1000个元素，后来只有10个元素，那么vec的capacity至少还是1000，
    后面的990个内存单元，没有使用，但是还被vec霸占着。如何释放这些内存呢？
2、我们知道，vector进行copy构造的时候，根据rhs 的size进行分配内存。因此，我们可以建立一个临时对象，然后交换一下就可以了。如下：
    vector<int>(vec).swap(vec);
    vector<int>(vec) 是个临时对象，可认为capacity为10，而vec的capacity为1000，二者交换后，vec的capacity为10，临时对象析构。
3、这里需要注意两点：
    a、临时对象的capacity有可能还是大于10，不能保证容量最小，而是尽量小。
    b、对于vector 的swap方法，内部实现只是交换了彼此的begin指针和end指针，并没有交换内容。
    这个很好理解，对于资源管理类，也就是内含指针的类，交换的时候，只需要交换彼此的指针就好了。
    举个例子：甲住501，乙住502，现在甲乙想换房子。只要换一下钥匙就好了，如果去把房间里的家电家具换一下，方法也太笨了。
4、考虑一个特殊情况，我想清空一个容器，并释放所有内存，该怎么办？
    首先，clear方法是不行的，因为它只是把元素清空，内存还被霸占着。由上面的分析，很容易想到，拿一个空容器与当前容器交换一下，就行了。
    也就是：vector<int>().swap(vec);

1、高级语言有个缺点，抽象程度提高了，但是所生成的代码效率降低了。
2、操作一个只包含double类型的对象比直接操作double效率要低。
3、但是将函数对象传递给STL算法往往比传递函数效率要高。这是为什么？
4、第一个原因，C++并不能真正地将一个函数作为参数传递给另一个函数，而是转化为函数指针传递过去。
    这就意味着，主调函数通过指针发出调用，编译器不会进行内联优化。
    也就是说，函数指针参数抑制了内联机制。而函数对象是可以进行内联优化的。
    因此，C++的sort算法就性能而言总是优于C语言的qsort
5、第二个原因，使用函数，有时候编译器会拒绝合法的代码，编译失败。而使用函数对象没有这个问题。
6、第三个原因，使用函数对象有助于避免一些微妙的、语言本身的缺陷。
    也就是说，STL算法对于函数对象有更好的支持。

1、一条语句做多件事情，使用复杂的函数嵌套，会导致代码难以阅读和理解。
2、软件工程的一条真理：代码被阅读的次数远远大于他被编写的次数。
3、更好的方法是：把做的多件事情分成几步来做。