Skip to content

Instantly share code, notes, and snippets.

@Gpinchon
Last active December 6, 2022 21:49
Show Gist options
  • Save Gpinchon/19dd224d5e7fc92596e01f5df6508e2a to your computer and use it in GitHub Desktop.
Save Gpinchon/19dd224d5e7fc92596e01f5df6508e2a to your computer and use it in GitHub Desktop.
Yet another sparse set implementation
project(SparseSet LANGUAGES CXX)
set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_FLAGS_RELEASE "-Ox")
set(SPARSE_SET_TEST_SRC
${CMAKE_CURRENT_SOURCE_DIR}/main.cpp)
add_library(SparseSet INTERFACE ${CMAKE_CURRENT_SOURCE_DIR}/sparse_set.hpp)
add_executable(Test ${SPARSE_SET_TEST_SRC})
target_include_directories(Test PUBLIC ${CMAKE_CURRENT_SOURCE_DIR})
target_link_libraries(Test SparseSet)
#include <sparse_set.hpp>
#include <cassert>
struct Transform {
std::array<float, 3> position{ 0, 0, 0 };
};
int main()
{
auto sparseSet = new sparse_set<Transform, 65536>;
for (auto i = 0u; i < sparseSet->max_size(); ++i) {
sparseSet->insert(i).position[0] = i;
}
for (auto i = 0u; i < sparseSet->size(); ++i) {
assert(sparseSet->at(i).position[0] == i);
}
for (auto i = 0u; i < sparseSet->max_size(); ++i) {
if (i % 3) sparseSet->erase(i);
}
for (auto i = 0u; i < sparseSet->max_size(); ++i) {
if (i % 3) assert(!sparseSet->contains(i));
else assert(sparseSet->contains(i));
}
delete sparseSet;
}
#pragma once
////////////////////////////////////////////////////////////////////////////////
// Includes
////////////////////////////////////////////////////////////////////////////////
#include <cstring>
#include <cstdint>
#include <array>
#include <memory>
#include <type_traits>
////////////////////////////////////////////////////////////////////////////////
// Class declarations
////////////////////////////////////////////////////////////////////////////////
/**
* @brief sizeof(sparse_set) is at least sizeof(Type) * Size. Large sets should
* therefore be allocated on the heap.
* Every time an element is erased invalidates every object reference to elements
* in this set.
* In general it is ill-advised to keep reference to objects inside the set.
* Users should instead reference the set and access elements through index when
* they need it.
*/
template<typename Type, uint32_t Size>
class sparse_set {
public:
using value_type = Type;
using size_type = decltype(Size);
constexpr sparse_set() noexcept;
inline ~sparse_set() noexcept(std::is_nothrow_invocable_v<decltype(&sparse_set::clear), sparse_set>);
/** @return The maximum number of elements that can be inserted in the set*/
[[nodiscard]] constexpr size_type max_size() const noexcept;
/** @return The number of elements contained in the set */
[[nodiscard]] constexpr size_type size() const noexcept;
/** @return true if the set contains no element */
[[nodiscard]] constexpr bool empty() const noexcept;
/** @return true if the number of elements in the set equals max_size() */
[[nodiscard]] constexpr bool full() const noexcept;
/** @brief empties the set */
constexpr void clear()
noexcept(std::is_nothrow_invocable_v<decltype(&sparse_set::erase), sparse_set, size_type>);
/** @return a ref to the element contained at this index */
[[nodiscard]] constexpr value_type& at(size_type a_Index);
/** @return a ref to the element contained at this index */
[[nodiscard]] constexpr const value_type& at(size_type a_Index) const;
/** @return *UNCHECKED* a ref to the element contained at this index */
[[nodiscard]] constexpr value_type& operator[](size_type a_Index) noexcept;
/** @return *UNCHECKED* a ref to the element contained at this index */
[[nodiscard]] constexpr const value_type& operator[](size_type a_Index) const noexcept;
/**
* @brief Inserts a new element at the specified index,
* replaces the current element if it already exists
* @return a ref to the newly created element
*/
template<typename ...Args>
constexpr value_type& insert(size_type a_Index, Args&&... a_Args)
noexcept(std::is_nothrow_constructible_v<value_type, Args...> && std::is_nothrow_destructible_v<value_type>);
/** @brief Removes the element at the specified index */
constexpr void erase(size_type a_Index)
noexcept(std::is_nothrow_destructible_v<value_type>);
/** @return true if a value is attached to this index */
constexpr bool contains(size_type a_Index) const;
private:
#pragma warning(push)
#pragma warning(disable : 26495) //variables are left uninitialized on purpose
struct storage {
size_type sparseIndex;
alignas(value_type) std::byte data[sizeof(value_type)];
operator value_type& () { return *(value_type*)data; }
};
#pragma warning(pop)
size_type _size{ 0 };
std::array<size_type, Size> _sparse;
std::array<storage, Size> _dense;
};
template<typename Type, uint32_t Size>
constexpr sparse_set<Type, Size>::sparse_set() noexcept {
_sparse.fill(max_size());
}
template<typename Type, uint32_t Size>
inline sparse_set<Type, Size>::~sparse_set()
noexcept(std::is_nothrow_invocable_v<decltype(&sparse_set::clear), sparse_set>)
{
clear();
}
template<typename Type, uint32_t Size>
constexpr auto sparse_set<Type, Size>::max_size() const noexcept -> size_type {
return Size;
}
template<typename Type, uint32_t Size>
constexpr auto sparse_set<Type, Size>::size() const noexcept -> size_type {
return _size;
}
template<typename Type, uint32_t Size>
constexpr bool sparse_set<Type, Size>::empty() const noexcept {
return _size == 0;
}
template<typename Type, uint32_t Size>
constexpr bool sparse_set<Type, Size>::full() const noexcept {
return _size == max_size();
}
template<typename Type, uint32_t Size>
constexpr void sparse_set<Type, Size>::clear()
noexcept(std::is_nothrow_invocable_v<decltype(&sparse_set::erase), sparse_set, size_type>)
{
for (size_type index = 0; !empty(); ++index) {
erase(index);
}
}
template<typename Type, uint32_t Size>
constexpr auto sparse_set<Type, Size>::at(size_type a_Index) -> value_type& {
//if a_Index out of bound or element empty, we should crash
return _dense.at(_sparse.at(a_Index));
}
template<typename Type, uint32_t Size>
constexpr auto sparse_set<Type, Size>::at(size_type a_Index) const -> const value_type& {
return _dense.at(_sparse.at(a_Index));
}
template<typename Type, uint32_t Size>
constexpr auto sparse_set<Type, Size>::operator[](size_type a_Index) noexcept -> value_type& {
return _dense[_sparse[a_Index]];
}
template<typename Type, uint32_t Size>
constexpr auto sparse_set<Type, Size>::operator[](size_type a_Index) const noexcept -> const value_type& {
return _dense[_sparse[a_Index]];
}
template<typename Type, uint32_t Size>
template<typename ...Args>
constexpr auto sparse_set<Type, Size>::insert(size_type a_Index, Args && ...a_Args)
noexcept(std::is_nothrow_constructible_v<value_type, Args...> && std::is_nothrow_destructible_v<value_type>) -> value_type&
{
if (contains(a_Index)) //just replace the element
{
auto& dense = _dense[_sparse[a_Index]];
std::destroy_at((value_type*)dense.data);
return *new(dense.data) value_type(std::forward<Args>(a_Args)...);
}
//push new element back
_sparse[a_Index] = _size;
auto& dense = _dense.at(_size); //if full it should crash here
dense.sparseIndex = a_Index;
_size++;
return *new(dense.data) value_type(std::forward<Args>(a_Args)...);
}
template<typename Type, uint32_t Size>
constexpr void sparse_set<Type, Size>::erase(size_type a_Index)
noexcept(std::is_nothrow_destructible_v<value_type>)
{
if (empty() || !contains(a_Index)) return;
_size--;
auto& currDense = _dense[_sparse[a_Index]];
auto& lastDense = _dense[_size];
size_type lastIndex = lastDense.sparseIndex;
std::destroy_at((value_type*)currDense.data); //call current data's destructor
std::memmove(currDense.data, lastDense.data, sizeof(value_type)); //crush current data with last data
std::swap(lastDense.sparseIndex, currDense.sparseIndex);
std::swap(_sparse[lastIndex], _sparse[a_Index]);
_sparse[a_Index] = max_size();
}
template<typename Type, uint32_t Size>
constexpr bool sparse_set<Type, Size>::contains(size_type a_Index) const {
//if a_Index is out of bound we should crash here
return _sparse.at(a_Index) != max_size();
}
@Gpinchon
Copy link
Author

Gpinchon commented Dec 4, 2022

I got inspired by this blog post and implemented a fixed-size sparse set, removing the need for vectors, because everything is allocated on the sparse set creation, you should allocate on the heap when using a large set.

@Gpinchon
Copy link
Author

Gpinchon commented Dec 4, 2022

Added some test code and an example CMakeLists.txt

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment