Implement a serializable key-value store

Implement in C++ an in-memory key-value store with:

• put(key: string, value: string), get(key) -> optional<string>, erase(key).
• serialize() -> vector<uint8_t> that encodes the entire store state.
• deserialize(const vector<uint8_t>&) to restore an identical store state. Constraints:
• Use only the provided helper byte I/O functions; do not use external libraries for serialization.
• Choose a robust binary format (versioned, length-prefixed) that supports arbitrary bytes in keys/values and Unicode.
• Ensure correctness for empty store, very large keys/values, duplicate overwrites, and deletions.
• Validate input and handle malformed or truncated streams gracefully with clear error signaling.
• Time/space complexity should be O(n) in the total serialized data size; support streaming-friendly encoding.
• Provide unit tests and explain complexity, trade-offs (e.g., delimiter-escaped text vs. length-prefixed binary), and failure recovery.

Implement a Serializable Key-Value Store

Implement an in-memory key–value store with a custom binary serialization format, driven by a list of operations.

Because the judge calls a single function rather than a class, you are given a list of operations to apply, in order, to one store. Each operation is a sequence (tuple/list) whose first element is the operation name and whose remaining elements are its arguments:

def solution(operations):
    ...

Operations

Apply each operation to a single store, in the given order:

• ('put', key, value) — Insert or update key with value. If key already exists, overwrite its value in place (do not create a duplicate entry, and keep the key's original position in insertion order). Produces no output.
• ('get', key) — Append the stored value for key to the result, or None if the key is absent.
• ('erase', key) — Remove key from the store. Erasing a missing key does nothing. Produces no output.
• ('serialize',) — Append the bytes encoding of the entire current store to the result (see format below).
• ('deserialize', blob) — Attempt to parse blob. Append True if the blob is fully valid (and replace the store with the parsed contents), or False if it is malformed (and leave the store unchanged).

Return a list containing the outputs of every get, serialize, and deserialize operation, in the order they occurred. put and erase contribute nothing to the result.

Key / value handling

• Keys and values are bytes objects.
• If a test passes a Python str, treat it as UTF-8 and convert it to bytes before storing, comparing, or encoding.

Binary serialization format

serialize must produce, and deserialize must accept, exactly this length-prefixed binary layout:

1. 4-byte magic header: the ASCII bytes KVS1.
2. 4-byte unsigned big-endian entry count.
3. For each key–value pair, in current insertion order:
   • 4-byte unsigned big-endian key length
   • the raw key bytes
   • 4-byte unsigned big-endian value length
   • the raw value bytes

Length prefixes (rather than delimiters) keep the format robust for keys/values that may contain arbitrary bytes, including zero bytes and non-ASCII Unicode data.

Deserialization rules (all-or-nothing)

deserialize replaces the store only if blob is completely valid. On any failure, leave the store unchanged and append False. A blob is malformed if any of the following hold:

• The magic header is not KVS1.
• The blob is truncated — any declared length runs past the end of the data, or there are too few bytes to read a required field.
• It contains duplicate keys.
• There are extra trailing bytes after the declared number of entries have been read.

Constraints

• 1 <= len(operations) <= 200000
• The total number of bytes across all keys, values, and serialized blobs is at most 10^6.
• Each key and value length is between 0 and 2^32 - 1 bytes.
• Average-case O(1) map operations are acceptable; each serialize / deserialize must run in time linear in the blob size.

Examples

Example 1

Input: [('put', b'name', b'alice'), ('put', b'lang', b'py'), ('get', b'name'), ('serialize',), ('erase', b'name'), ('get', b'name'), ('deserialize', b'KVS1\x00\x00\x00\x02\x00\x00\x00\x04name\x00\x00\x00\x05alice\x00\x00\x00\x04lang\x00\x00\x00\x02py'), ('get', b'name'), ('get', b'lang')]
Output: [b'alice', b'KVS1\x00\x00\x00\x02\x00\x00\x00\x04name\x00\x00\x00\x05alice\x00\x00\x00\x04lang\x00\x00\x00\x02py', None, True, b'alice', b'py']

Explanation: The store is serialized with two entries, then one key is deleted. Deserializing the earlier blob restores both pairs.

Example 2

Input: [('serialize',), ('deserialize', b'KVS1\x00\x00\x00\x00'), ('get', b'missing')]
Output: [b'KVS1\x00\x00\x00\x00', True, None]

Explanation: An empty store serializes to just the header and a zero entry count. Deserializing it succeeds and the store remains empty.

Hints

1. A delimiter like ':' is unsafe because keys and values may contain arbitrary bytes. Store a fixed-size length before each raw byte sequence.
2. For failure recovery, do not modify the live store while parsing a blob. Decode into a temporary dictionary first, then replace the store only if parsing finishes exactly at the end.

Approach

The store is a plain Python dict. Because dict preserves insertion order (3.7+), it doubles as both the hash map for O(1) get/put/erase and the ordered record of entries that serialization must emit — put on an existing key reassigns the value in place, so order is preserved and no duplicate entry is created.

Operation loop. to_bytes normalizes any str/bytearray input to bytes (UTF-8 for strings) so keys/values are uniform. get returns store.get(key) (None if absent); erase is store.pop(key, None) (no-op on miss). Outputs of get, serialize, deserialize are appended to result in order.

Serialize. serialize_store appends the KVS1 magic, a big-endian u32 entry count, then for each pair a u32 key length + raw key + u32 value length + raw value, joined once with b''.join. Lengths are written via manual byte shifts in write_u32.

Deserialize (the careful part). try_deserialize parses into a fresh new_store and only the caller swaps store on success, guaranteeing the store is untouched on any failure. It rejects: blobs shorter than 8 bytes, wrong magic, any read that would run past the end (read_u32 returns None, or pos + len > len(data) — catches truncation), a key already present in new_store (duplicate), and pos != len(data) at the end (extra trailing bytes). All of these return False.

Why correct: length-prefixing makes parsing unambiguous for arbitrary bytes (including NUL/non-ASCII), and every malformed condition in the spec maps to one explicit check.

• Time complexity: O(Q + B) where Q is the number of operations and B is the total bytes across all serialize/deserialize blobs. Each put/get/erase is average-case O(1) on the dict; serialize/deserialize each touch every byte exactly once (linear in blob size).
• Space complexity: O(M + S) where M is the total bytes currently held in the store and S is the size of the largest blob being produced or parsed (the joined output, or the fresh new_store built during deserialize).