Início / coding / Perguntas / 76956150
Accepted
intrigued_66
Asked: 2023-08-23 02:53:08 +0800 CST

Recipiente STL/Boost como array, armazenando elementos em ordem de classificação, sem lacunas?

  • 772

Gostaria de inserir e 'excluir' elementos em uma matriz de tamanho fixo. Após cada operação os elementos estão ordenados e contíguos (sem lacunas).

O primeiro elemento será inserido no meio.

Existe algum contêiner existente (incluindo Boost) que faça isso? Posso escrever um pouco da lógica, mas certamente este deve ser um requisito incomum.

Posso adicionar um pouco da lógica adicional/não-vanilla no topo.

c++

2 respostas

  1. Duvido que alguém tenha essa estrutura específica pré-construída. A menos que você garanta que a maioria das inserções aconteça perto do final, o desempenho será péssimo. Mas é claro que esta garantia pode existir, por exemplo, ao construir iterativamente uma matriz esparsa.

    De qualquer forma, com boost::container::devectore std::upper_boundvocê tem tudo que precisa para torná-lo uma função de uma linha.

    #include <boost/container/devector.hpp>
#include <algorithm>
#include <cassert>
#include <random>


template<class T>
void insert(boost::container::devector<T>& vec, const T& val)
{ vec.insert(std::upper_bound(vec.begin(), vec.end(), val), val); }

int main()
{
    boost::container::devector<int> vec;
    std::default_random_engine rng;
    for(int i = 0; i < 100000; ++i)
        insert(vec, static_cast<int>(rng()));
    assert(std::is_sorted(vec.begin(), vec.end()));
}

    No entanto, dado o fraco desempenho, considere alternativas como std::mapou ordenar apenas no primeiro acesso se a estrutura for principalmente de leitura.

    • 2
  2. Best Answer

    Dê uma olhada em boost::container::flat_sete boost::container::flat_map.

    Por exemplo

    Ao vivo no Coliru

    #include <boost/container/flat_map.hpp>
#include <boost/container/static_vector.hpp>
#include <iostream>
#include <iomanip>

namespace bc = boost::container;

int main() {
    static const bc::flat_map<std::string_view, int> m{
        {"one", 111}, {"two", 222}, {"five", 555}, {"seven", 777}, {"nine", 999},
    };

    for (auto [k,v]: m) {
        std::cout << quoted(k) << " -> " << v << "\n";
    }
}

    Imprime o esperado

    "five" -> 555
"nine" -> 999
"one" -> 111
"seven" -> 777
"two" -> 222

    O mais interessante é que os iteradores são de acesso aleatório e, de fato, referem-se a índices adjacentes:

    auto one = m.find("one");
auto seven = m.find("seven");
for (auto it : {one, seven}) {
    std::cout << "index of " << quoted(it->first) << ": " << (it - m.begin()) << "\n";
}

std::cout << "one and seven are " << (seven - one) << " places apart\n";

    Impressões ao vivo no Coliru

    index of "one": 2
index of "seven": 3
one and seven are 1 places apart

    Estática/pré-alocação e otimizações

    Existem construtores/operações otimizados para adotar uma sequência ordenada conhecida:

    bc::flat_set<int> m;
m.adopt_sequence_equal(bc::ordered_unique_range, {111,222,555,777,999});

    Você pode até otimizá-los para tamanhos fixos/pequenos. Por exemplo, um mapa simples de tamanho estático com no máximo 10 entradas:

    namespace bc = boost::container;
template <typename K, typename V, typename Cmp = std::less<K>, typename Pair = std::pair<K const, V>>
using Map10 = bc::flat_map<K, V, Cmp, bc::static_vector<Pair, 10>>;

static Map10<std::string_view, int> const m{
    {"one", 111}, {"two", 222}, {"five", 555}, {"seven", 777}, {"nine", 999},
};

    Ainda funciona da mesma maneira .

    Isso tem zero alocações de tempo de execução.

    • 2

relate perguntas