I posted the same question at StackOverflow then I got an advice to post it here.

Original question: https://stackoverflow.com/questions/49998297/fast-insert-unique-container

I have to store elements (struct State) in a 2D vector container and each element must be unique.

I store the elements like this:

std::vector<std::vector<std::unique_ptr<State>>> m_container;

And I have an insert function

bool insert(State && value, std::size_t deepness);

Which should inset 'value' into m_container[deepness] if the value is unique or the new deepness is smaller then the previous in which case I have to remove the previous State (return true is inserted).

I have multiple threads inserting at the same time, I already have an implementation but I not sure if it is the best so I am interested in a better and faster way for the insert or some improvements.

My implementation is rather long so I try to shrink it down while keeping the logic behind it.

other than the container I have multimap:

std::multimap<std::size_t, std::pair<std::size_t, std::size_t>> m_multimap;

key: hash of the state

pair_1: deepness

pair_2: the position of the State in m_container[deepness]

I have a lockless_queue of struct Temp (lockless_queue m_queue) I insert here first then to the container.

template<typename T>
class lockless_queue {
public:
    // storeing the elements
    struct node;
    struct node_ptr;

    // insert element
    template<typename... Args>
    void produce(Args&&... args);
    void produce(T && data);
    void produce(const T & data);

    // consume all elements form queue
    node_ptr consume_all();

    // queue is not empty
    operator bool() const;
};

struct Temp {
    std::unique_ptr<State> value;
    std::size_t hash;
    std::size_t deepness;
    bool exist = false;

    Temp(State * v, std::size_t hash, std::size_t deepness, bool exist);
    Temp(State && v, std::size_t deepness);

    Temp move() {
        return Temp(value.release(), hash, deepness, exist);
    }

    bool is_equal(const State & state) const;
    bool is_equal(State * state) const;
    bool is_equal(const Temp & other) const;
    bool is_equal(Temp * other) const;

    void swap(State && v, std::size_t d) {
        deepness = d;
        value.reset(new State(std::move(v)));
    }
};

The following function is the insert function which inserts to the locless_queue

bool pre_emplace(State && value, std::size_t deepness) {
    Temp temp(std::move(value), deepness);
    const auto range = m_multimap.equal_range(temp.hash);
    if (range.first == range.second) {
        m_queue.produce(std::move(temp));
        return true;
    } else {
        const auto & container = m_container;
        const auto it = std::find_if(range.first, range.second, [&temp, &container](const auto & iter) {
            return temp.is_equal(container[iter.second.first][iter.second.second].get());
        });
        if (it == range.second || deepness < it->second.first) {
            temp.exist = true;
            m_queue.produce(std::move(temp));
            return true;
        }
    }
    return false;
}

(some case the return true is invalid because the queue is not unique but it is not a problem, I only use the return value for estimating the number of inserted elements)

this function consumes the elements from the queue into a temporary multimap of hash and Temp

void m_finalize_cycle(std::multimap<std::size_t, Temp> & multimap) {
    auto head = m_queue.consume_all();
    auto node = head.ptr;
    while (node != nullptr) {
        if (node->data.value == false) { node = node->next;  continue; }
        auto & temp = node->data;
        const auto range = multimap.equal_range(temp.hash);
        if (range.first == range.second) {
            multimap.emplace(std::make_pair(temp.hash, temp.move()));
        } else {
            const auto it = std::find_if(range.first, range.second, [&temp](const auto & pair) {
                return temp.is_equal(pair.second.value.get());
            });
            if (it == range.second) {
                multimap.emplace_hint(range.first, std::make_pair(temp.hash, temp.move()));
            } else if (temp.deepness < it->second.deepness) {
                it->second.value.reset(temp.value.release());
                it->second.deepness = temp.deepness;
            }
        }
        node = node->next;
    }
}

and this function load all Temp value from the previous multimap into m_container

void m_finalize_write(std::multimap<std::size_t, Temp> & multimap) {
    for (auto &[hash, temp] : multimap) {
        if (temp.exist) {
            const auto range = m_multimap.equal_range(temp.hash);
            auto & container = m_container;
            const auto it = std::find_if(range.first, range.second, [&temp, &container](const auto & iter) {
                return temp.is_equal(container[iter.second.first][iter.second.second].get());
            });
            if (it != range.second) {
                m_container.at(it->second.first).at(it->second.second).reset(nullptr);
                m_multimap.erase(it);
            }
        } else {
        }
        // extend m_container
        extend_if_needed(temp.deepness);
        m_container.at(temp.deepness).push_back(std::move(std::unique_ptr<State>(temp.value.release())));
        m_multimap.emplace(hash, std::make_pair(temp.deepness, m_container[temp.deepness].size() - 1));
    }
}

while I insert elements I run the m_finalize_cycle in every 10 microseconds then if I finished with the inserts I call the m_finalize_write.

This implementation works fine for me but unfortunately, it is the slowest part of my code so I am interested in better ways.