CODEWITHSUNDEEP
c++stl
Sebastian
Sebastian

Reputation: 11

Whats the best c++ stl container for fast lookup?

I search for a container which has a fast lookup time and I want to store objects in it like the following

class Flow{
const int L3Outside;
const int L4Protocol;
const int L4Oustside;
const int L4Inside;
time_t inOut;
time_t outIn;
}

The container should only store unique elements BUT for the comparision whether two objects are equal only the constant variables must be compared.

Half of the time I try to insert an element if it isn't already in the container and half of the time I have to find and access an element if it is already contained in the container.

Also important their shouldn't be any collisions due to hashing or if they are collisions I must be able to insert both elements and also find only an element if their are equal not only their hashes.

Any suggestions?

Upvotes: 0

Views: 4216

Answers (2)

Richard Hodges
Richard Hodges

Reputation: 69942

The std:: way to do this is as per the answer above - separate the immutable key from the mutable data, which is the purpose of a std::map or std::unordered_map.

If you absolutely cannot do this for some legacy reason, you can use a std::set and provide a custom less functor. Or you could use a std::unordered_set in which case you'd need to provide a custom equality function object and a custom hash object.

Since c++11 however, be aware that the std::set<>::iterator type has const semantics (i.e. referent is not mutable) so you will need to force the issue with a const_cast:

#include <iostream>
#include <set>
#include <tuple>
#include <utility>
#include <ctime>

struct compare_flow_less;

class Flow{
public:
    Flow(int l3o, int l4p, int l4o, int l4i, time_t io = 0, time_t oi = 0)
    : L3Outside { l3o }
    , L4Protocol { l4p }
    , L4Outside { l4o }
    , L4Inside { l4i }
    , inOut { io }
    , outIn { oi }
    {
    }    

    void set_times(time_t t1, time_t t2)
    {
        inOut = t1;
        outIn = t2;
    }

private:
    const int L3Outside;
    const int L4Protocol;
    const int L4Outside;
    const int L4Inside;
    time_t inOut;
    time_t outIn;

    friend compare_flow_less;
};

struct compare_flow_less
{
    bool operator()(const Flow&l, const Flow&r)
    {
        return l.L3Outside < r.L3Outside
        && l.L4Protocol < r.L4Protocol
        && l.L4Outside < r.L4Outside
        && l.L4Inside < r.L4Inside;
    }
};

using FlowSet = std::set<Flow, compare_flow_less>;

using namespace std;

int main()
{
    FlowSet myflows;

    // to insert/overwrite a flow
    time_t t1 = time(nullptr);
    time_t t2 = t1 + 1;

    bool inserted = false;
    FlowSet::iterator insert_position;

    // try to insert a new one
    tie(insert_position, inserted) = myflows.emplace(1,2,3,4,t1,t2);

    // if insertion failed, one already exists so update it
    if (!inserted) {
        const_cast<Flow&>(*insert_position).set_times(t1, t2);
    }

   return 0;
}

Upvotes: 0

Gilead Silvanas
Gilead Silvanas

Reputation: 97

std::multimap

Lookup: O(log N) plus linear if there are multiple elements for that specific key.

Insertion: O(log N)

Seems to be the most balanced speed for lookup and insertion with good handling of collisions.

Upvotes: 1

Related Questions