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

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

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：
Summits set epoch-making milestone in history of China-Arab ties
In the face of COVID-19 pandemic, China and Arab countries have
15 Macao residents qualify as candidates for deputies to nationa
Study finds genetic solution to pre-harvest sprouting in rice, w
Bodybuilders dying as coaches, judges encourage extreme measures
Malta's Marsaskala, China's Dujiangyan sign sister city agreemen
U.S. mortgage applications continue slide amid surging interest
Russian, UAE presidents discuss bilateral cooperation over phone
Hate crimes in U.S. Los Angeles County rise to highest level sin
Chinese mainland reports 4,031 new local confirmed COVID-19 case
Share：Facebook Twitter
Comment list
Comment add