UOJ Logo kczno1的博客

博客

手写vector模板

2017-08-08 09:54:01 By kczno1

stl的vector太慢了

还是手写的好

upd: 有一件很神奇的事情,就是我第一次pb的时候会分配0的空间,似乎是不对的,但我已经用了多次且没有出锅。。。

但还是多分配一个空间好了


#include<bits/stdc++.h>
using namespace std;

template<typename T>
struct vec
{
T *a;
int n;
void clear()
{
   //if (n>0) {free(a);a=0;}
    n=0;
}
void pb(const T &x)
{
    if((n&-n)==n)//a=(T*)realloc(a,(n*2+1)*sizeof(T));
    {
        T *_a=new T [n*2+1];
        memcpy(_a,a,n*sizeof(T));
        a=_a;
    }
    a[n++]=x;
}
};
vec<int> a;
#define fore(arr) for(auto it=arr.a,end=it+arr.n;it!=end;++it)

int main()
{
     a.pb(1);
    fore(a) printf("%d\n",*it);
    a.clear();
    a.pb(2);
    fore(a) printf("%d\n",*it);
}

评论

immortalCO
如果把memcpy换成realloc不仅更短还更快 a=(T*)realloc(a,(n*2)*sizeof(T)); 这样就行了。 更快的原因是,如果a+n后面直接就有n的空间,那么就直接将这些空间分配给a,否则才拷贝。
xumingkuan
这个clear是要内存泄漏啊。。
OldDriverTree
我似乎也用这个卡过常数来着
OldDriverTree
就是那个假的可持久化启发式合并题

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。