diff options
Diffstat (limited to 'json4cpp/include/nlohmann/ordered_map.hpp')
| -rw-r--r-- | json4cpp/include/nlohmann/ordered_map.hpp | 359 |
1 files changed, 359 insertions, 0 deletions
diff --git a/json4cpp/include/nlohmann/ordered_map.hpp b/json4cpp/include/nlohmann/ordered_map.hpp new file mode 100644 index 0000000000..d8606f82fd --- /dev/null +++ b/json4cpp/include/nlohmann/ordered_map.hpp @@ -0,0 +1,359 @@ +// __ _____ _____ _____ +// __| | __| | | | JSON for Modern C++ +// | | |__ | | | | | | version 3.12.0 +// |_____|_____|_____|_|___| https://github.com/nlohmann/json +// +// SPDX-FileCopyrightText: 2013-2026 Niels Lohmann <https://nlohmann.me> +// SPDX-License-Identifier: MIT + +#pragma once + +#include <functional> // equal_to, less +#include <initializer_list> // initializer_list +#include <iterator> // input_iterator_tag, iterator_traits +#include <memory> // allocator +#include <stdexcept> // for out_of_range +#include <type_traits> // enable_if, is_convertible +#include <utility> // pair +#include <vector> // vector + +#include <nlohmann/detail/macro_scope.hpp> +#include <nlohmann/detail/meta/type_traits.hpp> + +NLOHMANN_JSON_NAMESPACE_BEGIN + +/// ordered_map: a minimal map-like container that preserves insertion order +/// for use within nlohmann::basic_json<ordered_map> +template <class Key, class T, class IgnoredLess = std::less<Key>, + class Allocator = std::allocator<std::pair<const Key, T>>> + struct ordered_map : std::vector<std::pair<const Key, T>, Allocator> +{ + using key_type = Key; + using mapped_type = T; + using Container = std::vector<std::pair<const Key, T>, Allocator>; + using iterator = typename Container::iterator; + using const_iterator = typename Container::const_iterator; + using size_type = typename Container::size_type; + using value_type = typename Container::value_type; +#ifdef JSON_HAS_CPP_14 + using key_compare = std::equal_to<>; +#else + using key_compare = std::equal_to<Key>; +#endif + + // Explicit constructors instead of `using Container::Container` + // otherwise older compilers choke on it (GCC <= 5.5, xcode <= 9.4) + ordered_map() noexcept(noexcept(Container())) : Container{} {} + explicit ordered_map(const Allocator& alloc) noexcept(noexcept(Container(alloc))) : Container{alloc} {} + template <class It> + ordered_map(It first, It last, const Allocator& alloc = Allocator()) + : Container{first, last, alloc} {} + ordered_map(std::initializer_list<value_type> init, const Allocator& alloc = Allocator() ) + : Container{init, alloc} {} + + std::pair<iterator, bool> emplace(const key_type& key, T&& t) + { + for (auto it = this->begin(); it != this->end(); ++it) + { + if (m_compare(it->first, key)) + { + return {it, false}; + } + } + Container::emplace_back(key, std::forward<T>(t)); + return {std::prev(this->end()), true}; + } + + template<class KeyType, detail::enable_if_t< + detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> + std::pair<iterator, bool> emplace(KeyType && key, T && t) + { + for (auto it = this->begin(); it != this->end(); ++it) + { + if (m_compare(it->first, key)) + { + return {it, false}; + } + } + Container::emplace_back(std::forward<KeyType>(key), std::forward<T>(t)); + return {std::prev(this->end()), true}; + } + + T& operator[](const key_type& key) + { + return emplace(key, T{}).first->second; + } + + template<class KeyType, detail::enable_if_t< + detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> + T & operator[](KeyType && key) + { + return emplace(std::forward<KeyType>(key), T{}).first->second; + } + + const T& operator[](const key_type& key) const + { + return at(key); + } + + template<class KeyType, detail::enable_if_t< + detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> + const T & operator[](KeyType && key) const + { + return at(std::forward<KeyType>(key)); + } + + T& at(const key_type& key) + { + for (auto it = this->begin(); it != this->end(); ++it) + { + if (m_compare(it->first, key)) + { + return it->second; + } + } + + JSON_THROW(std::out_of_range("key not found")); + } + + template<class KeyType, detail::enable_if_t< + detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> + T & at(KeyType && key) // NOLINT(cppcoreguidelines-missing-std-forward) + { + for (auto it = this->begin(); it != this->end(); ++it) + { + if (m_compare(it->first, key)) + { + return it->second; + } + } + + JSON_THROW(std::out_of_range("key not found")); + } + + const T& at(const key_type& key) const + { + for (auto it = this->begin(); it != this->end(); ++it) + { + if (m_compare(it->first, key)) + { + return it->second; + } + } + + JSON_THROW(std::out_of_range("key not found")); + } + + template<class KeyType, detail::enable_if_t< + detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> + const T & at(KeyType && key) const // NOLINT(cppcoreguidelines-missing-std-forward) + { + for (auto it = this->begin(); it != this->end(); ++it) + { + if (m_compare(it->first, key)) + { + return it->second; + } + } + + JSON_THROW(std::out_of_range("key not found")); + } + + size_type erase(const key_type& key) + { + for (auto it = this->begin(); it != this->end(); ++it) + { + if (m_compare(it->first, key)) + { + // Since we cannot move const Keys, re-construct them in place + for (auto next = it; ++next != this->end(); ++it) + { + it->~value_type(); // Destroy but keep allocation + new (&*it) value_type{std::move(*next)}; + } + Container::pop_back(); + return 1; + } + } + return 0; + } + + template<class KeyType, detail::enable_if_t< + detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> + size_type erase(KeyType && key) // NOLINT(cppcoreguidelines-missing-std-forward) + { + for (auto it = this->begin(); it != this->end(); ++it) + { + if (m_compare(it->first, key)) + { + // Since we cannot move const Keys, re-construct them in place + for (auto next = it; ++next != this->end(); ++it) + { + it->~value_type(); // Destroy but keep allocation + new (&*it) value_type{std::move(*next)}; + } + Container::pop_back(); + return 1; + } + } + return 0; + } + + iterator erase(iterator pos) + { + return erase(pos, std::next(pos)); + } + + iterator erase(iterator first, iterator last) + { + if (first == last) + { + return first; + } + + const auto elements_affected = std::distance(first, last); + const auto offset = std::distance(Container::begin(), first); + + // This is the start situation. We need to delete elements_affected + // elements (3 in this example: e, f, g), and need to return an + // iterator past the last deleted element (h in this example). + // Note that offset is the distance from the start of the vector + // to first. We will need this later. + + // [ a, b, c, d, e, f, g, h, i, j ] + // ^ ^ + // first last + + // Since we cannot move const Keys, we re-construct them in place. + // We start at first and re-construct (viz. copy) the elements from + // the back of the vector. Example for the first iteration: + + // ,--------. + // v | destroy e and re-construct with h + // [ a, b, c, d, e, f, g, h, i, j ] + // ^ ^ + // it it + elements_affected + + for (auto it = first; std::next(it, elements_affected) != Container::end(); ++it) + { + it->~value_type(); // destroy but keep allocation + new (&*it) value_type{std::move(*std::next(it, elements_affected))}; // "move" next element to it + } + + // [ a, b, c, d, h, i, j, h, i, j ] + // ^ ^ + // first last + + // remove the unneeded elements at the end of the vector + Container::resize(this->size() - static_cast<size_type>(elements_affected)); + + // [ a, b, c, d, h, i, j ] + // ^ ^ + // first last + + // first is now pointing past the last deleted element, but we cannot + // use this iterator, because it may have been invalidated by the + // resize call. Instead, we can return begin() + offset. + return Container::begin() + offset; + } + + size_type count(const key_type& key) const + { + for (auto it = this->begin(); it != this->end(); ++it) + { + if (m_compare(it->first, key)) + { + return 1; + } + } + return 0; + } + + template<class KeyType, detail::enable_if_t< + detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> + size_type count(KeyType && key) const // NOLINT(cppcoreguidelines-missing-std-forward) + { + for (auto it = this->begin(); it != this->end(); ++it) + { + if (m_compare(it->first, key)) + { + return 1; + } + } + return 0; + } + + iterator find(const key_type& key) + { + for (auto it = this->begin(); it != this->end(); ++it) + { + if (m_compare(it->first, key)) + { + return it; + } + } + return Container::end(); + } + + template<class KeyType, detail::enable_if_t< + detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> + iterator find(KeyType && key) // NOLINT(cppcoreguidelines-missing-std-forward) + { + for (auto it = this->begin(); it != this->end(); ++it) + { + if (m_compare(it->first, key)) + { + return it; + } + } + return Container::end(); + } + + const_iterator find(const key_type& key) const + { + for (auto it = this->begin(); it != this->end(); ++it) + { + if (m_compare(it->first, key)) + { + return it; + } + } + return Container::end(); + } + + std::pair<iterator, bool> insert( value_type&& value ) + { + return emplace(value.first, std::move(value.second)); + } + + std::pair<iterator, bool> insert( const value_type& value ) + { + for (auto it = this->begin(); it != this->end(); ++it) + { + if (m_compare(it->first, value.first)) + { + return {it, false}; + } + } + Container::push_back(value); + return {--this->end(), true}; + } + + template<typename InputIt> + using require_input_iter = typename std::enable_if<std::is_convertible<typename std::iterator_traits<InputIt>::iterator_category, + std::input_iterator_tag>::value>::type; + + template<typename InputIt, typename = require_input_iter<InputIt>> + void insert(InputIt first, InputIt last) + { + for (auto it = first; it != last; ++it) + { + insert(*it); + } + } + +private: + JSON_NO_UNIQUE_ADDRESS key_compare m_compare = key_compare(); +}; + +NLOHMANN_JSON_NAMESPACE_END |