For some extensions to STL that have been proposed, the first major step would be to develop appropriate concepts.
NUMA iterators are a category of iterators that in addition to random iterator requirements provide an ability to access cache lines. They have an affiliated type LineIterator that allows a faster traversal within cache lines and a function cache_line that takes an iterator range and returns a range of LineIterators--the next cache line to be done. There is a prefetch function defined on LineIterators. Implement NUMA-iterator versions of important STL algorithms. Make deque iterators into NUMA-iterators. Implement cache line and prefetch for pointers.This problem, which Alex Stepanov proposed more than a year ago at SGI, was part of the stimulus for the development of hierarchical iterators.
See also the parallel algorithms project, which is predicated on solution of the NUMA-iterator problem.