Estrutura do Map

O map armazena pares chave-valer (Key-Value) onde cada chave é única. Aqui está a implementação:

#pragma once

#include <iostream>
#include "ArvoreRB.h"

template<typename Chave, typename Valor>
class Mapa {
    struct ExtratorChave {
        const Chave& operator()(const std::pair<Chave, Valor>& par) const {
            return par.first;
        }
    };

public:
    typedef std::pair<Chave, Valor> Par;
    typedef IteradorRB<Par, Par*, Par&> Iterador;

    Iterador inicio() {
        return _arvore.inicio();
    }

    Iterador fim() {
        return _arvore.fim();
    }

    bool inserir(const std::pair<Chave, Valor>& par) {
        return _arvore.inserir(par);
    }

    void percorrerEmOrdem() {
        _arvore.percorrerEmOrdem();
    }

private:
    ArvoreRB<Chave, std::pair<Chave, Valor>, ExtratorChave> _arvore;
};

Estrutura do Set

O set armazena apenas chaves únicas. Sua implementação segue abaixo:

#pragma once

#include "ArvoreRB.h"

template<typename Chave>
class Conjunto {
    struct ExtratorChave {
        const Chave& operator()(const Chave& valor) const {
            return valor;
        }
    };

public:
    typedef IteradorRB<Chave, Chave*, Chave&> Iterador;

    Iterador inicio() {
        return _arvore.inicio();
    }

    Iterador fim() {
        return _arvore.fim();
    }

    bool inserir(const Chave& valor) {
        return _arvore.inserir(valor);
    }

    void percorrerEmOrdem() {
        _arvore.percorrerEmOrdem();
    }

private:
    ArvoreRB<Chave, Chave, ExtratorChave> _arvore;
};

Implementação da Árvore Rubro-Negra

Abaixo está a implementação da árvore rubro-negra utilizada tanto pelo map quanto pelo set:

#pragma once

#include <iostream>

enum Cor { VERMELHO, PRETO };

template<typename TipoValor>
struct NoRB {
    NoRB(const TipoValor& valor = TipoValor())
        : esquerda(nullptr), direita(nullptr), pai(nullptr), cor(VERMELHO), dado(valor) {}

    NoRB<TipoValor>* esquerda;
    NoRB<TipoValor>* direita;
    NoRB<TipoValor>* pai;
    int cor;
    TipoValor dado;
};

template<typename TipoValor, typename Ponteiro, typename Referencia>
class IteradorRB {
    typedef NoRB<TipoValor> No;

public:
    IteradorRB(No* no) : _no(no) {}

    Ponteiro operator->() {
        return &(_no->dado);
    }

    Referencia operator*() {
        return _no->dado;
    }

    bool operator!=(const IteradorRB& outro) const {
        return _no != outro._no;
    }

    IteradorRB& operator++() {
        if (_no->direita) {
            No* esquerdo = _no->direita;
            while (esquerdo->esquerda) {
                esquerdo = esquerdo->esquerda;
            }
            _no = esquerdo;
        } else {
            No* atual = _no;
            No* pai = atual->pai;
            while (pai && atual == pai->direita) {
                atual = pai;
                pai = pai->pai;
            }
            _no = pai;
        }
        return *this;
    }

private:
    No* _no;
};

template<typename Chave, typename TipoValor, typename ExtratorChave>
class ArvoreRB {
public:
    typedef NoRB<TipoValor> No;
    typedef IteradorRB<TipoValor, TipoValor*, TipoValor&> Iterador;

    ArvoreRB() : _raiz(nullptr) {}

    Iterador inicio() {
        No* atual = _raiz;
        while (atual && atual->esquerda) {
            atual = atual->esquerda;
        }
        return Iterador(atual);
    }

    Iterador fim() {
        return Iterador(nullptr);
    }

    bool inserir(const TipoValor& valor) {
        // Inserção básica
        No* atual = _raiz;
        No* pai = nullptr;

        while (atual) {
            pai = atual;
            if (ExtratorChave()(atual->dado) < ExtratorChave()(valor)) {
                atual = atual->esquerda;
            } else if (ExtratorChave()(atual->dado) > ExtratorChave()(valor)) {
                atual = atual->direita;
            } else {
                return false;
            }
        }

        atual = new No(valor);
        if (!pai) {
            _raiz = atual;
        } else {
            if (ExtratorChave()(pai->dado) > ExtratorChave()(valor)) {
                pai->esquerda = atual;
            } else {
                pai->direita = atual;
            }
            atual->pai = pai;
        }

        // Balanceamento após inserção
        balancear(atual);

        return true;
    }

