الوصف: |
When having undergraduate data structure courses, we discovered that after learning STL containers, students still don’t fully understand how does STL works, the characteristic of different containers, and how computer architecture can influence the performance of STL containers. In order to help students to have a better understanding of STL containers, and learn more about how the memory and cache will influence the performance of containers, so that storing, searching and sorting can be done more efficiently when facing different kinds of restrictions such as limited time and memory, this paper gives an introduction to the implementation of the seven popular STL containers, which are vector, list, deque, set, map, unordered_set, and unordered_map. The performance of insertion, searching, and sorting of them is tested with different sizes of data. After the test, we analyze the result from the perspective of the memory hierarchy. According to the experiments, vector has the fastest insertion speed; Among the three sortable containers, the sorting performance of vector and deque are very close, while list is much slower. Among set, map, unordered_set, unordered_map and unordered_set possess the best searching performance. Based on the test results, we offer some suggestions on how to choose a container for different requirements. |