0

I know how to use iterators on a surface level, but I am trying to understand how iterators work in relation to a container class such as vector.

According to why do we put :: (scope resoulation operator) before iterator?

std::vector is a class template in the std namespace, which makes std::vector<double> a class.

std::vector<T>::iterator is a nested type under std::vector<T>

From what I understand, the class template vector has a member of type iterator which it gets from the class template in #include <iterator>.

This is confusing because when I look in http://www.cplusplus.com/reference/iterator/iterator/ there is no const_iterator class template in #include <iterator> that I can see?

Community
  • 1
  • 1
csguy
  • 1,354
  • 2
  • 17
  • 37
  • https://en.cppreference.com/w/cpp/container/vector – macroland Dec 10 '19 at 07:53
  • _the class template `vector` has a member of type `iterator` which it gets from the class template in `#include `_ — This is incorrect. The member type `iterator` of `vector` is implementation-specified. It may even be an alias for `value_type*`. There is no requirement that `std::iterator` would need to be used here. – Daniel Langr Dec 10 '19 at 07:56
  • @DanielsaysreinstateMonica oh so some implementations do use the template from ? if not whats the purpose of the iterator class template in #include – csguy Dec 10 '19 at 08:00
  • 3
    it doesn't serve much purpose at all which is why its deprecated: https://en.cppreference.com/w/cpp/iterator/iterator – Alan Birtles Dec 10 '19 at 08:01
  • 2
    _some implementations do use the template from ``?_ You can check the source code of, e.g., [libstdc++](https://github.com/gcc-mirror/gcc/tree/master/libstdc%2B%2B-v3), [libc++](https://github.com/llvm-mirror/libcxx), or [Microsoft's](https://github.com/microsoft/STL). But I don't think so; as Alan pointed out, `std::iterator` is now deprecated since C++17. – Daniel Langr Dec 10 '19 at 08:02
  • so is iterator just a user defined type with the name "iterator" that is implemented in containers? – csguy Dec 10 '19 at 08:06
  • 2
    @csguy Not necessarily. As I pointed out, it may be a _type alias_ for _pointer-to-value-type_ as well. However, AFAIK, C++ Standard Library implementations define their own classes-types for container iterators. – Daniel Langr Dec 10 '19 at 08:09
  • 2
    There is nothing in the specification of `std::vector` that says `vector::iterator` or `vector::const_iterator` have any particular relationship to `std::iterator` (even in standards predating deprecation of `std::iterator`). Also, although `iterator` and `const_iterator` are types declared in the scope of `vector`, there is no requirement that `vector` have a member of either type - `iterator` and `const_iterator` are part of the interface of `std::vector` e.g. overloads of the member `begin()` returns those types, but nothing is said about how those function obtain the iterator they return. – Peter Dec 10 '19 at 08:24
  • @ThomasSablik No. a `const_iterator` gives you a `T const`. A `const iterator` gives you a `T` but you may not use the iterator to iterate, since its is const. so basically useless :D – phön Dec 10 '19 at 08:38
  • @Peter there are no requirements for iterator and const_iterator members in container classes? – csguy Dec 10 '19 at 08:42
  • 2
    @csguy There is a requirement for a `begin` and `end` function that returns iterators (or raw pointers as that satisfies the requirements for an iterator). There is nothing that says the iterator needs to be implemented in the container. – super Dec 10 '19 at 08:46
  • @super is it a requirement for that iterator to have the name "iterator" hence why the `std::container::iterator` syntax works in something like `std::container::iterator i = container.begin()` – csguy Dec 10 '19 at 09:39
  • 1
    @csguy If you look at [std::vector](https://en.cppreference.com/w/cpp/container/vector) for example, you see that there is a list of member types.Includes `iterator`, `const_iterator` and `value_type` among others. Usually they are type aliases, `using iterator = ...;` defined inside the class. – super Dec 10 '19 at 09:43
  • @super hmm I see ...so containers define those member types usually with type alias for something like LegacyRandomAccessIterator which is "A pointer to an element of an array satisfies all requirements of LegacyRandomAccessIterator" – csguy Dec 10 '19 at 09:53
  • 2
    Yes. But `LegacyRandomAccesIterator` is an [iterator category](https://en.cppreference.com/w/cpp/named_req/Iterator). A pointer satisfies the requirements of a `LegacyRandomAccesIterator`. – super Dec 10 '19 at 10:09
  • Note: an example of container that doesnt have iterators is std::pair – csguy Dec 13 '19 at 04:06

1 Answers1

0

Gathered information from the comments:

  • std::iterator from #include <iterator> is deprecated as of C++17

  • Before it was deprecated, it was possible for STL containers (which are implementation defined) to implemented iterators with the help of the std::iterator template class.

  • For vector for example:

    There is nothing in the specification of std::vector that says vector::iterator or vector::const_iterator have any particular relationship to std::iterator (even in standards predating deprecation of std::iterator). Also, although iterator and const_iterator are types declared in the scope of vector, there is no requirement that vector have a member of either type - iterator and const_iterator are part of the interface of std::vector e.g. overloads of the member begin() returns those types, but nothing is said about how those function obtain the iterator they return

  • What is and isn't required in a STL container is:

    "a begin and end function that returns iterators (or raw pointers as that satisfies the requirements for an iterator). There is nothing that says the iterator needs to be implemented in the container."

  • STL containers define those member types (iterator, const_iterator, etc) usually with type alias for some iterator category like LegacyRandomAccessIterator which defined as "A pointer to an element of an array satisfies all requirements of LegacyRandomAccessIterator".

csguy
  • 1,354
  • 2
  • 17
  • 37