使用自定义分配器似乎是减少构建和释放std::set<...>
所需时间的一种方法。下面是一个完整的简单分配器演示,以及一个对结果时间进行分析的程序。
#include <algorithm>
#include <chrono>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <memory>
#include <set>
#include <vector>
template <typename T, std::size_t pool_size = 1024>
class pool_allocator
{
private:
std::vector<T*> d_pools;
T* d_next;
T* d_end;
public:
template <typename O>
struct rebind {
typedef pool_allocator<O, pool_size> other;
};
pool_allocator(): d_next(), d_end() {}
~pool_allocator() {
std::for_each(this->d_pools.rbegin(), this->d_pools.rend(),
[](T* memory){ operator delete(memory); });
}
typedef T value_type;
T* allocate(std::size_t n) {
if (std::size_t(this->d_end - this->d_next) < n) {
if (pool_size < n) {
this->d_pools.push_back(static_cast<T*>(operator new(sizeof(T) * n)));
return this->d_pools.back();
}
this->d_pools.push_back(static_cast<T*>(operator new(sizeof(T) * pool_size)));
this->d_next = this->d_pools.back();
this->d_end = this->d_next + pool_size;
}
T* rc(this->d_next);
this->d_next += n;
return rc;
}
void deallocate(T*, std::size_t) {
}
};
template <typename Allocator>
void time(char const* name, std::vector<int> const& random) {
std::cout << "running " << name << std::flush;
using namespace std::chrono;
high_resolution_clock::time_point start(high_resolution_clock::now());
std::size_t size(0);
{
std::set<int, std::less<int>, Allocator> values;
for (int value: random) {
values.insert(value);
}
size = values.size();
}
high_resolution_clock::time_point end(high_resolution_clock::now());
std::cout << ": size=" << size << " time="
<< duration_cast<milliseconds>(end - start).count() << "ms\n";
}
int main()
{
std::cout << "preparing..." << std::flush;
std::size_t count(10000000);
std::vector<int> random;
random.reserve(count);
std::generate_n(std::back_inserter(random), count, [](){ return std::rand(); });
std::cout << "done\n";
time<std::allocator<int>>("default allocator ", random);
time<pool_allocator<int, 32>>("custom allocator (32) ", random);
time<pool_allocator<int, 256>>("custom allocator (256) ", random);
time<pool_allocator<int, 1024>>("custom allocator (1024)", random);
time<pool_allocator<int, 2048>>("custom allocator (2048)", random);
time<pool_allocator<int, 4096>>("custom allocator (4096)", random);
time<std::allocator<int>>("default allocator ", random);
}