SortedVectorMap.h File Reference

This file implements a map backed by a sorted SmallVector. More...

#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Compiler.h"
#include <functional>
#include <tuple>
#include <utility>

Go to the source code of this file.

Classes
class	llvm::SortedVectorMap< KeyT, ValueT, N, KeyCompare >
	A map implementation backed by a sorted SmallVector. More...

Namespaces
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.

Detailed Description

This file implements a map backed by a sorted SmallVector.

It provides a std::map-like interface with binary search lookup while maintaining contiguous memory layout and dense cache locality.

SortedVectorMap is intended for:

• Small maps where memory footprint is a primary concern. In particular, it avoids the initial bucket overhead of DenseMap (e.g. 64 buckets by default) when only a few elements are stored.
• Use cases that require iteration in sorted key order.

Trade-offs:

• Lookups take O(log N) time via binary search rather than O(1) in DenseMap.
• Insertions and deletions take O(N) time due to shifting elements in the underlying vector, making it best suited for small N or mostly-read data.
• Compared to std::map, elements are stored contiguously, eliminating per-node heap allocations and pointer chasing.
• Compared to MapVector, elements are ordered by key rather than insertion order, with zero auxiliary hash table overhead.

Definition in file SortedVectorMap.h.