Representing sets in C++: A practical investigation
The standard C++ classes for storing ordered sets and maps were created at a time when the latencies of the memory hierarchy were not as dominant a factor of performance as they are today. Consequently, the restrictions placed on a conforming implementation of the C++ standard forces a design similar to a balanced binary search tree. These structures have many desirable qualities, but do not make effiecient use of the memory hierarchy.
This report presents alternative ordered set structures which conform to a subset of the C++ standard demands. Drawbacks and strengths of these alternative structures are discussed, and running time for a number of use cases, set sizes and element types is measured.
These experiments show that relaxing the requirements of the C++ standard ordered set definition can give large gains in performance.
Place, publisher, year, edition, pages
Institutt for datateknikk og informasjonsvitenskap , 2014. , 86 p.
IdentifiersURN: urn:nbn:no:ntnu:diva-24798Local ID: ntnudaim:10491OAI: oai:DiVA.org:ntnu-24798DiVA: diva2:720589
Hetland, Magnus Lie, Førsteamanuensis