.. Copyright 2023 Julien Blanc Distributed under the Boost Software License, Version 1.0. https://www.boost.org/LICENSE_1_0.txt Comparison with other approaches ================================ ``indexed_array`` solves a common problem, for which solutions already exists. They, however, all have their different trade-offs, which lead me to the writing of this library. Using std c++20 range library (views) ------------------------------------- C++20 ``views`` are an elegant solution to the problem of indexing using arbitrary indexes. However, they are not containers per-se: they don’t own the data. As such, they do not guarantee anything about the data, such as contiguity or elements storage order, which can make a difference in some scenarios. The good news is that ``indexed_array``, like any container, can take full benefit of ``views``, which can be used on top of it. Using ``std::unordered_map`` ---------------------------- ``std::unordered_map`` provides the same convenience of access as ``indexed_array``. However, it is a dynamically sized container. It does not provide the triviality guarantees, nor does it provides safe initialization. It also requires dynamic allocation. Its size is dynamic, and items are not contiguous. It stores both the “key” and the “value”, whereas ``indexed_array`` stores only the value. Boost.MultiIndex ---------------- ``boost::multi_index`` is intended to provide different ways of indexing a data set. This is different from ``indexed_array`` which provides a single indexing mechanism. It does not provide triviality guarantees, and is dynamically resizable. Frozen ------ `Frozen `__ Frozen’s ``unordered_map`` offers another way to access elements via custom values. It provides a fixed size, container-like structure. It allows providing a custom hash. It guarantees O(1) access to its elements. There are a few differences, though: - there are no guarantees on the way the element are stored inside the container. In particular, you don’t have any control on the order of the elements. - there is no triviality propagation - there are no guarantees on the size of the data structure. An ``unordered_map`` of 4 pairs of int values takes already more than 150 bytes. - being inherently a map, it stores both the keys and the values. This is different from ``indexed_array``, which stores only the values. - there is no unchecked access, only the throwing at() function is provided Feature table comparison ------------------------ .. csv-table:: Feature Comparison :header-rows: 1 :file: comparison.csv ¹: Access guarantees depends on indexer template parameter. O(1) access is guaranted by the default indexer if the index is a contiguous range of elements (no gaps between the successive values). If that’s not the case, the current implementation use O(n) access. This could be improved to O(log(n)) in a further release, for great values of n. ²: ``std::unordered_map`` initialization mechanism will prevent any order fiasco, with the value being associated to the wrong key due to a refactor. However, you don’t have any size check. ³: I think it could theoretically reside in ro section, but for some reasons that does not seem to be the case with the tests i made. I’m leaving it as unsure for now, as it may just be some bad usage. ⁴: Type safe index means that you cannot access the content using a value of a wrong type. While technically, you can’t access an ``std::array`` content with anything else than a ``size_t``, this is a too generic type to be considered type safe. ⁵: Iterating through both keys and values is supported via an helper function, for single dimensional arrays only. This helper is, however, not suitable for large size arrays, as it would generate a lot of code.