Change search
ReferencesLink to record
Permanent link

Direct link
Representing sets in C++: A practical investigation
Norwegian University of Science and Technology, Faculty of Information Technology, Mathematics and Electrical Engineering, Department of Computer and Information Science.
2014 (English)MasteroppgaveStudent thesis
Abstract [en]

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.
URN: urn:nbn:no:ntnu:diva-24798Local ID: ntnudaim:10491OAI: diva2:720589
Available from: 2014-05-31 Created: 2014-05-31 Last updated: 2014-05-31Bibliographically approved

Open Access in DiVA

fulltext(978 kB)406 downloads
File information
File name FULLTEXT01.pdfFile size 978 kBChecksum SHA-512
Type fulltextMimetype application/pdf
cover(184 kB)17 downloads
File information
File name COVER01.pdfFile size 184 kBChecksum SHA-512
Type coverMimetype application/pdf
attachment(35 kB)14 downloads
File information
File name ATTACHMENT01.zipFile size 35 kBChecksum SHA-512
Type attachmentMimetype application/zip

By organisation
Department of Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 406 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 237 hits
ReferencesLink to record
Permanent link

Direct link