什么是快速查找最好的c + + stl容器？

我寻找具有快速查找时间的容器，我想在其中存储对象，如以下什么是快速查找最好的c + + stl容器？

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

容器应只存储唯一的元素，但是对于比较是否两个对象只相当于恒变量必须进行比较。

半的我试试，如果它是不是已经在我必须找到，如果它已经包含在容器访问一个元素时的容器和半插入元素的时间。

同样重要的他们应该不会有任何冲突，由于散列或者如果他们碰撞我必须能够同时插入的元素，也只找到一个元素，如果他们是平等的不仅是他们的哈希值。

有什么建议吗？

来源

2015-04-02 Sebastian

A 4-d矩阵（或放松你的限制） – 2015-04-02 12:56:32

你如何寻找你的结构？你比较所有的领域？ – NathanOliver 2015-04-02 13:00:50

可能我没有足够的内存用于整个4D矩阵。在实践中，它只会是一个稀疏矩阵 – Sebastian 2015-04-02 13:03:09

std::multimap

查找：O(log N)加是否存在针对该特定键的多个元件是线性的。

插入：O(log N)

似乎是查找和插入具有良好的操控性冲突的最平衡的速度。

来源

2015-04-02 14:06:33

std ::这样做的方式是根据上面的答案 - 从可变数据中分离不可变关键字，这是std::map或std::unordered_map的目的。

如果因为某些遗留原因绝对不能这样做，可以使用std::set并提供自定义less仿函数。或者您可以使用std::unordered_set，在这种情况下，您需要提供自定义的相等函数对象和自定义哈希对象。

由于C++ 11然而，要注意的是，std::set<>::iterator类型有const的语义（即指称是不可变的），所以你需要强制问题与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; 
}

来源

2015-04-02 14:43:21

什么是快速查找最好的c + + stl容器？

回答

相关问题