A simple heterogeneous container in C++ without relying on 'variant' nor 'any'
Building an heterogeneous container: basic ingredients
In a precedent post, I outlined the implementation of an heterogeneous dynamic array. Let us try now to reflect on what was done to draw some genericity out of it.
The basic ingredients to build an heterogeneous container are:
data the objectptr where the object is stored: a pointer or offset allowing to find the object in memorytag what is the type of that object: a unique way to identify types at runtime.dtor how to destroy the object: to avoid memory leaks- (how to copy the object)
Numerous implementations can be obtained by combining these components together in various ways. For example, std::any is basically a structure containing tag, ptr, and dtor together. As such std::any is self-contained and can be put into a vector without worries. While it is ideal for passing a single item around, having a collection of them is not so great.
In the implementation of an heterogeneous dynamic array here, dtor is separated from the ptr, data is held among others into a std::vector<std::bytes>. The main data structure is the map associating the tag to ptr and the major part of the look-up cost is there. In a shortened format, this gives:
1
2
3
| std::vector<std::byte> data;
std::unordered_map<tag,ptr> type_to_offset;
std::unordered_map<tag,dtor> type_to_destructor;
|
The implementation only accepts a single instance of each type within, which allows the user to find an object without necessitating a previously acquired handle. With a single instance per type, the user can either store an handle for direct access or obtain content by the type of the object. In the case of multiple instances of a type per container, the user must store and share an index, returned upon insertion, in order to be able to retrieve the right instance later.
By imposing data locality of the objects in order to have an heterogeneous array, it was not the simplest implementation ever due to shenanigans in memory allocation.
A simpler heterogeneous container
Let us outline the implementation of a really simple heterogeneous container. Specifically, I will not make use of std::any, because it has poor performance (left for another post 😉), and tag will not be stored along ptr and dtor. Since the container is meant to be extensible at runtime, std::variant is out of question.
It is still quite common to see pointers passed around as void* argument, especially to pass user-defined content to some interface based or closely related to C. This is basically a way of passing type-erased objects around. I was tempted at first to make a homemade structure slapping void-ized ptr and dtor together… but then I learnt that std::unique_ptr could take a void template argument 😲. So, considering this and the fact that it can take a custom deleter function: a type-erased object can be stored readily in a std::unique_ptr<void,void(*)(void*)>.
Consequently, it is possible to simply store heterogeneous content within:
1
2
| using ptr_dtor = std::unique_ptr<void,void(*)(void*)>;
std::unordered_map<tag,ptr_dtor> type_to_object;
|
The necessary to insert and retrieve object is only a matter of wrapping the manipulation of the map. As for the tag for the type, a simple type counter based on static variables as in the previous post will do. As an alternative, std::type_index could be used instead to avoid the extra fluff of the type counter. The implementation is can be played around on compiler explorer and pasted at the bottom for completeness.
The pros of this data structure are simplicity and pointer stability. The user does not have to repeatedly access the container itself since it can store directly the pointers to objects of interest (assuming the lifetime of the container and its content is well specified). Moreover, destruction is guaranteed by the unique_ptr. The cons is that objects are stored wherever in memory by the system, and it cannot be copyable. Finally, some fine-tune optimizations cannot be done by relying on unique_ptr, such as destructor elision for trivially destructible type.
Code
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
| // MIT License
//
// Copyright(c) 2020 Fabien Péan
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this softwareand associated documentation files(the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and /or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions :
//
// The above copyright noticeand this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
#include <cstddef> // for size_t
#include <cstdint> // for std::uint32_t
#include <memory> // for unique_ptr
#include <tuple> // for forward_as_tuple
#include <type_traits> // for remove_reference_t, remove_cv_t
#include <unordered_map> // for unordered_map
#include <utility> // for forward
namespace heco
{
template<typename T>
using rm_cvref_t = std::remove_cv_t<std::remove_reference_t<T>>;//remove_cvref_t from C++20 only
using type_id_t = std::uint32_t;
class TypeCounter {
static inline type_id_t i = 0;
public:
template<typename T>
static inline const auto id = i++;
};
template<typename T> inline auto type_id() { return TypeCounter::id<rm_cvref_t<T>>; }
struct HeterogeneousContainer
{
HeterogeneousContainer() = default;
HeterogeneousContainer(const HeterogeneousContainer&) = delete;
HeterogeneousContainer& operator=(const HeterogeneousContainer&) = delete;
HeterogeneousContainer(HeterogeneousContainer&&) = default;
HeterogeneousContainer& operator=(HeterogeneousContainer&&) = default;
~HeterogeneousContainer() = default;
std::unordered_map<type_id_t, std::unique_ptr<void, void(*)(void*)>> data;
template<typename... Ts>
bool contains() const noexcept { return (data.count(type_id<Ts>()) && ...);}
template<typename...Ts>
void reserve() { reserve(sizeof...(Ts)); }
void reserve(std::size_t n) { data.reserve(n); }
template<typename T, typename... Rest>
auto get() noexcept -> decltype(auto)
{
using U = std::remove_reference_t<T>;
if constexpr (sizeof...(Rest) == 0)
return *static_cast<U*>(data.at(type_id<U>()).get());
else
return std::forward_as_tuple(get<T>(), get<Rest>()...);
}
template<typename T, typename... Rest>
auto get() const noexcept -> decltype(auto)
{
using U = std::remove_reference_t<T>;
if constexpr (sizeof...(Rest) == 0)
return *static_cast<U*>(data.at(type_id<U>()).get());
else
return std::forward_as_tuple(get<T>(), get<Rest>()...);
}
template<typename T = void, typename... Args>
auto insert(Args&& ... args) -> decltype(auto)
{
if constexpr (std::is_same_v<T, void>)
static_assert(((copyable_if_lvalue<Args> || moveable_if_rvalue<Args>) && ...), "Use in-place construction version insert<T>(Args...) instead.");
if constexpr (!std::is_same_v<T, void>)
return insert_1<T>(std::forward<Args>(args)...);
else if constexpr (sizeof...(Args) == 1)
return insert_1<Args...>(std::forward<Args>(args)...);
else
return insert_n(std::forward<Args>(args)...);
}
template<typename T = void, typename... Args>
auto insert_or_assign(Args&& ... args) -> decltype(auto)
{
if constexpr (!std::is_same_v<T, void>)
return insert_or_assign_1<T>(std::forward<Args>(args)...);
else if constexpr (sizeof...(Args) == 1)
return insert_or_assign_1<Args...>(std::forward<Args>(args)...);
else
return std::forward_as_tuple(insert_or_assign_1<Args>(std::forward<Args>(args))...);
}
private:
template<typename T>
static constexpr bool copyable_if_lvalue = std::is_lvalue_reference_v<T> && std::is_copy_constructible_v<T>;
template<typename T>
static constexpr bool moveable_if_rvalue = (std::is_object_v<T> || std::is_rvalue_reference_v<T>) && std::is_move_constructible_v<T>;
template<typename T, typename... Args>
auto insert_1(Args&&... args) -> decltype(auto)
{
using U = rm_cvref_t<T>;
auto&&[it, in] = data.emplace(
type_id<T>(),
std::unique_ptr<void, void (*)(void*)>{ new U{ std::forward<Args>(args)... },
+[](void* instance) { delete static_cast<U*>(instance); } });
return *static_cast<U*>(it->second.get());
}
template<typename... Ts>
auto insert_n(Ts&&... values) -> decltype(auto)
{
data.reserve(data.size() + sizeof...(Ts));
return std::forward_as_tuple(insert_1<Ts>(std::forward<Ts>(values))...);
}
template<typename T, typename... Args>
auto insert_or_assign_1(Args&& ... args) -> decltype(auto)
{
using U = rm_cvref_t<T>;
auto&&[it,in] = data.insert_or_assign(
type_id<T>(),
std::unique_ptr<void, void(*)(void*)>{ new U{ std::forward<Args>(args)... },
+[](void* instance) { delete static_cast<U*>(instance); } }
);
return *static_cast<U*>(it->second.get());
}
};
}
|