メモリーの使われ方
vector内の各要素は連続、すなわちvector<T> cに対して&c[n] + 1 == &c[n+1]であることが保証されています。それ故vectorの容量を拡張する際に増加分を継ぎ足すことができません。おうちが手狭になっても増築は許されず、より大きなおうちを新築し／引っ越して／以前のおうちを解体するしかありません。その様子を観察しましょう。
まず領域拡張の度合を調べます。vectorのメンバ関数size()とcapacity()はそれぞれ"要素数"と"拡張なしに収容できる要素の個数"を返します。vector<int>に100個分の容量を確保した状態から要素を1つずつ挿入し、capacity()が変化した（拡張が行われた）ときのsize()とcapacity()とを出力してみます。
#include <iostream>
#include <vector>
using namespace std;
int main() {
{
cout << "\n----- vector<int> size & capacity" << endl;
vector<int> c;
c.reserve(100);
size_t cap = c.capacity();
for ( int i = 0; i < 1000; ++i ) {
if ( cap != c.capacity() ) {
cout << "size=" << c.size()
<< "\tcapacity=" << (cap = c.capacity())
<< "\tchange ratio=" << static_cast<double>(c.capacity()) / c.size()
<< endl;
}
c.emplace_back(i);
}
cout << "-----" << endl;
}
}
Visual C++ 12（Visual Studio 2013）のvectorはおおよそ5割増の領域拡張を行っています。そして要素数が100から1000になるまでに領域の確保／要素の移動／旧領域の解放を6回繰り返しています。なので最大要素数が想定できるのであれば、あらかじめreserve()しておけば少しは速くなりそうです。移動（コピー）がコスト高な要素を大量に挿入するような場合、かなり効果があるんじゃないかしら。
つぎにメモリーの利用効率、要素の格納に必要な領域の大きさを実測します。vectorに限らずSTLコンテナはメモリーの確保／解放を司る部分を外付けにできますから、これを利用して確保／解放のたびにどれだけ取ったか／返したかを出力しましょう。
#ifndef MALLOCATOR_H__
#define MALLOCATOR_H__
#include <cstdio>
#include <cstdlib>
#include <new>
#include <map>
#include <typeinfo>
namespace epi {
template<typename T> struct mallocator {
typedef T value_type;
template<typename U> mallocator(const mallocator<U>&) {}
mallocator() {}
bool operator==(const mallocator&) const{ return true; }
bool operator!=(const mallocator&) const{ return false; }
T* allocate(const size_t n) const {
if ( n == 0 )
return nullptr;
if (n > static_cast<size_t>(-1) / sizeof(T) )
throw std::bad_array_new_length();
size_t siz = n * sizeof(T);
void* pv = std::malloc(siz);
if ( !pv )
throw std::bad_alloc();
usage_[pv] = siz;
printf("%3d %s (%4dB) MALLOC : %p (%d)\n", n, typeid(T).name(), siz, pv, in_use());
return static_cast<T*>(pv);
}
void deallocate(T* const p, size_t n) const {
usage_.erase(p);
printf("%3d %s (%4dB) FREE : %p (%d)\n", n, typeid(T).name(), sizeof(T)*n, p, in_use());
std::free(p);
}
void construct(T* p, const T& val) { new ((void*)p) T(val); }
void destroy(T* p) { p->T::~T(); }
template<typename Other> struct rebind {
typedef mallocator<Other> other;
};
static std::map<void*,size_t> usage_;
static size_t in_use() {
size_t result = 0;
for ( auto item : usage_ ) {
result += item.second;
}
return result;
}
};
template<typename T> std::map<void*,size_t> mallocator<T>::usage_;
}
#endif
vectorとlistでメモリーの使いっぷりを観察した結果がコチラ。
#include <iostream>
#include <vector>
#include <list>
#include "mallocator.h"
using namespace std;
template<typename T> using my_vec = std::vector<T, epi::mallocator<T>>;
template<typename T> using my_list = std::list<T, epi::mallocator<T>>;
int main() {
{
cout << "\n----- vector<int>" << endl;
my_vec<int> c;
for ( int i = 0; i < 10; ++i ) {
c.push_back(i);
}
cout << "-----" << endl;
}
{
cout << "\n----- list<int>" << endl;
my_list<int> c;
for ( int i = 0; i < 10; ++i ) {
c.push_back(i);
}
cout << "-----" << endl;
}
}
vector<int> での結果から、前述の新築と解体の様子が見てとれます。新旧領域間での要素の移動の間、新旧2つの領域が存在するため、一時的に全要素が必要とする領域のおよそ2.5倍が確保されていますが、定常的には要素1つ分の大きさ×要素数×（1～1.5）、おおむね最小限のメモリー量でやりくりしてくれてます。
対してlist<int>では要素の型つまりintではなく、std::_List_node<int,void*>が各要素の格納のために確保されています。この_List_node<>の正体をヘッダ<list>に見つけました。
template<class _Value_type>
struct _List_node<_Value_type,void*> {
typedef _List_node<_Value_type,void*>* _Nodeptr;
_Nodeptr _Next;
_Nodeptr _Prev;
_Value_type _Myval;
private:
_List_node& operator=(cosnt _List_node&);
};
要素1つを格納するのに、その大きさに加えてポインタ2つ分大きい領域を消費します。listは双方向のリンク・リストなので直前と直後の要素をたどるため2つのポインタが必要なんですね。なので要素が小さいほどメモリ効率は相対的に悪くなります。このサンプルは32bitアプリとしてコンパイルしていますけど、64bitだとポインタが大きくなって要素1つあたり16byte余計に必要ってことになります。
