Iterator Concepts
What's the use of iterators? Why do generic algorithm parameters receive iterators?
Iterator iterator is one of the components of C++ STL. It is used to traverse containers and is a general way to traverse container elements. No matter what data structure the container is based on, although the way of traversing elements is different for different data structures, the code of traversing different containers with iterators is exactly the same. The classic iterator traverses the container as follows:
vector<int>::iterator it = vec.begin();
for (; it != vec.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
unordered_set<int>::iterator it = us.begin();
for (; it != us.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
In fact, the foreach statement of the new C++11 standard traverses the container through the iterator. If the container does not implement the iterator iterator, the foreach statement cannot traverse the container. The traversal code of the vector container above can be simplified as follows:
for (int val : vec)//It's actually traversing the container vec with an iterator
{
cout << val << " ";
}
cout << endl;
Iterators are generally implemented as nested types of containers and provide specific implementations inside containers. However, different containers have different ways of traversing the underlying elements, so why does the iterator traverse all containers in the same way?
That's because the iterator provides the commonly used operator! =, The overloaded functions of operators such as operator + +, operator * hide the details of iterative containers in these general operator overloaded functions. Therefore, the user side shows that the iterator traverses all containers in the same way. In fact, the bottom layer is different!
So you can answer the question at the beginning. The generic algorithm is a general algorithm implemented for many containers. It certainly needs a unified way to traverse the elements of the container. Only the iterator can do it!
iterator implementation
This section provides a minimalist implementation of the vector container, and then provides it with an implementation of the iterator iterator to see what the principle of the container iterator is. The space configurator of the container directly uses the allocator default implementation of the C + + standard library.
The following is the code implementation of the minimal vector container and iterator:
#include <iostream>
//For a simple vector container implementation, mainly view the implementation of its nested class iterator iterator
template<typename T,
typename Alloc = std::allocator<T>>
class MyVector
{
public:
MyVector(const Alloc& alloc = Alloc())
:_allocator(alloc)
{
_first._ptr = _last._ptr = _end._ptr = nullptr;
}
template<typename T>
void push_back(T&& val)
{
if (full())
resize();
_allocator.construct(_last._ptr, std::forward<T>(val));
_last._ptr++;
}
void pop_back()
{
if (empty())
return;
_last._ptr--;
_allocator.destroy(_last._ptr);
}
bool full()const { return _last._ptr == _end._ptr; }
bool empty()const { return _first._ptr == _last._ptr; }
//Implementation of container iterator
class iterator
{
public:
friend class MyVector;
iterator(T* ptr = nullptr)
:_ptr(ptr) {}
void operator++() { ++_ptr; }
bool operator!=(const iterator& it) { return _ptr != it._ptr; }
T& operator*() { return *_ptr; }
T* operator->() { return _ptr; }
private:
T* _ptr;
};
//The container's begin method returns the first element iterator
iterator begin() { return iterator(_first._ptr); }
//The end method of the container returns the iterator of the subsequent position of the last element
iterator end() { return iterator(_last._ptr); }
private:
iterator _first;//Points to the actual address of the array
iterator _last;//Points to the successor position of the last valid element
iterator _end;//Points to the subsequent position of the element at the end of the data space
Alloc _allocator;//Space configurator at the bottom of the container
//Expansion function of container
void resize()
{
if (_first._ptr == nullptr)
{
_first._ptr = _allocator.allocate(1);
_last._ptr = _first._ptr;
_end._ptr = _first._ptr + 1;
}
else
{
int size = _last._ptr - _first._ptr;
T* ptmp = _allocator.allocate(2 * size);
for (int i = 0; i < size; ++i)
{
_allocator.construct(ptmp + i, _first._ptr[i]);
_allocator.destroy(_first._ptr + i);
}
_allocator.deallocate(_first._ptr, size);
_first._ptr = ptmp;
_last._ptr = _first._ptr + size;
_end._ptr = _first._ptr + 2 * size;
}
}
};
As can be seen from the above code, the iterator of the container is implemented as a nested class type of the container, which provides operator overload functions commonly used in iterative containers. The container itself provides begin and end methods. Begin returns the iterator of the first element of the container, and end returns the iterator of the subsequent position of the element at the end of the container.
Container iterator failure
The problem of iterator failure of container is often considered. With the iteration of VS version, the iteration of g + + version, the source code of C + + standard library container and iterator have been greatly modified, but the essence of iterator failure can be summarized as follows:
1> Iterators of different containers cannot be compared
2> After the elements of the container are added and deleted, all the original iterators will become invalid
It can be clearly seen from the source code that the operator is performed in the two iterators iterator= The comparison operation will be carried out_ Compat's judgment:
const _Container_base12 *_Getcont() const noexcept
{ // get owning container
return (_Myproxy == nullptr ? nullptr : _Myproxy->_Mycont);
}
void _Compat(const _Vector_const_iterator& _Right) const
{ // test for compatible iterator pair
#if _ITERATOR_DEBUG_LEVEL == 0
(void)_Right;
#else /* ^^^ _ITERATOR_DEBUG_LEVEL == 0 ^^^ // vvv _ITERATOR_DEBUG_LEVEL != 0 vvv */
_STL_VERIFY(this->_Getcont() == _Right._Getcont(), "vector iterators incompatible");
#endif /* _ITERATOR_DEBUG_LEVEL == 0 */
}
When traversing the container with an iterator, the current iterator it will be judged every time= Whether container. End () has reached the end iterator of the container. After the above two conditions occur, here_ STL_ VERIFY(this->_Getcont() == _Right._Getcont(), “vector iterators incompatible”); This judgment fails. When the program runs, an error is reported, indicating that the iterator does not match, which means that the iterator fails!
What if the iterator fails?
The answer is to update the iterator in real time, as shown in the following code:
#include <vector>
#include <iostream>
int main()
{
std::vector<int> vec1;
for (int i = 0; i < 20; ++i)
{
vec1.push_back(rand() % 100);
}
//Delete all even numbers
auto it = vec1.begin();
while (it != vec1.end())
{
if (*it % 2 == 0)
{
//Here, the iterator should be updated in real time, otherwise the container element will change and the it iterator will fail!
it = vec1.erase(it);
}
else
{
++it;
}
}
for (int v : vec1)
{
std::cout << v << " ";
}
std::cout << std::endl;
return 0;
}
const_iterator implementation
const_ Compared with the above ordinary iterators, the iterator is readable and writable through the iterator, while const_ The iterator can only read container elements and cannot modify container elements. Const_ In terms of design, iterator generally exists as the base class of iterator, because an iterator object can initialize const_ Iterators, on the other hand, do not work. Their operations are almost the same, except for different read and write permissions.
Based on the above MyVector demonstration code, const is implemented_ Iterator constant iterator with the following code:
#include <iostream>
//For a simple vector container implementation, mainly view the implementation of its nested class iterator iterator
template<typename T,
typename Alloc = std::allocator<T>>
class MyVector
{
public:
MyVector(const Alloc& alloc = Alloc())
:_allocator(alloc)
{
_first._ptr = _last._ptr = _end._ptr = nullptr;
}
template<typename T>
void push_back(T&& val)
{
if (full())
resize();
_allocator.construct(_last._ptr, std::forward<T>(val));
_last._ptr++;
}
void pop_back()
{
if (empty())
return;
_last._ptr--;
_allocator.destroy(_last._ptr);
}
bool full()const { return _last._ptr == _end._ptr; }
bool empty()const { return _first._ptr == _last._ptr; }
//Implementation of container constant iterator
class const_iterator
{
public:
friend class MyVector;
const_iterator(T* ptr = nullptr)
:_ptr(ptr) {}
void operator++() { ++_ptr; }
bool operator!=(const const_iterator& it) { return _ptr != it._ptr; }
//The return value is modified by const. It can only be read and cannot be modified
const T& operator*()const { return *_ptr; }
const T* operator->()const { return _ptr; }
protected:
T* _ptr;
};
//Ordinary iterator inherits from const_iterator
class iterator : public const_iterator
{
public:
iterator(T* ptr = nullptr)
:const_iterator(ptr) {}
//The return type is a common reference of T & and is readable and writable
T& operator*() { return *const_iterator::_ptr; }
T* operator->() { return const_iterator::_ptr; }
};
//The container's begin method returns the first element iterator
iterator begin() { return iterator(_first._ptr); }
//The end method of the container returns the iterator of the subsequent position of the last element
iterator end() { return iterator(_last._ptr); }
//The constant object calls the constant begin and end methods to return a constant iterator, which can only read the container data and cannot be modified
const_iterator begin()const { return const_iterator(_first._ptr); }
const_iterator end()const { return const_iterator(_last._ptr); }
private:
iterator _first;//Points to the actual address of the array
iterator _last;//Points to the successor position of the last valid element
iterator _end;//Points to the subsequent position of the element at the end of the data space
Alloc _allocator;//Space configurator at the bottom of the container
//Expansion function of container
void resize()
{
if (_first._ptr == nullptr)
{
_first._ptr = _allocator.allocate(1);
_last._ptr = _first._ptr;
_end._ptr = _first._ptr + 1;
}
else
{
int size = _last._ptr - _first._ptr;
T* ptmp = _allocator.allocate(2 * size);
for (int i = 0; i < size; ++i)
{
_allocator.construct(ptmp + i, _first._ptr[i]);
_allocator.destroy(_first._ptr + i);
}
_allocator.deallocate(_first._ptr, size);
_first._ptr = ptmp;
_last._ptr = _first._ptr + size;
_end._ptr = _first._ptr + 2 * size;
}
}
};
You can write the following code to test. The constant iterator can only read and cannot be modified:
int main()
{
MyVector<int> vec;
for (int i = 0; i < 20; ++i)
{
vec.push_back(rand() % 100);
}
MyVector<int>::const_iterator cit = vec.begin();
for (; cit != vec.end(); ++cit)
{
std::cout << *cit << " ";//Here * cit cannot be assigned as an lvalue
}
std::cout << std::endl;
return 0;
}
reverse_iterator and Const_ reverse_ Design of iterator
In fact, the reverse iterator reverse_iterator and inverse constant iterator const_reverse_iterator is through the forward iterators iterator and const_ The iterator is implemented. The corresponding reverse iterator is obtained by instantiating the forward iterator. See the following code to demonstrate the implementation:
#include <iostream>
//Reverse iterator implementation
template<typename Iterator>
class _reverse_iterator
{
public:
using value_type = typename Iterator::value_type;
//Build a reverse iterator from a forward iterator
_reverse_iterator(Iterator it) :_it(it) {}
template<typename Other>
_reverse_iterator(const _reverse_iterator<Other>& src)
: _it(src._it) {}
bool operator!=(const _reverse_iterator<Iterator>& it)
{
return _it != it._it; // The actual call is still the operator of the forward iterator= function
}
void operator++() { --_it; }//The + + operation of the reverse iterator is the -- operation of the forward iterator
value_type& operator*() { return *_it; }
value_type* operator->() { return &(*this); }//Gets the address of the iterated element
private:
Iterator _it;//The reverse iterator relies on the forward iterator implementation of the container
template<typename Other>
friend class _reverse_iterator;
};
//For a simple vector container implementation, mainly view the implementation of its nested class iterator iterator
template<typename T,
typename Alloc = std::allocator<T>>
class MyVector
{
public:
//Type pre declaration
class const_iterator;
class iterator;
//Defines the type names of inverse iterators and inverse constant iterators
using reverse_iterator = _reverse_iterator<iterator>;
using const_reverse_iterator = _reverse_iterator<const_iterator>;
MyVector(const Alloc& alloc = Alloc())
:_allocator(alloc)
{
_first._ptr = _last._ptr = _end._ptr = nullptr;
}
template<typename T>
void push_back(T&& val)
{
if (full())
resize();
_allocator.construct(_last._ptr, std::forward<T>(val));
_last._ptr++;
}
void pop_back()
{
if (empty())
return;
_last._ptr--;
_allocator.destroy(_last._ptr);
}
bool full()const { return _last._ptr == _end._ptr; }
bool empty()const { return _first._ptr == _last._ptr; }
//Implementation of container constant iterator
class const_iterator
{
public:
using value_type = const T;
friend class MyVector;
const_iterator(T* ptr = nullptr)
:_ptr(ptr) {}
void operator++() { ++_ptr; }
void operator--() { --_ptr; }
bool operator!=(const const_iterator& it) { return _ptr != it._ptr; }
//The return value is modified by const. It can only be read and cannot be modified
const T& operator*()const { return *_ptr; }
const T* operator->()const { return _ptr; }
protected:
T* _ptr;
};
//Ordinary iterator inherits from const_iterator
class iterator : public const_iterator
{
public:
using value_type = T;
iterator(T* ptr = nullptr)
:const_iterator(ptr) {}
//The return type is a common reference of T & and is readable and writable
T& operator*() { return *const_iterator::_ptr; }
T* operator->() { return const_iterator::_ptr; }
};
//The container's begin method returns the first element iterator
iterator begin() { return iterator(_first._ptr); }
//The end method of the container returns the iterator of the subsequent position of the last element
iterator end() { return iterator(_last._ptr); }
//The constant object calls the constant begin and end methods to return a constant iterator, which can only read the container data and cannot be modified
const_iterator begin()const { return const_iterator(_first._ptr); }
const_iterator end()const { return const_iterator(_last._ptr); }
//rbegin returns the iterator representation of the last valid element
reverse_iterator rbegin() { return reverse_iterator(iterator(_last._ptr - 1)); }
//rend returns the leading position of the first element
reverse_iterator rend() { return reverse_iterator(iterator(_first._ptr - 1)); }
//rbegin returns the iterator representation of the last valid element
const_reverse_iterator rbegin()const { return const_reverse_iterator(iterator(_last._ptr - 1)); }
//rend returns the leading position of the first element
const_reverse_iterator rend()const { return const_reverse_iterator(iterator(_first._ptr - 1)); }
private:
iterator _first;//Points to the actual address of the array
iterator _last;//Points to the successor position of the last valid element
iterator _end;//Points to the subsequent position of the element at the end of the data space
Alloc _allocator;//Space configurator at the bottom of the container
//Expansion function of container
void resize()
{
if (_first._ptr == nullptr)
{
_first._ptr = _allocator.allocate(1);
_last._ptr = _first._ptr;
_end._ptr = _first._ptr + 1;
}
else
{
int size = _last._ptr - _first._ptr;
T* ptmp = _allocator.allocate(2 * size);
for (int i = 0; i < size; ++i)
{
_allocator.construct(ptmp + i, _first._ptr[i]);
_allocator.destroy(_first._ptr + i);
}
_allocator.deallocate(_first._ptr, size);
_first._ptr = ptmp;
_last._ptr = _first._ptr + size;
_end._ptr = _first._ptr + 2 * size;
}
}
};
The newly added code above is the code of the reverse iterator. You can install Beyond Compare software to compare the changes of the code and experience the excellent design of the reverse iterator. The code test is as follows:
int main()
{
MyVector<int> vec;
for (int i = 0; i < 20; ++i)
{
vec.push_back(rand() % 100);
}
//Forward traversal of container elements
auto it = vec.begin();
for (; it != vec.end(); ++it)
{
std::cout << *it << " ";
}
std::cout << std::endl;
//Reverse traversal of container elements
MyVector<int>::const_reverse_iterator rit = vec.rbegin();
for (; rit != vec.rend(); ++rit)
{
std::cout << *rit << " ";
// *rit = 20; An inverse constant iterator cannot modify the value of a container element
}
std::cout << std::endl;
return 0;
}
Insert insert iterator
The C + + standard library provides some insertion iterators, which are mainly used in generic algorithms to add elements to containers. The insertion row iterators are:
Example code:
#include <vector>
#include <list>
#Include < algorithm > / / include generic algorithms
#Include < iterator > / / contains all kinds of iterators
using namespace std;
int main()
{
vector<int> vec;
for (int i = 0; i < 20; ++i)
{
vec.push_back(rand() % 100);
}
vector<int> vec2;
//Through the back end insertion iterator, the elements of the VEC container are inserted into vec2 according to the end insertion mode
copy(vec.begin(), vec.end(), back_inserter(vec2));
for (int v : vec2)
{
cout << v << " ";
}
cout << endl;
list<int> mylist;
//Insert the elements of the vec container into the list container in reverse order
reverse_copy(vec.begin(), vec.end(), back_inserter(mylist));
for (int v : mylist)
{
cout << v << " ";
}
cout << endl;
return 0;
}
Stream Iterator
In C + +, whether it is a standard input / output stream, a file stream, or a character stream, it can also be regarded as a container. The C + + library provides a stream iterator. See the following code example:
#include <vector>
#include <list>
#include<iostream>
#Include < algorithm > / / include generic algorithms
#Include < iterator > / / contains all kinds of iterators
using namespace std;
int main()
{
vector<int> vec;
//Through the input stream iterator, the int is obtained from the standard input device and the header is inserted into the vec container
copy(istream_iterator<int>(cin), istream_iterator<int>(),
inserter(vec, vec.begin()));
vector<int> vec2;
copy(vec.begin(), vec.end(), back_inserter(vec2));
//Through the output stream iterator, the elements of the vec2 container are output to cout
copy(vec2.begin(), vec2.end(), ostream_iterator<int>(cout, " "));
cout << endl;
list<int> mylist;
reverse_copy(vec.begin(), vec.end(), back_inserter(mylist));
//Through the output stream iterator, the elements of the mylist container are output to cout
copy(mylist.begin(), mylist.end(), ostream_iterator<int>(cout, " "));
cout << endl;
return 0;
}
You can see that with the help of copy generic algorithm, insert row iterator and istream_iterator input stream iterator and ostream_iterator output stream iterator can easily carry out stream operation. File stream and string stream are the same.