Faz std::setarmazenar objetos em memória contígua como std::vector?
Não consegui encontrar isso na web, a cppreference não menciona detalhes sobre alocação de memória. Mas não consigo entender por que ela não pode usar memória contígua, daí a minha pergunta.
set::insertrequisitos: en.cppreference.com/w/cpp/container/set/insert "... Nenhum iterador ou referência é invalidado ...." para que ele não possa ser realocado quando precisa ser expandidostd::vector.std::seté claro, mas não é uma dessas coisas, que é a chave aqui.Respostas:
Não há garantia de que sim. Também na prática, não pode devido aos requisitos do contêiner. Portanto, não, ele não armazena objetos na memória contígua.
As referências aos elementos do conjunto devem permanecer válidas após a inserção e apagamento (exceto as referências ao elemento apagado). Este requisito é incompatível com a memória contígua.
Até onde eu sei, uma árvore de pesquisa equilibrada é a única estrutura de dados que pode ser implementada
std::set.fonte
insertcópia de todos os nós em um novo bloco maior para limitá-lo a apenas um bloco, caso o realloc no local falhe ou (típico para C ++) o alocador não suporte esse realloc.)Não é excluído explicitamente, embora certas restrições
std::settornem impossível o uso de memória contígua.Por exemplo,
set::insertpossui complexidade logarítmica enquantovector::insertrequer complexidade linear para embaralhar suas entradas. Tambémset::insertnão invalida os iteradores. Ambos os requisitos não podem ser cumpridos com memória contígua.fonte