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

Hi all,

Just wondering, sets\tables\vectors all have a read\write complexity of O(n) ?

n - referring to the number of elements in the container.

Thanks

B

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.

Jan

> 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