Question

C++模板 实现 vector和list比较

比如有
vector<int> vi;
vector<string> vs;
list<int> li;
list<string>ls;
现在我要写一个函数模板,如来实现对上面四个不同类型的容器以及他们所容纳的不同类型的数据进行操作。
如
insert_element(vi, 5000) //输入5000个vector 整数

insert_element(vs,5000)／／输入5000个vector 字符串
insert_element(li,5000)//输入5000个 list 整数
insert_element(ls,5000)／／输入5000个list 字符串

这个用模板如何实现呢？
我尝试了：
template<typename C, typename X, typename T>

void insert_element(C<X>& container, const T n)// 希望编译器推断出 C=vector 或list， X＝int 或string
可是不行啊，总说我这样声明不正确

Answer 1

vector就是动态数组.它也是在堆中分配内 存,元素连续存放,有保留内存,如果减少大小后内存也不会释放.如果新值>当前大小时才会再分配内存.对最后元素操作最快(在后面添加删除 最快 ), 此时一般不需要移动内存,只有保留内存不够时才需要.对中间和开始处进行添加删除元素操作需要移动内存,如果你的元素是结构或是类,那么移动的同时还会进行构造和析构操作，所以性能不高（最好将结构或类的指针放入vector中，而不是结构或类本身，这样可以避免移动时的构造与析构)。访问方面,对任何元素的访问都是O(1),也就是是常数的,所以vector常用来保存需要经常进行随机访问的内容,并且不需要经常对中间元素进行添加删除操作.
总之：需要经常随机访问请用vector

list就是链表,元素也是在堆中存放,每个元素都是放在一块内存中.list没有空间预留习惯,所以每分配一个元素都会从内存中分配,每删除一个元素都 会释放它占用的内存,这与上面不同,可要看好了
list在哪里添加删除元素性能都很高,不需要移动内存,当然也不需要对每个元素都进行构 造与析构了,所以常用来做随机操作容器.但是访问list里面的元素时就开始和最后访问最快访问其它元素都是O(n) ,所以如果需要经常随机访问的话,还是使用其它的好

总之：经常添加删除大对象的话,那么请使用list

Answer 2

编译器推导不出来的原因是因为，vector与list的实际的实现的容器并不只有一个模块参数的，而是至少有两个，只不过有默认值，你并时用的时候只提供一个而已。但在这种模板实现里，默认参数是会被忽略的，所以你需要重新指定了。明白了吧？
同时，最好不要这样使用STL容器，要写插入方法，最好还是用Iterator来做，提供一个带begin的参数不是很好么。参考 back_inserter 之类的模板。

追问

怎么改成iterator啊，我刚开始学这个。能给我点提示吗。能不能给我写个template的声明啊

追答

STL标准算法里面这样的例子很多的，比如下面这个copy算法的的例子
template
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
{
while (first!=last) {
*result = *first;
++result; ++first;
}
return result;
}

Answer 3

// implementation by container_type::push_back

template<typename C, typename T>
void insert_element(C& inst_int, const T& n);
template<template<class, class> typename C)
void contint_insert (const C<int, std::allocator<int> >& cint, const int);

void f(std::vector<double>& v, std::deque<int>& ls, const std::string& s)
{
insert_element(v, 100.0);
insert_element(ls, 700);
contint_insert(ls, 900);
contint_insert(s, 'd');
/* error, std::string=std::basic_string<char, std::char_traits<char>, std::allocator<char> >
C=std::basic_string, 函数第一个参数要求是两个类型参数的模板类型C的实例对象，且第一个模板类型参数为int，而std::string的std::basic_string的第一个类型参数是char且是一个三个类型参数的模板。*/
contint_insert(v, 70.0);
/* C=std::vector， std::vector<double, std::allocator<double>与std::vector<int, std::allocator<int>，类型参数不同 */

}

记住std::vector<int>、std::vector<double>、std::string、std::list<std::string>是一个类型

http://zhidao.baidu.com/question/412950067?&oldq=1
http://zhidao.baidu.com/question/423146796?&oldq=1
http://zhidao.baidu.com/question/452957474?&oldq=1