0

I learned it is different between random access iterator and bidirectional iterator. random access iterator can use +, -, += , -=, [] operator but bidirectional iterator can't. map use bidirectional iterator. But map still use [] operator.

for example:

map<int,int> a;
a[5]++;

it works well.

I don't understand what this do.

By any chance, can you tell me how?

Anchal Singh
  • 364
  • 4
  • 10
조민국
  • 89
  • 1
  • 4

2 Answers2

2

pointers support [], which is defined as p[i] being equivalent to *(p + i). RandomAccessIterators are things that behave like pointers, so they also support that, with the same meaning.

A number of containers also support []. Of these, there are two kinds.

The first kind are those SequenceContainers who's iterators are RandomAccessIterator, and the parameter to SequenceContainer::operator[] is std::size_t, i.e. something that identifies an element by it's position in the sequence. vec[i] is the same as vec.begin()[i] is the same as *(vec.begin() + i).

If you can easily find an element at a particular index, your iterators can easily be incremented or decremented by an offset larger than 1.

The second kind are those AssociativeContainers or UnorderedAssociativeContainerss that have a mapped_type. The parameter to AssociativeContainer::operator[] is AssociativeContainer::key_type, i.e. something that identifies an element by it's value.

Easily finding an element with a particular value doesn't help with moving along a sequence. It turns out that the currently known data-structures that allow easy access by value are not as good at knowing which element is n further along.

Caleth
  • 52,200
  • 2
  • 44
  • 75
  • @PeteBecker oops, fixed – Caleth Mar 01 '19 at 13:42
  • Thank you for your answer. Thanks to you, I know what I'm missing. – 조민국 Mar 01 '19 at 15:40
  • Sorry, didn't notice this before. Sequence containers don't categorically provide random access iterators. `std::list` provides bidirectional iterators, and `std::forward_list` provides forward iterators. The defining characteristic of a sequence container is that the you control the order of elements in the container; associative containers make their own decisions about the order. – Pete Becker Mar 01 '19 at 16:19
  • @PeteBecker Yes, there are other *SequenceContainer*s, which are only bidirectional (or forward), which is exactly the demarcation between "has []" and "lacks []" – Caleth Mar 01 '19 at 16:21
  • Oh, I see: you're restricting those paragraphs to containers that support []. Okay. – Pete Becker Mar 01 '19 at 16:22
  • Yes, also the *Associative*s that are map-like, rather than set-like. It would be nice if we had standardese for these subgroups, for situations like this. – Caleth Mar 01 '19 at 16:23
2

random access iterator can use +, -, += , -=, [] operator but bidirectional iterator can't.

That's an oversimplification, and you've discovered why.

A bidirectional iterator can't perform random access operations. For some containers, [] is a random access operation. It takes you some "distance" into the container.

For an associative container like a map, though, it isn't: it's an operation specifically designed for those containers. It takes a key and gives you a value. It's a different operation.

Try to think in terms of features and behaviours rather than of symbols, because symbols take different meanings depending on the context. If you want to learn what a symbol means in some given context, you can refer to a reference or to your book.

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • nitpick: "A bidirectional iterator" -> "something that is *only* bidirectional iterator", random access implies bidirectional – Caleth Mar 01 '19 at 13:48
  • 1
    @Caleth Granted. For this level of discussion I think I'll leave it alone, but if I can think of a way to describe that cascading property of iterator categories without confusing the heck out of the OP I may :) I personally wouldn't call a RA iterator "bidirectional" even though it does inherit the properties of a bidirectional iterator via the BidirectionalIterator category. Same way I wouldn't call a `float` an integer, even though it's capable of holding natural numbers. – Lightness Races in Orbit Mar 01 '19 at 13:49
  • Thank you. Thanks to your kind explanation, I could understand.I confused what is different between vector's [] and map's []. now, I clearly know what is diffrent. Please make sure I know exactly what you're saying. vector's [] operator is to return size and map's [] operator is to return value. right? if you say me "you are right", I can sleep. – 조민국 Mar 01 '19 at 15:42
  • @조민국 They both return a value ;) But they do it in different ways. Vector's requires "random access", whereas map's doesn't, because the ways of getting to the data are so different. – Lightness Races in Orbit Mar 02 '19 at 14:43