    void percorrerEmOrdem() {
        _percorrerEmOrdem(_raiz);
    }

private:
    void _percorrerEmOrdem(No* raiz) {
        if (!raiz) return;
        _percorrerEmOrdem(raiz->esquerda);
        std::cout << ExtratorChave()(raiz->dado) << " ";
        _percorrerEmOrdem(raiz->direita);
    }

    void rotacionarDireita(No* pai) {
        No* filhoEsquerdo = pai->esquerda;
        No* netoDireito = filhoEsquerdo->direita;

        No* avo = pai->pai;

        pai->esquerda = netoDireito;
        if (netoDireito) {
            netoDireito->pai = pai;
        }

        filhoEsquerdo->direita = pai;
        pai->pai = filhoEsquerdo;

        filhoEsquerdo->pai = avo;

        if (avo) {
            if (avo->esquerda == pai) {
                avo->esquerda = filhoEsquerdo;
            } else {
                avo->direita = filhoEsquerdo;
            }
        } else {
            _raiz = filhoEsquerdo;
        }
    }

    void rotacionarEsquerda(No* pai) {
        No* filhoDireito = pai->direita;
        No* netoEsquerdo = filhoDireito->esquerda;

        No* avo = pai->pai;

        pai->direita = netoEsquerdo;
        if (netoEsquerdo) {
            netoEsquerdo->pai = pai;
        }

        filhoDireito->esquerda = pai;
        pai->pai = filhoDireito;

        filhoDireito->pai = avo;

        if (avo) {
            if (avo->esquerda == pai) {
                avo->esquerda = filhoDireito;
            } else {
                avo->direita = filhoDireito;
            }
        } else {
            _raiz = filhoDireito;
        }
    }

    void balancear(No* novoNo) {
        novoNo->cor = VERMELHO;
        while (novoNo != _raiz && novoNo->pai->cor == VERMELHO) {
            No* pai = novoNo->pai;
            No* avo = pai->pai;

            if (avo->esquerda == pai) {
                No* tio = avo->direita;

                if (tio && tio->cor == VERMELHO) {
                    pai->cor = PRETO;
                    tio->cor = PRETO;
                    avo->cor = VERMELHO;
                    novoNo = avo;
                } else {
                    if (novoNo == pai->direita) {
                        rotacionarEsquerda(pai);
                        novoNo = pai;
                        pai = novoNo->pai;
                    }
                    rotacionarDireita(avo);
                    pai->cor = PRETO;
                    avo->cor = VERMELHO;
                }
            } else {
                No* tio = avo->esquerda;

                if (tio && tio->cor == VERMELHO) {
                    pai->cor = PRETO;
                    tio->cor = PRETO;
                    avo->cor = VERMELHO;
                    novoNo = avo;
                } else {
                    if (novoNo == pai->esquerda) {
                        rotacionarDireita(pai);
                        novoNo = pai;
                        pai = novoNo->pai;
                    }
                    rotacionarEsquerda(avo);
                    pai->cor = PRETO;
                    avo->cor = VERMELHO;
                }
            }
        }
        _raiz->cor = PRETO;
    }

    No* _raiz;
};

Testando o Código

Segue um exemplo de teste para as estruturas implementadas:

#define _CRT_SECURE_NO_WARNINGS 1

#include "Mapa.h"
#include "Conjunto.h"
#include <iostream>

void testeMapa() {
    int valores[] = {5, 3, 7, 3, 7, 8, 4, 2, 9, 10};
    Mapa<int, int> mapa;

    for (int valor : valores) {
        mapa.inserir(std::make_pair(valor, valor));
    }

    mapa.percorrerEmOrdem();
}

void testeConjunto() {
    int valores[] = {5, 3, 7, 3, 7, 8, 4, 2, 9, 10};
    Conjunto<int> conjunto;

    for (int valor : valores) {
        conjunto.inserir(valor);
    }

    conjunto.percorrerEmOrdem();
}

int main() {
    testeMapa();
    return 0;
}