1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
/*************************************************************************
*
* HTCd - Copyright (C) 1998-2006 Henrik Rydberg
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
#ifndef MVECH
#define MVECH
#include <malloc.h>
#include <string.h>
#include <new>
const int mv_mincaps=16;
template <class T> class mrvec {
public:
typedef T* iterator;
typedef const T* const_iterator;
mrvec():
map((T*)malloc(mv_mincaps*sizeof(T))),dim(0),caps(mv_mincaps) {}
mrvec(int n):
map((T*)malloc(mv_mincaps*sizeof(T))),dim(0),caps(mv_mincaps) { resize(n); }
~mrvec() { free(map); }
int size() const { return dim; }
int capacity() const { return caps; }
bool empty() const { return dim==0; }
bool nempty() const { return dim!=0; }
T& at(int pos) { return map[pos]; }
const T& at(int pos) const { return map[pos]; }
T& operator[](int pos) { return map[pos]; }
const T& operator[](int pos) const { return map[pos]; }
iterator begin() { return map; }
const_iterator begin() const { return map; }
iterator end() { return map+dim; }
const_iterator end() const { return map+dim; }
T& front() { return map[0]; }
const T& front() const { return map[0]; }
T& back() { return map[dim?dim-1:0]; }
const T& back() const { return map[dim?dim-1:0]; }
////////////////////////////////////////////////////////////////
void clear() { dim=0; }
iterator insert(iterator it,const T& s) {
int pos=it-map; ins(pos,1); return &(map[pos]=s);
}
void insert(iterator it,int n,const T& s) {
int pos=it-map; ins(pos,n); while(n--) map[pos++]=s;
}
void insert(iterator it,const_iterator p,const_iterator e) {
int pos=it-map; ins(pos,e-p); while(p<e) map[pos++]=*p++;
}
iterator erase(iterator it) {
int pos=it-map; ins(pos+1,-1); return map+pos;
}
////////////////////////////////////////////////////////////////
void reserve(int n) {
if(caps<n) { while(caps<n) caps<<=1; map=(T*)realloc(map,caps*sizeof(T)); }
}
void resize(int n) { reserve(n); dim=n; }
void push_back(const T& s) { reserve(dim+1); map[dim++]=s; }
void pop_back(const T& s) { if(dim) --dim; }
////////////////////////////////////////////////////////////////
protected:
mrvec(const mrvec&) {}
void operator=(const mrvec&) {}
void ins(int pos,int n) {
if(n) { reserve(dim+n); memmove(map+pos+n,map+pos,(dim-pos)*sizeof(T)); dim+=n; }
}
T* map;
int dim,caps;
};
template <class T> class msvec : public mrvec<T> {
public:
using mrvec<T>::map;
using mrvec<T>::dim;
typedef typename mrvec<T>::iterator iterator;
typedef typename mrvec<T>::const_iterator const_iterator;
msvec() : mrvec<T>() {}
msvec(int n) : mrvec<T>(n) { for(int i=0;i<dim;i++) new (map+i) T(); }
~msvec() { while(dim) map[--dim].~T(); }
////////////////////////////////////////////////////////////////
void clear() { while(dim) map[--dim].~T(); }
iterator insert(iterator it,const T& s) {
int pos=it-map; mrvec<T>::ins(pos,1); return new(map+pos) T(s);
}
void insert(iterator it,int n,const T& s) {
int pos=it-map; mrvec<T>::ins(pos,n); while(n--) new(map+pos++) T(s);
}
void insert(iterator it,const_iterator p,const_iterator e) {
int pos=it-map; mrvec<T>::ins(pos,e-p); while(p<e) new(map+pos++) T(*p++);
}
iterator erase(iterator it) {
it->~T(); int pos=it-map; mrvec<T>::ins(pos+1,-1); return map+pos;
}
void push_back(const T& s) { mrvec<T>::reserve(dim+1); new(map+dim++) T(s); }
void pop_back(const T& s) { if(dim) map[--dim].~T(); }
////////////////////////////////////////////////////////////////
void resize(int n) {
while(dim>n) map[--dim].~T();
mrvec<T>::reserve(n);
while(dim<n) new (map+dim++) T();
}
protected:
msvec(const msvec&) {}
void operator=(const msvec&) {}
};
#endif
|
