cpp-data-structure-selection

Installation
SKILL.md

C++ Data Structure Selection

Use this skill to pick the container behind an operation so its work scales correctly with input size, and to decide whether an existing structure should change. The canonical fix is replacing a per-element linear scan that runs once per element — an O(n²) shape — with a structure that makes the inner step O(1) or O(log n): a hash map/set, a sorted vector with binary search, or a balanced tree. The opposite is also a finding: a heavyweight node-based container used for a handful of elements where a flat array or linear scan is faster and lighter.

The goal is a behavior-preserving change: same elements, same observable results and ordering guarantees, lower asymptotic or constant cost. This is design work — choosing the representation — not a local copy/move tweak.

UTILITY SKILL. INVOKES: read-only file access for supplied targets; no other tools or skills. FOR SINGLE OPERATIONS: use to judge one hot loop, one container choice, or one "should this be a map?" question.

This skill owns the algorithmic and data-structure question of which structure a collection should be. It is distinct from local source-level cost review (how a single value is copied, moved, or passed) and from in-memory layout review (how one type's members are ordered to shrink its footprint). When the finding is about which container makes an operation scale, it belongs here; when it is about copy/move/allocation cost of an already-chosen structure, or member padding of one type, it does not.

Scope

  • Use this skill for: a loop whose inner step scans a collection that grows with input (nested find/find_if/any_of/count, dedup by re-scanning the output, "is this already in the list" checks); choosing between linear scan over a contiguous array, hash map/set (unordered_map/unordered_set, boost::unordered_flat_map), sorted std::vector + std::lower_bound/std::ranges::binary_search, balanced tree (std::map/std::set), and a small fixed lookup table; deciding whether an associative container is worth its per-node allocation and pointer-chasing versus a flat structure; sizing the crossover point where one structure overtakes another.
  • Apply it to: per-request/per-connection/per-message code in a server (cost multiplies by concurrency and request rate), inner loops over caller-controlled or unbounded input, and any structure the user reports as "slow as N grows."
  • Keep the change behavior-preserving: same logical contents and the same ordering/iteration/stability guarantees the callers actually depend on. Only the representation changes.

DO NOT USE FOR:

Installs
2
GitHub Stars
2
First Seen
Jun 28, 2026