11.03 Red-Black Trees vs Hash Tables: Deterministic O(log N) vs Unpredictable O(1) Rehash Latency
std::map) against bucket-based Hash Tables (std::unordered_map). We explore time complexity determinism, catastrophic rehash latency spikes, dynamic node allocation heap fragmentation, and why static flat maps are the standard embedded choice.
💻 1. Annotated Source Code
#include <iostream> #include <map> #include <unordered_map> #include <string> using namespace std; int main() { cout << "=== std::map ===" << endl; map<string, int> orderedMap; orderedMap["banana"] = 3; orderedMap["apple"] = 5; orderedMap["cherry"] = 2; cout << "Contents of ordered map (keys will be sorted):" << endl; for (const auto& pair : orderedMap) { cout << pair.first<<": " << pair.second << endl; } cout << "\nLooking up 'apple' in orderedMap: "; auto it1 = orderedMap.find("apple"); if (it1 != orderedMap.end()) { cout << "Found, value = " << it1->second << endl; } else { cout << "Not found!" << endl; } cout << endl << endl; cout << "=== std::unordered_map ===" << endl; unordered_map<string, int> unorderedMap; unorderedMap["banana"] = 3; unorderedMap["apple"] = 5; unorderedMap["cherry"] = 2; cout << "Contents of unordered map (no guaranteed order):" << endl; for (const auto& pair : unorderedMap) { cout << pair.first << ": " << pair.second << endl; } cout << "\nLooking up 'apple' in unorderedMap: "; auto it2 = unorderedMap.find("apple"); if (it2 != unorderedMap.end()) { cout << "Found, value = " << it2->second << endl; } else { cout << "Not found." << endl; } return 0; }
📐 2. Architecture & UML Class Model
📚 3. Core C++ Concepts Deep-Dive
1. Data Structure Architecture
std::map is implemented as a Self-Balancing Red-Black Tree with strictly ordered keys. Search, insertion, and deletion are guaranteed $O(\log N)$ time.
std::unordered_map is implemented as a Hash Table with Chaining. Average lookup is $O(1)$, but worst-case lookup is $O(N)$ when hash collisions occur or when the table triggers a dynamic rehashing re-allocation.
⚡ 4. Embedded Systems & Hardware Reality
1. Real-Time Determinism: The Rehash Latency Spike Hazard
In hard real-time systems (e.g. braking systems, avionics), an operation must NEVER exceed its worst-case execution time (WCET). While std::unordered_map is fast on average, inserting an element that triggers a bucket table resize reallocates memory and re-hashes every existing entry—causing latency spikes of several milliseconds!
2. Heap Fragmentation: 24 to 32 Bytes per Node
Both standard containers dynamically allocate individual heap nodes for every stored element (storing tree pointers: parent, left, right, color, or hash buckets). On microcontrollers with limited SRAM, this causes extreme memory fragmentation.
💡 The Embedded Solution: Flat Maps (Sorted Arrays)
For small, fixed sets of keys (e.g. CAN message IDs, sensor calibration tables), use a contiguous sorted std::array<std::pair<K, V>, N> with std::lower_bound for $O(\log N)$ binary search, zero heap allocations, and 100% L1 cache locality!
💡 5. Production-Ready Embedded Refactoring
Here is an embedded compile-time Flash ROM lookup table using binary search on sorted array:
#include <array> #include <algorithm> #include <iostream> #include <string_view> struct CanMessageDescriptor { uint32_t canId; std::string_view name; }; // Stored directly in Flash ROM (.rodata) - ZERO RAM overhead! constexpr std::array<CanMessageDescriptor, 4> CAN_LUT = {{ {0x100, "Engine RPM"}, {0x101, "Vehicle Speed"}, {0x200, "Brake Pressure"}, {0x305, "Battery Voltage"} }}; std::string_view lookupCanName(uint32_t id) { auto it = std::lower_bound(CAN_LUT.begin(), CAN_LUT.end(), id, [](const CanMessageDescriptor& item, uint32_t target) { return item.canId < target; }); if (it != CAN_LUT.end() && it->canId == id) { return it->name; } return "Unknown ID"; }
📝 Knowledge Verification Quiz
Test your understanding of the C++ concepts and embedded microcontroller trade-offs covered in this guide. Click any option for instant feedback.
std::map guarantees $O(\log N)$ worst-case time complexity, whereas std::unordered_map can spike to $O(N)$ during hash collisions and bucket table reallocations, violating real-time deadlines.
malloc for each element to allocate tree nodes or linked list collision nodes, causing severe SRAM fragmentation and pointer overhead.