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