Estruturas de dados imutáveis ​​de última geração

• vantagens arquitetônicas da imunidade;
• criação de um tipo de vetor persistente eficaz baseado em árvores RRB;
• análise da arquitetura no exemplo de um editor de texto simples.

A tragédia da arquitetura baseada em valor

const auto v0 = vector<int>{};

const auto v0 = vector<int>{};
const auto v1 = v0.push_back(15);
const auto v2 = v1.push_back(16);
const auto v3 = v2.set(0, 42);

assert(v2.size() == v0.size() + 2);
assert(v3[0] - v1[0] == 27);

Em busca de um vetor mágico

vector<int> myiota(vector<int> v, int first, int last)
{
    for (auto i = first; i < last; ++i)
        v = v.push_back(i);
    return v;
}

vector<int> myiota(vector<int> v, int first, int last)
{
    auto t = v.transient();
    for (auto i = first; i < last; ++i)
        t.push_back(i);
    return t.persistent();
}

vector<char> say_hi(vector<char> v)
{
    return v.push_back('h')        
            .push_back('i')        
            .push_back('!');       
}

vector<char> say_hi(vector<char> v)
{
    return v.push_back('h')        ⟵ named value: v
            .push_back('i')        ⟵ r-value value
            .push_back('!');       ⟵ r-value value
}

vector<int> myiota(vector<int> v, int first, int last)
{
    for (auto i = first; i < last; ++i)
        v = std::move(v).push_back(i);
    return v;
}

Ewig

Retornar à arquitetura baseada em valor

application update(application state, action ev);

void run(const char* fname)
{
    auto term  = terminal{};
    auto state = application{load_buffer(fname), key_map_emacs};
    while (!state.done) {
        draw(state);
        auto act = term.next();
        state = update(state, act);
    }
}

using index = int;

struct coord
{
    index row = {};
    index col = {};
};

using line = immer::flex_vector<char>;
using text = immer::flex_vector<line>;

struct file
{
    immer::box<std::string> name;
    text content;
};

struct snapshot
{
    text content;
    coord cursor;
};
 
struct buffer
{
    file from;
    text content;
    coord cursor;
    coord scroll;
    std::optional<coord> selection_start;
    immer::vector<snapshot> history;
    std::optional<std::size_t> history_pos;
};

struct application
{
    buffer current;
    key_map keys;
    key_seq input;
    immer::vector<text> clipboard;
    immer::vector<message> messages;
};

struct action { key_code key; coord size; };

Cancelar

buffer record(buffer before, buffer after)
{
    if (before.content != after.content) {
        after.history = after.history.push_back({before.content, before.cursor});
        if (before.history_pos == after.history_pos)
            after.history_pos = std::nullopt;
    }
    return after;
}

buffer undo(buffer buf)
{
    auto idx = buf.history_pos.value_or(buf.history.size());
    if (idx > 0) {
        auto restore = buf.history[--idx];
        buf.content = restore.content;
        buf.cursor = restore.cursor;
        buf.history_pos = idx;
    }
    return buf;
  }

Viagem no tempo

Resumir

Juan Puente falou na conferência C ++ Russia 2019 Moscow e falou sobre estruturas de dados que permitem fazer coisas interessantes. Parte da magia dessas estruturas está na elisão de cópias - é sobre isso que Anton Polukhin e Roman Rusyaev falarão na próxima conferência . Siga as atualizações do programa no site.