Mechanics of the Subscript Operator in std::map

The operator[] in std::map serves as both an insertion and a lookup mechanism. Unlike the at() member function, which throws an exception if a key is missing, the subscript operator ensures the key exists after the call.

Under the hood, operator[] is typically implemanted using the insert method. The insert function returns a pair<iterator, bool>, where the iterator points to the element with the target key (whether newly created or already existing), and the bool indicates if a new insertion occurred. The operator then dereferences the iterator to access the value part of the pair<const Key, Value> and returns a reference to it.

If the key does not exist, the container value-initializes the mapped type (e.g., int becomes 0, and objects call their default constructor). Because of this behavior, using operator[] for lookup is generally discouraged if you do not want to inadvertent modify the container. For read-only access, find() or at() should be preferred.

Comparing Ordered and Unordered Containers

C++ provides two main families of associative containers: std::map/std::set and std::unordered_map/std::unordered_set.

Hashing Fundamentals and Collision Resolution

Hashing maps a large key space to a smaller array index range. The efficiency of a hash table depends on its hash function and its strategy for handling collisions (when two keys map to the same index).

Open Addressing (Closed Hashing)

In open addressing, if a collision occurs, the algorithm searches for the next available slot within the array. Common probing techniques include:

1. Linear Probing: Checking the next sequential slot (index + 1).
2. Quadratic Probing: Checking slots based on a quadratic sequence (index + i²).

Below is an implementation of a hash table using linear probing:

enum class SlotStatus { Empty, Occupied, Deleted };

template<typename K, typename V>
struct HashEntry {
    std::pair<K, V> _kv;
    SlotStatus _status = SlotStatus::Empty;
};

template<typename K, typename V, typename KeyExtractor>
class OpenAddressingTable {
public:
    bool Insert(const std::pair<K, V>& data) {
        KeyExtractor extract;
        if (_storage.empty() || _count * 10 / _storage.size() >= 7) {
            Rehash();
        }

        size_t pos = extract(data.first) % _storage.size();
        while (_storage[pos]._status == SlotStatus::Occupied) {
            if (extract(_storage[pos]._kv.first) == extract(data.first)) return false;
            pos = (pos + 1) % _storage.size();
        }

        _storage[pos]._kv = data;
        _storage[pos]._status = SlotStatus::Occupied;
        _count++;
        return true;
    }

private:
    void Rehash() {
        size_t newSize = _storage.empty() ? 10 : _storage.size() * 2;
        std::vector<HashEntry<K, V>> newTable(newSize);
        KeyExtractor extract;

        for (auto& entry : _storage) {
            if (entry._status == SlotStatus::Occupied) {
                size_t pos = extract(entry._kv.first) % newSize;
                while (newTable[pos]._status == SlotStatus::Occupied) {
                    pos = (pos + 1) % newSize;
                }
                newTable[pos] = entry;
            }
        }
        _storage.swap(newTable);
    }

    std::vector<HashEntry<K, V>> _storage;
    size_t _count = 0;
};

Separate Chaining (Open Hashing)

Separate chaining handles collisions by maintaining a linked list (or bucket) at each index. When multiple keys map to the same position, they are appended to the list. This method is generally more robust against high load factors than open addressing.

template<typename T>
struct BucketNode {
    T _data;
    BucketNode<T>* _next;
    BucketNode(const T& data) : _data(data), _next(nullptr) {}
};

template<typename K, typename V, typename KeyExtractor>
class ChainedHashTable {
    typedef BucketNode<std::pair<K, V>> Node;
public:
    bool Add(const std::pair<K, V>& kv) {
        KeyExtractor extract;
        if (_elementCount == _buckets.size()) {
            ExpandBuckets();
        }

        size_t index = extract(kv.first) % _buckets.size();
        Node* current = _buckets[index];
        while (current) {
            if (extract(current->_data.first) == extract(kv.first)) return false;
            current = current->_next;
        }

        Node* newNode = new Node(kv);
        newNode->_next = _buckets[index];
        _buckets[index] = newNode;
        _elementCount++;
        return true;
    }

private:
    void ExpandBuckets() {
        size_t newSize = _buckets.empty() ? 10 : _buckets.size() * 2;
        std::vector<Node*> newBuckets(newSize, nullptr);
        KeyExtractor extract;

        for (size_t i = 0; i < _buckets.size(); ++i) {
            Node* current = _buckets[i];
            while (current) {
                Node* nextNode = current->_next;
                size_t newIdx = extract(current->_data.first) % newSize;
                
                current->_next = newBuckets[newIdx];
                newBuckets[newIdx] = current;
                current = nextNode;
            }
            _buckets[i] = nullptr;
        }
        _buckets.swap(newBuckets);
    }

    std::vector<Node*> _buckets;
    size_t _elementCount = 0;
};

While open addressing is cache-friendly due to memory locality, separate chaining is easier to implement for deletion and performs more gracefully as the load factor approaches 1. In modern C++ standard library implementations, unordered_map typically utilizes a form of separate chaining.