C++

Forum

 
Iterators

stoneJax (260)
I have to rewrite some code using iterators. The code will reorganize names and scores into descending order. I have gotten a start on it but am feeling lost.

Given code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
 void sortData(Highscore highScores[], int size) {
    int largestIndex;
    Highscore tempRecord;
    
    for (int count = 0; count < size - 1; count++){
        largestIndex = indexOfLargest(highScores, count, size);
        tempRecord = highScores[largestIndex];
        highScores[largestIndex] = highScores[count];
        highScores[count] = tempRecord;
    }
}





int indexOfLargest(const Highscore highScores[], int startingIndex, int size){
    int targetIndex = startingIndex;
    
    for (int count = startingIndex + 1; count < size; count++){
        if (highScores[count].score > highScores[targetIndex].score){
            targetIndex = count;
        }
    }
    return targetIndex;
}


My code so far:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

const int MAX_NAMESIZE = 24;

struct Highscore {
	char name[MAX_NAMESIZE];
	int score;
};

void getArraySize(size_t& numberOfScores);
void readData(vector<Highscore>& scores);
void sortData(vector<Highscore>& scores);
int indexOfLargest(const vector<Highscore>& scores);

int main()
{
	size_t numberOfScores = 0;

	getArraySize(numberOfScores);
	vector<Highscore> scores(numberOfScores);
	readData(scores);

	system("pause");
}




void sortData(vector<Highscore>& scores) 
{
	int largestIndex;
	Highscore tempRecord;

	for (vector<Highscore>::iterator i = scores.begin(); i != scores.end(); i++) {
		largestIndex = indexOfLargest(scores, i);
		tempRecord = highScores[largestIndex];
		highScores[largestIndex] = highScores[count];
		highScores[count] = tempRecord;
	}
}





int indexOfLargest(const vector<Highscore>& scores) {
	int targetIndex = startingIndex;

	for (int count = startingIndex + 1; count < size; count++) {
		if (highScores[count].score > highScores[targetIndex].score) {
			targetIndex = count;
		}
	}
	return targetIndex;
}
rjphares (136)
This might not be what you want. Also, this site has some good references on Iterators. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include <map>
#include <string>

#include <iostream>


int main()

{

	std::map<std::string, int> Map;

	Map.insert(std::pair<std::string, int>("Player1",1000));
	Map.insert(std::pair<std::string, int>("Player2",800));
	std::map<std::string, int>::iterator mi;
	for (mi = Map.begin(); mi != Map.end(); mi++)
	{
		std::cout << mi->first << " " << mi->second << std::endl;
	}

	return 0;

}

keskiverto (10363)
Explain "have to".
1
2
3
4
5
6
7
8
9
10
 
int main()
{
	size_t numberOfScores = 0;
	getArraySize( numberOfScores );
	vector<Highscore> scores( numberOfScores );
	readData( scores );
	std::sort( scores.begin(), scores.end(),
		  []( const Highscore& lhs, const Highscore& rhs ){return lhs.score > rhs.score;}
		);
}

The C++ Standard Library algorithm std::sort is an example that does take iterators as parameters and hence "uses iterators".

I think your "sort" attempts to be conceptually similar to:
1
2
3
4
5
6
7
 
for ( auto i = scores.begin(); (i+1) != scores.end(); ++i )
{
	auto large = std::max_element( i+1, scores.end() );
	if ( i->score < large->score ) {
		std::iter_swap( i, large );
	}
}

You can find the description of those standard library algorithms.
Last edited on
stoneJax (260)
This is one part of a program that is given by the instructor for an online class. The given code is a pre-existing algorithm given to us, and the instructor wants us to practice using iterators. I'll post the instructions below.

Instructions regarding these two functions:

You could sort the scores by simply calling the STL sort() algorithm. I would suggest that you try this out because it's something you should know, but for your submitted program you are required to sort the vector as it is done in the given code, except using iterators to access the items in the vector.

