Underestimated iterators
It's about the standard library of templates STL. Existing iterator types and their classification will be reviewed, and several new wrappers over iterators will be proposed. Which will allow in some cases to avoid lambda expressions, which, as it were, there is no pre-C ++ 11.
One of the main paradigms of this library was the separation of two entities. Containers and algorithms. But for the direct effect of the algorithm on the data container had to enter an intermediate entity - an iterator.
Iterators allowed the algorithms to access the data contained in the container, regardless of the type of container. But for this, in each container, it was necessary to define an iterator class. Thus, algorithms act on data through iterators that are aware of the internal representation of the container.
')
In addition to the iterators accessing the data of a particular container, the STL library has several more iterators:
1. back_insert_iterator and front_insert_iterator
2. insert_iterator
3. istream_iterator and ostream_iterator
Iterators of the types back_insert_iterator and front_insert_iterator, when modifying the content, insert the element using the push_back () or push_front () method. Move operations to the previous / next element of the container are simply ignored by these iterators.
The insert_iterator iterator, when modified, inserts data. A container and an iterator are passed to it in the constructor to the position where the data should be inserted.
The istream_iterator and ostream_iterator iterators read data from a stream and write data to a stream. In the constructors of these iterators, it is necessary to transfer the input or output stream.
The existing classification of iterators includes 5 categories of iterators:
1. Input iterator
2. Output iterator
3. Forward iterator
4. Bidirectional iterator
5. Random access iterator
Iterators belonging to different categories have a different set of valid operations. Operations are categorized as follows:
To implement the following several ideas, it was necessary to implement a wrapper or wrapper . An iterator decorator must have the same category as the iterator being wrapped, and therefore provide the same set of methods. In accordance with the table of categories has been developed:
1. Five impurity classes ( mixin ) that implement non-intersecting sets of methods.
2. Template decorator class, parameterized by the iterator category.
3. Five specializations of the template, characterized by a set of admixed impurities .
4. Factory for convenient (without explicit template parameters) wrapping an iterator.
[You can take a look at this code here , it almost works]
After a brief discussion of the resulting structure with one good person, a new structure was developed. Not so saturated with patterns and more concise. It was decided to implement all the methods of all categories of iterators in a single template class, parameterized by the category of the iterator. The following property of the C ++ language was used: only those methods of the template class that are actually called are compiled.
Thus, if you need to wrap an iterator in the Input category, only those methods that are in the Input category and are called will be compiled. If you try to call a method that does not belong to this category, a compilation error will occur. And this is exactly what we wanted.
Bit iterator allows to bypass elements of containers bit by bit. The iterator can be used to both read and write bit values. The iterator has parameters:
1. In what order to bypass the container element bytes
2. In what order to bypass bits in bytes
Example of use:
A field iterator is an iterator, which, when dereferencing, returns the value of one of the structure fields. It can be very useful to search for an object by the value of one of the fields. Example of use:
The macro fieldof (Class, Field) looks like this:
UPD
As the user mayorovp noted , it was possible to get away with a pointer to the class field:
A sorting iterator is an iterator that performs a crawl of items in the order in which they are sorted. Container elements are not modified during the iteration process. The advantage in this case is that the time for sorting is not wasted (there is no certain portion of time allotted for sorting).
When the iterator moves to the next item, it searches for the smallest item among the remaining ones that are greater or equal to the previous one. Thus, the complexity of the algorithm is O (N 2 ), but there is no special time allocated for sorting. Sorting is done in the process of accessing data. Circulation through iterators is step by step - sorting is also step by step.
The iterator is parameterized by the sort order. Default: sort ascending.
Example of use:
1. The table of categories of iterators is borrowed from here (a couple of bugs were found in it - the source site was notified of errors): http://www.cplusplus.com/reference/std/iterator/
2. As many of you may have noticed, the code samples are tests for the Google C ++ Testing Framework , which means the code lies in the repository and there are tests for it. Find a bug - write a test that reveals it)) This is where all the code lies: http://code.google.com/p/stliw/ Comments on the code can be left without registration - welcome.
PS
This article was written by me six months ago. Today I discovered it in a nearly finished state and published it. It is difficult to say why she lay for six months in my drafts. Maybe I wanted to finish or redo something, in any case - I publish it now or never.
opening speech
One of the main paradigms of this library was the separation of two entities. Containers and algorithms. But for the direct effect of the algorithm on the data container had to enter an intermediate entity - an iterator.
Iterators allowed the algorithms to access the data contained in the container, regardless of the type of container. But for this, in each container, it was necessary to define an iterator class. Thus, algorithms act on data through iterators that are aware of the internal representation of the container.
')
Types of iterators in STL
In addition to the iterators accessing the data of a particular container, the STL library has several more iterators:
1. back_insert_iterator and front_insert_iterator
2. insert_iterator
3. istream_iterator and ostream_iterator
Iterators of the types back_insert_iterator and front_insert_iterator, when modifying the content, insert the element using the push_back () or push_front () method. Move operations to the previous / next element of the container are simply ignored by these iterators.
The insert_iterator iterator, when modified, inserts data. A container and an iterator are passed to it in the constructor to the position where the data should be inserted.
The istream_iterator and ostream_iterator iterators read data from a stream and write data to a stream. In the constructors of these iterators, it is necessary to transfer the input or output stream.
Iterator classification
The existing classification of iterators includes 5 categories of iterators:
1. Input iterator
2. Output iterator
3. Forward iterator
4. Bidirectional iterator
5. Random access iterator
Iterators belonging to different categories have a different set of valid operations. Operations are categorized as follows:
| Iterator Category | Characteristic | Valid expression | |||
|---|---|---|---|---|---|
| All categories | Can be copied and created in the image | X b (a); b = a; | |||
| Can be increased by one | ++ a a ++ * a ++ | ||||
| Random access | Bidirectional | Forward | Input | Supports equality / inequality comparison | a == b a! = b |
| May be derefered as an rvalue just to get the value | * a a-> m | ||||
| Output | May be dereferenced as an lvalue for use to the left of the assignment character. | * a = t * a ++ = t | |||
| Can be copied and used for re-traversal. | X a (b); ++ a == ++ b | ||||
| Can be reduced by one | --a a-- * a-- | ||||
| Supports arithmetic operations + and - | a + n n + a a - n a - b | ||||
| Supports comparisons (<,>, <= and> =) between iterators | a <b a> b a <= b a> = b | ||||
| Supports increment + = and decrement - = | a + = n a - = n | ||||
| Supports index dereferencing ([]) | a [n] | ||||
Development of an iterator decorator
To implement the following several ideas, it was necessary to implement a wrapper or wrapper . An iterator decorator must have the same category as the iterator being wrapped, and therefore provide the same set of methods. In accordance with the table of categories has been developed:
1. Five impurity classes ( mixin ) that implement non-intersecting sets of methods.
2. Template decorator class, parameterized by the iterator category.
3. Five specializations of the template, characterized by a set of admixed impurities .
4. Factory for convenient (without explicit template parameters) wrapping an iterator.
[You can take a look at this code here , it almost works]
After a brief discussion of the resulting structure with one good person, a new structure was developed. Not so saturated with patterns and more concise. It was decided to implement all the methods of all categories of iterators in a single template class, parameterized by the category of the iterator. The following property of the C ++ language was used: only those methods of the template class that are actually called are compiled.
Thus, if you need to wrap an iterator in the Input category, only those methods that are in the Input category and are called will be compiled. If you try to call a method that does not belong to this category, a compilation error will occur. And this is exactly what we wanted.
Bit iterator
Bit iterator allows to bypass elements of containers bit by bit. The iterator can be used to both read and write bit values. The iterator has parameters:
1. In what order to bypass the container element bytes
2. In what order to bypass bits in bytes
Example of use:
{ // 00001010 00001011 00001010 00001011 // * * * ** * * * ** char input[] = "\x0A\x0B\x0A\x0B"; char * input_ptr = input; int a = std::count(bit_walker(input_ptr), bit_walker(input_ptr+4), 1); EXPECT_EQ(2 + 3 + 2 + 3, a); } Field iterator
A field iterator is an iterator, which, when dereferencing, returns the value of one of the structure fields. It can be very useful to search for an object by the value of one of the fields. Example of use:
{ // What to find: [200] "puper" // // {100,"hello"} // {200,"super"} => {200,"super"} // {300,"puper"} => {300,"puper"} struct ABC { int value; std::string str; }; ABC input[] = { {100,"hello"}, {200,"super"}, {300,"puper"} }; ABC * input_ptr = input; int a = std::find(field_walker(input_ptr, fieldof(ABC,value)), field_walker(input_ptr+3, fieldof(ABC,value)), 200) - input_ptr; int b = std::find(field_walker(input_ptr, fieldof(ABC,str)), field_walker(input_ptr+3, fieldof(ABC,str)), "puper") - input_ptr; EXPECT_EQ(1, a); EXPECT_EQ(2, b); } The macro fieldof (Class, Field) looks like this:
#define fieldof(Object,field) (&(((Object*)NULL)->field)) UPD
As the user mayorovp noted , it was possible to get away with a pointer to the class field:
&Object::field Sorting iterator
A sorting iterator is an iterator that performs a crawl of items in the order in which they are sorted. Container elements are not modified during the iteration process. The advantage in this case is that the time for sorting is not wasted (there is no certain portion of time allotted for sorting).
When the iterator moves to the next item, it searches for the smallest item among the remaining ones that are greater or equal to the previous one. Thus, the complexity of the algorithm is O (N 2 ), but there is no special time allocated for sorting. Sorting is done in the process of accessing data. Circulation through iterators is step by step - sorting is also step by step.
The iterator is parameterized by the sort order. Default: sort ascending.
Example of use:
{ // A:{ 5,2,1,2,2 } => A:{ 5,2,1,2,2 } // B:{ 0,0,0,0,0 } => B:{ 5,2,2,2,1 } int input[5] = { 5,2,1,2,2 }; int output[5] = { 0,0,0,0,0 }; int * input_ptr = (int *)input; int * output_ptr = (int *)output; std::copy(sorter<Descending>(input_ptr,input_ptr+5), sorter<Descending>(input_ptr+5), output_ptr); // Expect input EXPECT_EQ(5, input[0]); EXPECT_EQ(2, input[1]); EXPECT_EQ(1, input[2]); EXPECT_EQ(2, input[3]); EXPECT_EQ(2, input[4]); // Expect output EXPECT_EQ(5, output[0]); EXPECT_EQ(2, output[1]); EXPECT_EQ(2, output[2]); EXPECT_EQ(2, output[3]); EXPECT_EQ(1, output[4]); } Notes:
1. The table of categories of iterators is borrowed from here (a couple of bugs were found in it - the source site was notified of errors): http://www.cplusplus.com/reference/std/iterator/
2. As many of you may have noticed, the code samples are tests for the Google C ++ Testing Framework , which means the code lies in the repository and there are tests for it. Find a bug - write a test that reveals it)) This is where all the code lies: http://code.google.com/p/stliw/ Comments on the code can be left without registration - welcome.
PS
This article was written by me six months ago. Today I discovered it in a nearly finished state and published it. It is difficult to say why she lay for six months in my drafts. Maybe I wanted to finish or redo something, in any case - I publish it now or never.
Source: https://habr.com/ru/post/122283/
All Articles