分类： C/C++
2015-08-14 08:57:33
原文地址：程序员面试宝典 第9章 STL模板与容器 作者：developinglife
（1）向量元素的浅拷贝，向量的释放
class CDemo
{
public:
CDemo():str(NULL){};
~CDemo()
{
if(str)
{
//static int i=0;
//cout<<"&CDemo"<
}
}
char *str;
};
int main()
{
CDemo d1;
d1.str = new char[32];
strcpy(d1.str, "trend micro");
vector
a1->push_back(d1);
delete a1;
return 0;
}
上面的程序错在哪？
上面程序会重复delete掉str所指向的内存两次，导致崩溃。
a1->push_back(d1);会调用CDemo的默认拷贝函数，这是浅拷贝，拷贝对象的str仍指向原对象的str。
Delete a1; 释放vector对象，此时vector里面的元素d1的拷贝也会被释放。由于d1是局部变量，main函数退出时会释放d1。但d1的拷贝对象和d1对象的str都指向同一片内存，被释放两次，导致错误。
Solution：
为CDemo添加拷贝构造函数，进行深拷贝：
CDemo(const CDemo &cd)
{
this->str = new char[strlen(cd.str)+1];
strcpy(str, cd.str);
}
（2）迭代器，erase
vector
array.push_back(1);
array.push_back(6);
array.push_back(6);
array.push_back(3);
vector
vector
itor= array.begin();
//删除数组中所有的6
for(itor=array.begin(); itor!=array.end(); )
{
if(6==*itor)
{
itor2 = itor;
array.erase(itor2);
}
itor++;
}
printVec(array);
上面程序只能删除一个6. Itor=itor2;说明这两个迭代器是一样的，当array.erase(itor2);时，itor已经指向下一个6了，在itor++,则itor指向3，略过了第二个6.
可这样删除：
array.erase( remove(array.begin(), array.end(), 6), array.end() );
9.2 模板（1）函数指针和模板都可以提高程序的可扩展性，便于重复利用：
int judge(int x, int y)
{
if(x >=0 )
return x;
else if( y = 0 )
return x;
else
return x/y;
}
int sub(int x, int y)
{
return x - y;
}
void test(int (*p)(int, int), int a, int b)
{
int i = (*p)(a, b);
cout<
}
template
class Operate
{
public:
static T add(T a, T b)
{
return a+b;
}
static T mul(T a, T b)
{
return a*b;
}
};
int main()
{
int A = 1,
B = 2;
test(sub, A, B);
test(judge, A, B);
cout<
cout<
return 0;
}
（2）STL的容器及其描述
|
数据结构 |
描述 |
头文件 |
|
Vector向量 |
连续存储的元素 |
|
|
List列表 |
有节点组成的双向链表 |
|
|
Deque双队列 |
连续存储的指向不同元素的指针组成的数组 |
|
|
Set集合 |
节点组成的红黑树，每个节点包含一个元素，节点之间按某种方式排列，所有元素的次序都不同 |
|
|
Multiset多重集合 |
集合中的元素的次序可以相同 |
|
|
Stack栈 |
后进先出的排列 |
|
|
Queue队列 |
先进先出的排列 |
|
|
Priority_queue优先队列 |
队列，元素的次序按照值的某种次序排列 |
|
|
Map映射 |
{key,value} 键对按某种方式排列 |
|
（2）试用多态实现线性列表（队列、串、堆栈），要求具备线性表的基本操作：插入、删除、测长等。
A:
template
struct tcontainer
{
virtual void push(const T&) = 0;
virtual void pop() = 0;
virtual const T& begin() = 0;
virtual const T& end() = 0;
virtual size_t size() = 0;
};
template
struct tvector: public tcontainer
{
//static const size_t _step = 100;//error!
size_t _step;
tvector()
{
_step = 100;
_size = 0; //初始化向量实际大小为0
_cap = _step;//向量初始空间为100
buf = 0; //首地址，需动态分配内存
re_capcity(_cap);
}
~tvector()
{
if(buf)
free(buf);
}
void re_capcity(size_t s)
{
if(!buf)
buf = (T*)malloc(sizeof(T) * s);
else
buf = (T*)realloc(buf, sizeof(T) * s);
}
virtual void push(const T& v)
{
if(_size >= _cap)
re_capcity(_cap + _step);
buf[_size++] = v;
}
virtual void pop()
{
if(_size)
_size--;
}
virtual const T& begin()
{
return buf[0];
}
virtual const T& end()
{
if(_size)
return buf[_size-1];
else
exit(-1);
}
virtual size_t size()
{
return _size;
}
const T& operator[] (size_t i)
{
if(i>=0 && i<_size)
return buf[i];
else
exit(-1);
}
private:
size_t _size;
size_t _cap;
T *buf;
};
int main()
{
tvector
for(int i=0; i<100; i++)
vec.push(i);
for(int j=0; j<10; j++)
vec.pop();
for(int k=0; k
cout<
cout<
return 0;
}
