Representing sets in C++: A practical investigation

Abstract

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.