[Bro] - set\table\vector types have a complexity of O(n) ?

Johanna Amann johanna at icir.org
Tue Apr 25 08:20:25 PDT 2017


On Tue, Apr 18, 2017 at 01:49:08PM +0200, Jan Grashöfer wrote:
> > Just wondering, sets\tables\vectors all have a read\write complexity of
> > O(n) ?
> > n - referring to the number of elements in the container.
> 
> If I am not mistaken, sets as well as tables are implemented as hash
> tables. Thus the average complexity for lookup and insert is O(1).
> Vectors are implemented using C++ vectors, I think. I.e., lookup would
> be O(1) while inserting depends on the context.

Just to (partially) confirm this - tables (and sets, which just are a
special case of tables) are implemented as hash-tables with O(1) for
insert/lookup. Bro has its own hash-table implementation and is not using
the STL for this.

Vectors are implemented using stl vectors; the complexity depends on the
implementation, but generally lookups should be O(1), and inserts can be
O(n) in the worst case, since they might require a copy of the whole data
structure, if additional space has to be allocated.

Johanna

> 
> Jan
> _______________________________________________
> Bro mailing list
> bro at bro-ids.org
> http://mailman.ICSI.Berkeley.EDU/mailman/listinfo/bro
> 


More information about the Bro mailing list