回答編集履歴
2
追記2
test
CHANGED
|
@@ -109,3 +109,155 @@
|
|
|
109
109
|
|
|
110
110
|
|
|
111
111
|
参考: [ロジック](http://blog.livedoor.jp/crackstars/archives/992541.html)
|
|
112
|
+
|
|
113
|
+
|
|
114
|
+
|
|
115
|
+
---
|
|
116
|
+
|
|
117
|
+
|
|
118
|
+
|
|
119
|
+
[追記2]
|
|
120
|
+
|
|
121
|
+
|
|
122
|
+
|
|
123
|
+
念のため一応書いておきます。
|
|
124
|
+
|
|
125
|
+
|
|
126
|
+
|
|
127
|
+
**あくまで趣味の範囲でやっているので**正しくない部分があるかもしれませんが、まあ、私なりのとらえ方として。
|
|
128
|
+
|
|
129
|
+
|
|
130
|
+
|
|
131
|
+
std::vectorは内部ではJavaやC#でいうnew, C++でいうnew/delete, Cでいうmalloc/free を用いて確保しているっぽいです。
|
|
132
|
+
|
|
133
|
+
|
|
134
|
+
|
|
135
|
+
```C++
|
|
136
|
+
|
|
137
|
+
// あくまでイメージ。
|
|
138
|
+
|
|
139
|
+
// 実際には template っていう機能?を使って実装しているようだけど、
|
|
140
|
+
|
|
141
|
+
// 例だし、面倒なので省略。ここではint型用としてやっています。
|
|
142
|
+
|
|
143
|
+
class IntVector{
|
|
144
|
+
|
|
145
|
+
public:
|
|
146
|
+
|
|
147
|
+
IntVector( int size = 100 ){
|
|
148
|
+
|
|
149
|
+
v = new int[size];
|
|
150
|
+
|
|
151
|
+
}
|
|
152
|
+
|
|
153
|
+
~IntVector(){ delete v[]; }
|
|
154
|
+
|
|
155
|
+
// ほかにもメンバがあるとして
|
|
156
|
+
|
|
157
|
+
private:
|
|
158
|
+
|
|
159
|
+
int *v;
|
|
160
|
+
|
|
161
|
+
};
|
|
162
|
+
|
|
163
|
+
```
|
|
164
|
+
|
|
165
|
+
|
|
166
|
+
|
|
167
|
+
で、削除したいとする。現在の要素数は10 だとして、4番目のデータを削除したい場合、
|
|
168
|
+
|
|
169
|
+
|
|
170
|
+
|
|
171
|
+
```C++
|
|
172
|
+
|
|
173
|
+
// IntVector内だとして。
|
|
174
|
+
|
|
175
|
+
// また、iteratorを このIntVectorで使えるイテレータだとする
|
|
176
|
+
|
|
177
|
+
iterator remove( int pos ){
|
|
178
|
+
|
|
179
|
+
// 一旦、別容器を用意
|
|
180
|
+
|
|
181
|
+
// 現在のint *v の -1 (つまり要素数を一戸減らす)して生成
|
|
182
|
+
|
|
183
|
+
int s = size() - 1;
|
|
184
|
+
|
|
185
|
+
int *temp = new int[ s ];
|
|
186
|
+
|
|
187
|
+
|
|
188
|
+
|
|
189
|
+
// ここでv -> temp する。ただし、vのpos番目はスキップする
|
|
190
|
+
|
|
191
|
+
|
|
192
|
+
|
|
193
|
+
// ここでvをいったんdeleteするか上書きかわからんが、
|
|
194
|
+
|
|
195
|
+
// とにかくvを空だと想定する
|
|
196
|
+
|
|
197
|
+
|
|
198
|
+
|
|
199
|
+
// 再度vを容量確保する
|
|
200
|
+
|
|
201
|
+
v = new int[s];
|
|
202
|
+
|
|
203
|
+
|
|
204
|
+
|
|
205
|
+
// tempの内容物をvにコピー
|
|
206
|
+
|
|
207
|
+
|
|
208
|
+
|
|
209
|
+
return /* ここでIntVectorのiteratorを返す */;
|
|
210
|
+
|
|
211
|
+
}
|
|
212
|
+
|
|
213
|
+
```
|
|
214
|
+
|
|
215
|
+
|
|
216
|
+
|
|
217
|
+
のようになっていると思う。
|
|
218
|
+
|
|
219
|
+
|
|
220
|
+
|
|
221
|
+
もちろん、この例はtemplateじゃなくてintに固定しているし、ところどころ違いますが、
|
|
222
|
+
|
|
223
|
+
「別容器を用意してそれにいったん移し替えて、サイズ変更して...」的な処理をしていることは
|
|
224
|
+
|
|
225
|
+
同じだと思う。
|
|
226
|
+
|
|
227
|
+
|
|
228
|
+
|
|
229
|
+
現在のPCだと気にならない速度だと思いますが、なるべくしょーもない時間取りは省きたいですよね?
|
|
230
|
+
|
|
231
|
+
|
|
232
|
+
|
|
233
|
+
std::listならパーツを取り換えるだけで済むのでstd::vectorよりは早い。
|
|
234
|
+
|
|
235
|
+
( これは D.A に載っている内容なので省きます。 )
|
|
236
|
+
|
|
237
|
+
|
|
238
|
+
|
|
239
|
+
ただし、リスト構造はエリア(厳密にはメモリアドレス)が飛び飛びなので
|
|
240
|
+
|
|
241
|
+
ランダムアクセスって呼ばれる、要素数を指定したアクセスとかが苦手です。
|
|
242
|
+
|
|
243
|
+
|
|
244
|
+
|
|
245
|
+
配列やstd::vectorだと arr[1] とかみたいにアクセスできるけど、
|
|
246
|
+
|
|
247
|
+
|
|
248
|
+
|
|
249
|
+
リスト構造は イテレータって呼ばれる、走査するためのやつを使うか、拡張forと呼ばれるやつとかで
|
|
250
|
+
|
|
251
|
+
最初から最後まで調べないといけない。( もちろん途中で抜けることはできるけど。 )
|
|
252
|
+
|
|
253
|
+
|
|
254
|
+
|
|
255
|
+
このメリット・デメリットを理解しているなら、
|
|
256
|
+
|
|
257
|
+
|
|
258
|
+
|
|
259
|
+
「フーム、今回はできるだけランダムアクセスできるようにしたいなぁ。追加や削除は...いらねぇなぁ。ってーことは...今回はstd::vectorでいいんじゃね?」
|
|
260
|
+
|
|
261
|
+
|
|
262
|
+
|
|
263
|
+
みたいに考えることができる。
|
1
例の修正
test
CHANGED
|
@@ -98,7 +98,9 @@
|
|
|
98
98
|
|
|
99
99
|
|
|
100
100
|
|
|
101
|
-
算数・数学だと「教科書読みました。でも公式? 知りません。」っていうレベルです。
|
|
101
|
+
算数・数学だと~~「教科書読みました。でも公式? 知りません。」っていうレベルです。~~
|
|
102
|
+
|
|
103
|
+
swordoneのお言葉をお借りして言うと、「教科書読みました。でもいつ公式を使うかわかりません。」っていうレベルです。
|
|
102
104
|
|
|
103
105
|
|
|
104
106
|
|