Regarding the indexOfLargest() function, you may run into some const/non-const difficulties. The function needs to return a regular iterator (so that the calling function can use it to modify the vector). But the vector passed into the function should be const, which means the iterator passed into the vector should be a const_iterator. But that makes it impossible to return a non-const iterator. To solve this we will have to make the second parameter a regular iterator, even though it could be used to modify the const vector.
stoneJax (260)
I haven't seen "map" yet. I'll have to look int that.

I appreciate the sort example because I want to practice that.
JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
#include <iostream>
#include <vector>
#include <iomanip>

struct name_and_score {

    static const int MAX_NAMESIZE = 24 ;

    char name[MAX_NAMESIZE] = "" ;
    int score = 0 ;
};

// return iterator 'pointing to' the highest score in the range [ from, scores.end() )
// invariant: from < scores.end
// we grit our teeth and adhere to this horrible career-teacher style hack
// 'To solve this we will have to make the second parameter a regular iterator,
//                    even though it could be used to modify the const vector.'
auto iter_to_highest_score( const std::vector<name_and_score>& scores,
                            std::vector<name_and_score>::iterator from ) {

    auto iter_to_highest = from ;

    for( auto iter = ++from ; iter != scores.end() ; ++iter )
        if( iter_to_highest->score < iter->score ) iter_to_highest = iter ;

    return iter_to_highest ;
}

// swap items 'pointed to' by the two iterators
// see: std::iter_swap https://en.cppreference.com/w/cpp/algorithm/iter_swap
void swap_indirect( std::vector<name_and_score>::iterator first,
                    std::vector<name_and_score>::iterator second )
{
    const name_and_score temp = *first ;
    *first = *second ;
    *second = temp ;
}

void sortData( std::vector<name_and_score>& scores ) { // iterative selection sort

    for( auto iter = scores.begin() ; iter != scores.end() ; ++iter )
        swap_indirect( iter, iter_to_highest_score( scores, iter ) ) ;
}

void displayData( const std::vector<name_and_score>& scores ) { // note: const

    // You must use iterators wherever possible to access the vector.
    for( auto iter = scores.begin() ; iter != scores.end() ; ++iter ) {

        std::cout << std::setw(name_and_score::MAX_NAMESIZE) << iter->name
                  << " : " << std::setw(3) << iter->score << '\n' ;
    }
}

int main() {

    std::vector<name_and_score> scores { {"abcd",23}, {"efgh",69}, {"ijkl",82}, {"mnop",41},
                                         {"qrst",71}, {"uvwx",18}, {"yzab",99}, {"cdef",31} };

    std::cout << "---- original -----\n" ;
    displayData(scores) ;

    std::cout << "\n---- sorted -----\n" ;
    sortData(scores) ;
    displayData(scores) ;
}

http://coliru.stacked-crooked.com/a/da4507340b03aa74
https://rextester.com/XQR29656
stoneJax (260)
Thank you. I am going over things, digesting it and making sense of it all. Would you be able to tell me what the difference is between the style of iterator that you use, compared to the style that the instructor is using.

 
 
for( auto iter = scores.begin() ; iter != scores.end() ; ++iter )


 
 
for (vector<Highscore>::iterator i = scores.begin(); i != scores.end(); i++)
JLBorges (13770)
stoneJax (260)
Okay thank you. I'll do some reading up on that.

Here is what I have for these two functions at the moment. I am getting an error in the indexOfLargest function under the return statement.

Error:

Severity Code Description Project File Line Suppression State
Error (active) E0413 no suitable conversion function from "std::_Vector_iterator<std::_Vector_val<std::conditional_t<true, std::_Simple_types<Highscore>, std::_Vec_iter_types<Highscore, size_t, ptrdiff_t, Highscore *, const Highscore *, Highscore &, const Highscore &>>>>" to "int" exists Project27
Severity Code Description Project File Line Suppression State
Error C2440 'return': cannot convert from 'std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>' to 'int' Project27 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
void sortData(vector<Highscore>& scores)
{
	int largestIndex;
	Highscore hold;

	for (vector<Highscore>::iterator i = scores.begin(); i != scores.end(); i++)
	{
		largestIndex = indexOfLargest(scores, i);
		
	}


}

