Default Init Allocator

components/default_init_allocator.hpp · GitHub で見る

共通ページ

#include "lib/components/default_init_allocator.hpp"
#include <vector>

std::vector<int, DefaultInitAllocator<int>> a(100);
for (int i = 0; i < 100; ++i) a[i] = i;

操作	内容・返り値	計算量
DefaultInitAllocator<T>()	std::vector などに渡すアロケータを構築	\(O(1)\)
construct(p)	p の位置に要素をデフォルト初期化。通常はコンテナから呼ばれる	T のデフォルト構築 1 回
allocate(n) / deallocate(p,n)	std::allocator<T> と同じ領域確保／解放	メモリ確保・解放処理に依存

要素を値初期化せずデフォルト初期化します。整数などの要素は読み出す前に代入してください。

\(n\) 要素の初期化は自明な型なら \(O(1)\)、その他は \(O(n)\)、空間は \(O(n)\) です。メモリ確保のコストは除きます。

検証コード

• test/auxiliary_tree.test.cpp
• test/auxiliary_tree.test.cpp
• test/basic_substring_structure_substrings.test.cpp
• test/basic_substring_structure_substrings.test.cpp
• test/disjoint_sparse_table_affine.test.cpp
• test/disjoint_sparse_table_min.test.cpp
• test/dynamic_pattern_matching_array.test.cpp
• test/dynamic_pattern_matching_array.test.cpp
• test/lca_path_sum.test.cpp
• test/lca_path_sum.test.cpp
• test/lowest_common_ancestor.test.cpp
• test/lowest_common_ancestor.test.cpp
• test/permutation_tree.test.cpp
• test/permutation_tree.test.cpp
• test/range_chmin_chmax_add_sum.test.cpp
• test/run_enumerate.test.cpp
• test/sparse_table_min.test.cpp
• test/static_range_min.test.cpp
• test/static_range_min.test.cpp
• test/static_threshold_search.test.cpp
• test/static_threshold_search.test.cpp
• test/suffix_tree_array.test.cpp
• test/suffix_tree_array.test.cpp
• test/suffix_tree_substrings.test.cpp
• test/suffix_tree_substrings.test.cpp
• test/two_edge_connected_components.test.cpp

コード

#ifndef DEFAULT_INIT_ALLOCATOR_HPP
#define DEFAULT_INIT_ALLOCATOR_HPP

#include <memory>
#include <new>

template <class T>
struct DefaultInitAllocator : std::allocator<T> {
	template <class U>
	struct rebind {
		using other = DefaultInitAllocator<U>;
	};
	DefaultInitAllocator() = default;
	template <class U>
	DefaultInitAllocator(const DefaultInitAllocator<U> &) noexcept {}
	template <class U>
	void construct(U *p) { ::new (static_cast<void *>(p)) U; }
};

#endif

Back to top page