Part 1: Implement flat_map

Design and implement an associative container flat_map backed by a sorted dynamic array of (Key, Value) pairs. The implementation must support the following APIs:

• Constructor(s)
• size() / empty()
• clear()
• find()
• count()
• contains()
• at()
• operator[]
• lower_bound() / upper_bound()
• insert() (single and range)
• emplace()
• erase() (by key, iterator, or range)
• Iteration in sorted key order
• Copy/move semantics
• Equality comparison

Constraints & Requirements:

• Enforce unique keys.
• Achieve O(log n) lookup via binary search.
• Achieve amortized O(n) insertion with minimal reallocations.
• Implement a conforming bidirectional iterator (and const_iterator) with correct validity/invalidations on insert/erase.
• Ensure iterator arithmetic/relational operators behave as specified.

Deliverables:

• Provide unit tests for edge cases (e.g., empty container, duplicates, key and value types with non-trivial moves, iterator invalidation, const-correctness).
• Explain your design choices and complexity trade-offs versus tree-based maps.

Part 2: Redistribute Wealth

Given an integer array representing individuals’ wealth (values may be negative, zero, or positive), design an algorithm to redistribute wealth via integer transfers between indices so that final wealths are as equal as possible while preserving the total sum.

Deliverables:

a) State and justify a precise objective (e.g., minimize maximum absolute deviation from the target, or minimize total absolute deviation). b) Determine the optimal target wealth value(s) under your objective when only integer amounts are allowed. c) Output a sequence of transfers (i, j, amount) that transforms the initial array to the final array, along with the final wealths. d) Prove correctness and analyze time and space complexity. Discuss alternative objectives and how they change the algorithm.