5,321
edits
C++: Difference between revisions
→Associative Containers
| Line 549: | Line 549: | ||
===Associative Containers=== | ===Associative Containers=== | ||
Also known as maps or associative arrays. | Also known as maps or associative arrays. | ||
====std::set==== | |||
[https://en.cppreference.com/w/cpp/container/set reference]<br> | |||
<code>#include<set></code><br> | |||
This is a binary tree (likely red-black tree). You can assume <math>O(\log n)</math> operations. | |||
====std::map==== | |||
[https://en.cppreference.com/w/cpp/container/map reference]<br> | |||
<code>#include<map></code><br> | |||
This is a binary tree (likely red-black tree). You can assume <math>O(\log n)</math> operations. | |||
====std::unordered_set==== | ====std::unordered_set==== | ||
[https://en.cppreference.com/w/cpp/container/unordered_set reference]<br> | [https://en.cppreference.com/w/cpp/container/unordered_set reference]<br> | ||
<code>#include <unordered_set></code><br> | <code>#include <unordered_set></code><br> | ||
This is a hashset.<br> | This is a hashset. You can assume operations are <math>O(1)</math> on average and <math>O(N)</math> worst case.<br> | ||
<syntaxhighlight lang="cpp> | <syntaxhighlight lang="cpp> | ||
std::unordered_set<int> my_set; | std::unordered_set<int> my_set; | ||
| Line 565: | Line 576: | ||
====std::unordered_map==== | ====std::unordered_map==== | ||
[https://en.cppreference.com/w/cpp/container/unordered_map reference]<br> | |||
<code>#include<unordered_map></code><br> | <code>#include<unordered_map></code><br> | ||
This is a hashmap. You can assume operations are <math>O(1)</math> on average and <math>O(N)</math> worst case.<br> | |||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
std::unordered_map<int, std::string> my_map; | std::unordered_map<int, std::string> my_map; | ||