Hey there. Does arithmetic operations on iterators work in O(n) ? Example: std::vector<int>::iterator

Question

C / C++

Sahand 🏔️

Hey there. Does arithmetic operations on iterators work in O(n) ? Example: std::vector<int>::iterator

it = v.begin();
it += 6;

Is "it += 6;" done in O(n) or constant time ?

0

22.01.2024

12 ответов

53 просмотра

Sahand 🏔️ Автор вопроса

Can anyone help out?

0

11 месяцев назад

Sahand 🏔️ Автор вопроса

²
i think its constant, just move address

So it's constant for std vector but for std list (that no random access is available) it'll be O(n) I think. Because the compiler says no operator '+=' is overloaded.

0

11 месяцев назад

²

Sahand 🏔️
So it's constant for std vector but for std list (...

as i know += from C++17

0

11 месяцев назад

²

Sahand 🏔️
So it's constant for std vector but for std list (...

oh, you right

0

11 месяцев назад

Sahand 🏔️ Автор вопроса

²

oh, you right

Which book is it

0

11 месяцев назад

²

Sahand 🏔️
Which book is it

0

11 месяцев назад

BinaryByter

²

oh, you right

Would be interesting to know if they give you any guarantees on complexity, but likely they won't

0

11 месяцев назад

Sahand 🏔️ Автор вопроса

BinaryByter
Would be interesting to know if they give you any ...

guarantees on the complexity of arithmetic operations on iterators?

0

11 месяцев назад

BinaryByter

Sahand 🏔️
guarantees on the complexity of arithmetic operati...

yea

0

11 месяцев назад

²

BinaryByter
Would be interesting to know if they give you any ...

🤷‍♂️

0

11 месяцев назад

Ihor

BinaryByter
Would be interesting to know if they give you any ...

You can see here that the operation on a random access I iterators is not O(1) while others iterators are O(n) https://en.cppreference.com/w/cpp/iterator/distance

0

11 месяцев назад

² · Accepted Answer

²

Sahand 🏔️
Can anyone help out?

i think its constant, just move address

0

11 месяцев назад

Похожие чаты

Hey there. Does arithmetic operations on iterators work in O(n) ? Example: std::vector<int>::iterator

12 ответов

Похожие вопросы