*vector ,const char* c ,?&vector[0]卛_
*string Qstring.c_str()
17.使用“交换技?#8221;来修正过剩容?br />*vector<Contestant> vec(contestants).swap(contestants)
18.避免使用vector<bool>
两个问题
*它不是一个STL容器Q它q不容纳bool
如果C是一个Tcd的对象的容器Q且C支持operator[],那么以下代码必须能够通过~译
T* p= &c[0] //无论operator[]q回什么，都可以用q个地址初始化一个T*
但是vector<bool>中做了优化，里面存放的是bit?br />deque内部内存不是q箋的，但里面存的是bool?br />q有一个bitse可解册个问?/p>
19.了解相等和等L区别
*相等的概忉|Zoperator== ,{h的概念基于operator<
20.为指针的兌容器指定比较cd
兌容器?相同 的定义是{h
21.永远让比较函数对相等的D回false
22.避免原地修改set和multiset的键
]]>
条款10Q注意分配器的协定和U束
如果要自定义分配?br />*把你的分配器做成一个模板，带有模板参数TQ代表你要分配的内存的对象类?br />*提供pointer和reference的typedefQ但L让pointer是T* reference是T&
*通常Q分配器不能有非静态的数据成员
*记得应该传给分配器的allocate成员函数需要分配的对象个数而不是字节数Q也应该记得q些函数q回T*指针Q即时还没有T对象被构?br />*一定要提供标准容器依赖的内嵌rebind模板
条款12Q对STL容器U程安全性的期待现实一?/p>
template<typename Container>class Lock
{
public:
Lock(const Container container): c( containner ){
Lock( getMutexFor( c );
} ~Lock(){ releaseMutexFor( c ); }private:const Container& c;
};vector<int> v;{ Lock< vect< int > > lock( v ); vector<int>::iterator first5( find(v.begin() v.end(), 5)); if( first5 != v.end()){ *first5 = 0; }}
]]>
c.erase ( remove( c.begin(), c.end(), 1963 ), c.endQ） Q；//当C时vector,string ,dequeӞq是一处特定值得元素的最x?br />*当C是标准关联容器的时?map, set)使用M叫做remove的东襉K是完全错误的
而应该直接采用c.erase(1963)Ҏ的高效时?br />*但如果操作是从C中除L个有特定值的物体
bool bandValue(int x)
对于序列容器Qvector, string,deque,list)我们要做的只是把每个remove替换为remove_if然后OK?br />c.erase( remove_if(c.begin(), c.end(), badValue), c.end())//vector,string,deque
c.remove_if( badValue ) //list
对于标准兌容器Q?br />AssocContainner<int> c;
for(AssoContainer<int>::iterator i = c.begin();
i!= c.end(); )
{
if(badValue(*i)) c.erase(i++);
else ++i;
}
]]>
*对于所有标准序列容?vectorQ?string, deque, 和list)都有效，无论何时你必d全替代一个容器的内容Q你应该想到赋?br />*insertQ每ơ都必须Ud为新元素腑ևI间
*序列容器erase时返回P代器Q而关联容器返回空
条款六，警惕C++最令h恼怒的解析
int g( double pf() ) pf其实是一个指?br />int g( double() );同上Q函数名省略
int g( double x) == int g( double (x) )
条款七， 当时用new得指针的容器Ӟ记得在销毁容器前delete那些指针
*q样的代码造成内存泄露
void doSomething(){ vector<Widget*> vwp; for(int i =0 ; i < SOME_MAGIC_NUMBER; ++i) { vwp.push_back(new Widget); } //使用完毕的时候，vwp内的Widget对象没有释放}
最单的实现Ҏ?/p>
void doSomething(){ for(vector<Widget*>::iterator i = vwp.begin(); != vwp.end(); ++i) { delete *i; }}
q样的问题是for循环代码多余for_eachQ但没有使用for_each单明?br />另一个问题是q段代码不是异常安全?/p>
z不考虑异常的方?/p>
struct DeleteObject{ template<typename T> void operator()(const T* ptr) const { delete prt; }};void doSomething(){ deque<SpecialString*> dssp; for_each( dssp.begin(), dssp.end(), DeleteObject());}void doSomething(){ typedef boost::shar_ptr<Widget> SPW; vector<SPW> vwp; for(int i = 0; i <SOME_MAGIC_NUMBER; ++i) { vwp.push_back( SPW(new Widget)); }}
]]>
条款?容器用empty来代替检查size()是否?
*理由很简单，对于所有的标准容器Qempty是一个常数时间的操作Q但对于一些List实现Qsize()pU性时?br />*list的sizepU性时间是因ؓZ让splice变ؓ常数旉Q这是一个让哪个函数实现最高效率的问题
所以对于所有容器来_用empty()而不是size()==0
]]>
UML 的几?ȝQ不一定对。?br />兌一般保存的都是指针
聚合一般保存的都是对象
依赖一般都是参?br />兌都是我主动方指向被动?br />
一般来讲不要这么写Q?/p>
class Widget{
};vector<Widget> vw;Widget bestWidget;vector<Widget>::iterator i = find(vw.begin(), vw.end(),bestWidget);
要这么写
class Widget{};typedef vector<Widget> WidgetContainer;typedef WidgetContainer::iterator WCIterator;WidgetContainer cw;Widget bestWidget;WCIterator i = find(cw.begin(), cw.end(),bestWidget);
]]>
*vector list deque Qvector是一U可以默认用的序列cdQ当很频J的对序列中q行插入和删除的时候应该用listQ大部分发生在尾部的话用dequeq种数据l构
*q箋内存容器和基于节点的容器的区?br />q箋容器vector/string/deque在一个或者多个内存块中保存它们的元素Q如果新元素被插入或者已存元素被删除Q其他在同一个内存块中的元素必须向上或者向下移动来为新元素提供I间或者填充原来被删除的元素所占的I间Q这U移动媄响了效率?br />Z节点的listQ插入或者删除的时候不需要移?br />*序列容器在Q意位|插入一个新元素Q关联容器不可以
*容器中的数据的内存布局需要兼容C吗，如果是，那只能用vector
*查找速度Q散列容器》排序的vector>标准的关联容?br />*需要可靠的插入和删除的能力Q如果是需要用基于节点的容器
*需要P代器、指针、引用的实效ơ数减少到最，如果是，使用介于节点的容器，一般来_在连l容器上的插入和删除会所有指向容器的q代器指针和引用实效
]]>
1、倒{单链?/p>
非递归?/p>
- struct Node
- {
- int data;
- Node * next;
- }
- void reverse(Node*& head) {
- if (head == NULL) {
- return;
- }
- Node * pre, * cur, * nxt;
- pre = head;
- cur = head -> next;
- while (cur != NULL) {
- pre = cur -> next;
- pre = cur;
- cur = nxt;
- nxt = nxt -> next;
- }
- head -> next = NULL;
- head = pre;
- }
递归?/p>
- Node * reverse(Node * node, Node *&head)
- {
- if (node == NULL || node -> next == NULL) {
- head = node;
- return;
- }
- else {
- Node * nxt = reverse(node -> next, head)
- node = nxt -> next;
- return node;
- }
- }
- 最后要返回的node的next域设为NULL?nbsp;
2、找出倒数Wk个元?或中间元素）Q设|快慢指?br />
3、删除环状单链表的一个节点，只给定指向要删除节点的指?/p>
思\Q无法获取前一个指针，那么可删除下一个节点，交换当前节点和下一个节点的值即?br />
4、两个有序链表的合ƈ
归ƈ卛_
5、判断单链表是否有环Q环首？
是否有环Q快慢指针，如果盔RQ说明存在环
环首Q可先求出环ѝ一个圆内的q及问题Q两ơ相遇时慢指针走q的距离即环长；
此时假设慢指针已Ci步，则快指针已走?i步；两个指针同时倒退i步的位置Q慢指针退到链首，快指针退到i处，则从q两个位|vQ指针各走i步既能在环内盔R?/p>
于是可设|两个指针，一个在N处，一个在i处，步长?Q第一ơ相遇的节点即ؓ环首的位|?/p>
6、如何判断两个链表是否交叉？如果扑ֈ交叉点？
思\?
]]>