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
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