1.. _module-pw_containers-maps: 2 3==== 4Maps 5==== 6.. pigweed-module-subpage:: 7 :name: pw_containers 8 9A map is an associative collection of keys that map to values. Pigweed provides 10an implementation of a constant "flat" map that can find values by key in 11constant time. It also provides implementations of dynamic maps that can insert, 12find, and remove key-value pairs in logarithmic time. 13 14----------------------- 15pw::containers::FlatMap 16----------------------- 17``FlatMap`` provides a simple, fixed-size associative array with ``O(log n)`` 18lookup by key. 19 20``pw::containers::FlatMap`` contains the same methods and features for looking 21up data as ``std::map``. However, modification of the underlying data is limited 22to the mapped values, via ``.at()`` (key must exist) and ``mapped_iterator`` 23objects returned by ``.mapped_begin()`` and ``.mapped_end()``. 24``mapped_iterator`` objects are bidirectional iterators that can be dereferenced 25to access and mutate the mapped value objects. 26 27The underlying array in ``pw::containers::FlatMap`` does not need to be sorted. 28During construction, ``pw::containers::FlatMap`` will perform a constexpr 29insertion sort. 30 31Examples 32======== 33A ``FlatMap`` can be created in one of several ways. Each of the following 34examples defines a ``FlatMap`` with two items. 35 36.. literalinclude:: examples/flat_map.cc 37 :language: cpp 38 :linenos: 39 :start-after: [pw_containers-flat_map] 40 :end-before: [pw_containers-flat_map] 41 42.. _module-pw_containers-intrusive_map: 43 44---------------- 45pw::IntrusiveMap 46---------------- 47``pw::IntrusiveMap`` provides an embedded-friendly, tree-based, intrusive 48map implementation. The intrusive aspect of the map is very similar to that of 49:ref:`module-pw_containers-intrusive_list`. 50 51See also :ref:`module-pw_containers-multiple_containers`. 52 53Example 54======= 55.. literalinclude:: examples/intrusive_map.cc 56 :language: cpp 57 :linenos: 58 :start-after: [pw_containers-intrusive_map] 59 :end-before: [pw_containers-intrusive_map] 60 61If you need to add this item to containers of more than one type, see 62:ref:`module-pw_containers-multiple_containers`, 63 64API reference 65============= 66This class is similar to ``std::map<K, V>``. Items to be added must derive from 67``pw::IntrusiveMap<K, V>::Item`` or an equivalent type. 68 69.. doxygenclass:: pw::IntrusiveMap 70 :members: 71 72--------------------- 73pw::IntrusiveMultiMap 74--------------------- 75``pw::IntrusiveMultiMap`` provides an embedded-friendly, tree-based, intrusive 76multimap implementation. This is very similar to 77:ref:`module-pw_containers-intrusive_map`, except that the tree may contain 78multiple items with equivalent keys. 79 80See also :ref:`module-pw_containers-multiple_containers`. 81 82Example 83======= 84.. literalinclude:: examples/intrusive_multimap.cc 85 :language: cpp 86 :linenos: 87 :start-after: [pw_containers-intrusive_multimap] 88 :end-before: [pw_containers-intrusive_multimap] 89 90If you need to add this item to containers of more than one type, see 91:ref:`module-pw_containers-multiple_containers`, 92 93API reference 94============= 95This class is similar to ``std::multimap<K, V>``. Items to be added must derive 96from ``pw::IntrusiveMultiMap<K, V>::Item`` or an equivalent type. 97 98.. doxygenclass:: pw::IntrusiveMultiMap 99 :members: 100 101 102Size reports 103------------ 104The tables below illustrate the following scenarios: 105 106* Scenarios related to ``FlatMap``: 107 108 * The memory and code size cost incurred by adding another ``FlatMap`` 109 * The memory and code size cost incurred by adding another ``FlatMap`` with 110 different key and value types. As ``FlatMap`` is templated on both key and 111 value types, this results in additional code being generated. 112 113* Scenarios related to ``IntrusiveMap``: 114 115 * The memory and code size cost incurred by a adding a single 116 ``IntrusiveMap``. 117 * The memory and code size cost incurred by adding another ``IntrusiveMap`` 118 with the same key type, but a different value type. As ``IntrusiveMap`` is 119 templated on both key and value types, this results in additional code being 120 generated. 121 * The memory and code size cost incurred by adding another ``IntrusiveMap`` 122 with the same value type, but a different key type. As ``IntrusiveMap`` is 123 templated on both key and value types, this results in additional code being 124 generated. 125 126* Scenarios related to ``IntrusiveMultiMap``: 127 128 * The memory and code size cost incurred by a adding a single 129 ``IntrusiveMultiMap``. 130 * The memory and code size cost incurred by adding another 131 ``IntrusiveMultiMap`` with the same key type, but a different value type. As 132 ``IntrusiveMultiMap`` is templated on both key and value types, this results 133 in additional code being generated. 134 * The memory and code size cost incurred by adding another 135 ``IntrusiveMultiMap`` with the same value type, but a different key type. As 136 ``IntrusiveMultiMap`` is templated on both key and value types, this results 137 in additional code being generated. 138 139* The memory and code size cost incurred by a adding both an ``IntrusiveMap`` 140 and an ``IntrusiveMultiMap`` of the same type. These types reuse code, so the 141 combined sum is less than the sum of its parts. 142 143.. TODO: b/388905812 - Re-enable the size report. 144.. .. include:: maps_size_report 145.. include:: ../size_report_notice 146