int indexOfLargest(const vector<Highscore>& scores, vector<Highscore>::iterator from)
{
	vector<Highscore>::iterator indexOfHighestValue = from;

	for (vector<Highscore>::iterator i = ++from; i != scores.end(); from++){

		if (indexOfHighestValue->score)
			indexOfHighestValue = from;
	}
	return indexOfHighestValue;
}
keskiverto (10363)
Your variable indexOfHighestValue has type vector<Highscore>::iterator
You return its value from the function (line 24).
However, you say that the function returns int (line 15).

How should the iterator be converted into integer? The compiler does not know. Hence the error.

Should the function return an integer, or perhaps an iterator?
stoneJax (260)
Thank you, that makes sense and I got that straightened out. Now, I am trying to get the sort data function to work with out a helper swap function. I was able to do it with the helper function but I am trying to keep the code closer to what the instructor is requiring as he says it is supposed to be like his code but with using iterators.

Instructors code:
1
2
3
4
5
6
7
8
9
10
11
 
void sortData(Highscore highScores[], int size) {
    int largestIndex;
    Highscore tempRecord;
    
    for (int count = 0; count < size - 1; count++){
        largestIndex = indexOfLargest(highScores, count, size);
        tempRecord = highScores[largestIndex];
        highScores[largestIndex] = highScores[count];
        highScores[count] = tempRecord;
    }
}


My code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
void sortData(vector<Highscore>& scores)
{
	vector<Highscore>::iterator hold;
	vector<Highscore>::iterator second;

	for (vector<Highscore>::iterator first = scores.begin(); first != scores.end(); first++)
	{
		second = indexOfLargest(scores, first);
		hold = first;
		first = second;
		second = hold;
		//swap(first, indexOfLargest(scores, first));

	}
}


JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
#include <iostream>
#include <vector>
#include <iomanip>

struct name_and_score {

    static const int MAX_NAMESIZE = 24 ;

    char name[MAX_NAMESIZE] = "" ;
    int score = 0 ;
};

// return iterator 'pointing to' the highest score in the range [ from, scores.end() )
// invariant: from < scores.end
// we grit our teeth and adhere to this horrible career-teacher style hack
// 'To solve this we will have to make the second parameter a regular iterator,
//                    even though it could be used to modify the const vector.'
auto iter_to_highest_score( const std::vector<name_and_score>& scores,
                            std::vector<name_and_score>::iterator from ) {

    auto iter_to_highest = from ;

    for( auto iter = ++from ; iter != scores.end() ; ++iter )
        if( iter_to_highest->score < iter->score ) iter_to_highest = iter ;

    return iter_to_highest ;
}

void sortData( std::vector<name_and_score>& scores ) { // iterative selection sort

    for( auto iter = scores.begin() ; iter != scores.end() ; ++iter ) {

        // swap_indirect( iter, iter_to_highest_score( scores, iter ) ) ;
        // this is implemented inline below.

        // get an iterator to the element with the highest score
        const auto iter_highest = iter_to_highest_score( scores, iter ) ;

        if( iter_highest != iter ) { // if it is not already at the beginning

            // bring it to the front by swapping the items (using the iterators)
            const name_and_score hold = *iter ;
            *iter = *iter_highest ;
            *iter_highest = hold ;
        }
    }
}

void displayData( const std::vector<name_and_score>& scores ) { // note: const

    // You must use iterators wherever possible to access the vector.
    for( auto iter = scores.begin() ; iter != scores.end() ; ++iter ) {

        std::cout << std::setw(name_and_score::MAX_NAMESIZE) << iter->name
                  << " : " << std::setw(3) << iter->score << '\n' ;
    }
}

int main() {

    std::vector<name_and_score> scores { {"abcd",23}, {"efgh",69}, {"ijkl",82}, {"mnop",41},
                                         {"qrst",71}, {"uvwx",18}, {"yzab",99}, {"cdef",31} };

    std::cout << "---- original -----\n" ;
    displayData(scores) ;

    std::cout << "\n---- sorted -----\n" ;
    sortData(scores) ;
    displayData(scores) ;
}

http://coliru.stacked-crooked.com/a/fa106006db277c6e
https://rextester.com/OCS15139
stoneJax (260)
Thank you guys for the help!
Topic archived. No new replies allowed.