C++: How to Iterate the Elements over the Sets (set, unordered_s

  • Time：2020-09-11 08:17:29
  • Class：Weblog
  • Read：23

In C++, we use set, multiset, unordered_multiset, unordered_set to store a hash set. C++ set/multiset implements a Red-Black tree that maintains the order of the elements. On the other hand, the unordered_set and unordered_multiset are based on Hashmap/Hashtable thus the elements are not sorted.

The multiset and unordered_multiset allows storing the duplicates in the set. To iterate over the sets, we can just use the simple for loop:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <iostream>
#include <unordered_set>
 
using namespace std;
 
int main() {
    unordered_set<int> data;
    data.insert(5);
    data.insert(3);
    data.insert(2);
    data.insert(3);
    data.insert(6);
    data.insert(7);
    for (const auto &n: data) {
        cout << n << endl;
    }
    return 0;
}
#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
	unordered_set<int> data;
	data.insert(5);
	data.insert(3);
	data.insert(2);
	data.insert(3);
	data.insert(6);
	data.insert(7);
	for (const auto &n: data) {
		cout << n << endl;
	}
	return 0;
}

Duplicates are stored only once. And the unordered_set does not sort the elements. Thus you may see different order e.g. 7 6 2 5 3.

Iterating over the C++ set is similar. The output shows that elements are ordered. The C++ set O(logN) update/insert/delete/query is slower than unordered_set which has O(1) constant complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <iostream>
#include <set>
 
using namespace std;
 
int main() {
    set<int> data;
    data.insert(5);
    data.insert(3);
    data.insert(2);
    data.insert(3);
    data.insert(6);
    data.insert(7);
    for (const auto &n: data) {
        cout << n << endl; // prints 2 3 5 6 7
    }
    return 0;
}
#include <iostream>
#include <set>

using namespace std;

int main() {
	set<int> data;
	data.insert(5);
	data.insert(3);
	data.insert(2);
	data.insert(3);
	data.insert(6);
	data.insert(7);
	for (const auto &n: data) {
		cout << n << endl; // prints 2 3 5 6 7
	}
	return 0;
}

For multiset and unordered_multiset, iterating over the elements are similar except that the results will print the duplicates.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <iostream>
#include <set>
 
using namespace std;
 
int main() {
    multiset<int> data;
    data.insert(5);
    data.insert(3);
    data.insert(2);
    data.insert(3);
    data.insert(6);
    data.insert(7);
    for (const auto &n: data) {
        cout << n << endl; // prints 2 3 3 5 6 7
    }
    return 0;
}
#include <iostream>
#include <set>

using namespace std;

int main() {
	multiset<int> data;
	data.insert(5);
	data.insert(3);
	data.insert(2);
	data.insert(3);
	data.insert(6);
	data.insert(7);
	for (const auto &n: data) {
		cout << n << endl; // prints 2 3 3 5 6 7
	}
	return 0;
}

Note that the C++ multiset is included in set header and unordered_multiset is provided in unordered_set header.

Alternatively, we can increment the iterator to start from begin() to end() of the sets: (set, multiset, unordered_set, and unordered_multiset). We use *it to de-reference the iterator pointer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <iostream>
#include <set>
 
using namespace std;
 
int main() {
    multiset<int> data;
    data.insert(5);
    data.insert(3);
    data.insert(2);
    data.insert(3);
    data.insert(6);
    data.insert(7);
    for (auto it = begin(data); it != end(data); it ++) {
        cout << *it << endl; // prints 2 3 3 5 6 7
    }
    return 0;
}
#include <iostream>
#include <set>

using namespace std;

int main() {
	multiset<int> data;
	data.insert(5);
	data.insert(3);
	data.insert(2);
	data.insert(3);
	data.insert(6);
	data.insert(7);
	for (auto it = begin(data); it != end(data); it ++) {
		cout << *it << endl; // prints 2 3 3 5 6 7
	}
	return 0;
}

–EOF (The Ultimate Computing & Technology Blog) —

Recommend：
Harddrives will fail – it is just a matter of when
Bruteforce/DFS/Backtracking Algorithm using Javascript to Solve
DFS and BFS Algorithm to Find Numbers With Same Consecutive Diff
How to Remove Items/Entries with Specific Values from Map/HashMa
Find the Real Root of 4^x + 6^x = 9^x
Depth First Search (Backtracking) Algorithm to Solve a Sudoku Ga
Using Bitmasking Algorithm to Compute the Combinations of an Arr
Flashing the BIOS of HPZ800 Server to 3.61 Rev.A
Algorithm to Sum The Fibonacci Numbers
How to Adapt Your Blog to Increasing Zero-Click Searches
Share：Facebook Twitter
Comment list
Comment add