Date: 2026-01-16 Module: containers Purpose: Comprehensive guide to BELFEM's custom container classes and their usage Revision: 2026-01-16 - Initial version incorporating community feedback
Overview
The src/containers module provides custom wrapper classes around STL containers, designed to offer:
- Consistent interface across BELFEM codebase
- Enhanced error checking with bounds validation in debug mode
- Domain-specific functionality (e.g., genetic algorithms, shift registers, bitset operations)
- Performance optimizations for specific use cases
Most containers are header-only template classes. Exceptions: DynamicBitset and StringList have separate .cpp implementation files.
Critical: Debug vs. Release Behavior All BELFEM_ASSERT checks are compiled out in release builds (-DNDEBUG).
- Debug: Bounds checking, descriptive error messages
- Release: Zero overhead, but undefined behavior on violations (mirrors STL)
Common Pitfalls
Before diving into the API, here are the most common mistakes:
1. Forgetting Debug/Release Differences
Cell<int> c(5, 0);
int bad = c(10);
Solution: Test in both debug and release builds. Use static analysis tools.
2. DynamicBitset: Modifying After lock()
DynamicBitset bits(100);
bits.set(5);
bits.lock();
bits.set(10);
Solution: Only lock() when finalized. Use unlock() to modify again.
3. ShiftRegister: revert() Only Works Once
ShiftRegister<int> reg(3);
reg.push(1);
reg.push(2);
reg.revert();
reg.revert();
Solution: Only call revert() immediately after a failed push().
4. Map: operator[] vs operator()
Map<string, int> m;
int x = m["missing"];
int y = m("missing");
Solution: Use [] for insert-or-access, () for checked read.
5. Genome: Insufficient Bit Resolution
Genome<4, 3> genome( mins, maxs, scales );
Solution: Choose B ≥ 10 for continuous parameters. Use log scaling for wide ranges.
6. Thread Safety
All containers are not thread-safe. Concurrent writes require external synchronization (mutexes).
Memory Management Strategies
Different containers use different memory models:
| Container | Strategy | Notes |
| Cell, Map, OrderedMap, Set, Queue | STL allocators | RAII, exception-safe |
| Bitset<N> | Stack (compile-time size) | Minimal overhead |
| DynamicBitset | malloc/free for uint64_t blocks | Manual deallocation in destructor |
| ShiftRegister<T> | malloc/free | +1 extra element for revert backup |
| StringList | malloc/free for char** | C API compatibility |
| Genome | Embeds Bitset<N*B> | Stack-based DNA |
Container Reference
1. Cell<T> - Dynamic Array
File: cl_Cell.hpp STL Equivalent: std::vector<T>
Purpose: Primary dynamic array container, wrapping std::vector<T> with additional functionality.
Description
Cell is BELFEM's most commonly used container, providing:
- Bounds-checked access via operator() in debug mode
- Additional utility functions (sort, unique, reverse, append)
- Move semantics support
- Direct access to underlying std::vector when needed
Key Features
Cell<int> a;
Cell<int> b(10, 0);
Cell<int> c = {1, 2, 3, 4};
int val = a(0);
int& first = a.first();
int& last = a.last();
a.push(5);
a.push(std::move(temp));
a.emplace(args...);
int popped = a.pop();
a.set_size(100);
a.reserve(1000);
a.shrink_to_fit();
a.clear();
std::vector<T>& vec = a.vector_data();
T* ptr = a.data();
for (auto& elem : a) { }
Free Functions
sort(myCell);
sort(myCell, comparator);
unique(myCell);
reverse(myCell);
append(cellA, cellB);
append_move(cellA, cellB);
swap(cellA, cellB);
When to Use
- Primary choice for dynamic arrays in BELFEM
- Node lists, element connectivity, general collections
- When you need STL vector functionality with bounds checking
Performance Notes
- operator() has zero overhead in release builds (NDEBUG)
- Debug builds include comprehensive bounds checking
- append_move() is more efficient than append() when source is temporary
See: Cell class and free functions in cl_Cell.hpp
2. Map<Key, Value> - Hash Map
File: cl_Map.hpp STL Equivalent: std::unordered_map<Key, Value>
Purpose: Wrapper around std::unordered_map with enhanced error reporting.
Description
Provides hash-based key-value storage with:
- Descriptive error messages for missing keys (debug mode)
- Consistent interface with other BELFEM containers
- Two access patterns: [] (insert-or-access) and () (checked access)
Key Features
Map<string, int> ages;
Map<int, Vector<real>> data;
ages["Alice"] = 30;
ages.map_data().insert({"Bob", 25});
int age = ages("Alice");
int& ref = ages["Charlie"];
bool exists = ages.key_exists("Bob");
size_t n = ages.size();
bool empty = ages.empty();
ages.erase_key("Alice");
ages.clear();
for (const auto& [name, age] : ages) {
}
std::unordered_map<Key, Value>& raw = ages.map_data();
Access Patterns
Two operators with different semantics:
- operator[](key): Insert-or-access, creates entry if missing (default-constructed)
- operator()(key): Checked access, asserts if key not found
Map<string, int> m;
m["new_key"] = 5;
int val = m("new_key");
int bad = m("missing");
When to Use
- ID-to-object mappings (e.g., node ID → node pointer)
- Fast lookups by key (O(1) average case)
- When insertion order doesn't matter
Performance Notes
- Hash-based: O(1) average lookup/insert, O(n) worst case
- No ordering guarantees
- Use OrderedMap if you need sorted iteration
See: Map class in cl_Map.hpp
3. OrderedMap<Key, Value> - Sorted Map
File: cl_OrderedMap.hpp STL Equivalent: std::map<Key, Value>
Purpose: Wrapper around std::map for sorted key-value storage.
Description
Similar to Map, but maintains keys in sorted order using a red-black tree.
Key Differences from Map
- Iteration order: Keys iterated in sorted order
- Performance: O(log n) lookup/insert (slower than Map)
- Use case: When sorted iteration is required
OrderedMap<int, string> sorted;
sorted[3] = "three";
sorted[1] = "one";
sorted[2] = "two";
for (const auto& [key, val] : sorted) {
cout << key << ": " << val << endl;
}
When to Use
- Need sorted iteration by key
- Range queries on keys
- Deterministic iteration order required
See: OrderedMap class in cl_OrderedMap.hpp
4. Set<Key> - Hash Set
File: cl_Set.hpp STL Equivalent: std::unordered_set<Key>
Purpose: Wrapper around std::unordered_set with set operations.
Description
Unordered collection of unique elements with mathematical set operations.
Key Features
Set<int> primes = {2, 3, 5, 7, 11};
Set<string> names(vec.begin(), vec.end());
primes.insert(13);
primes.emplace(17);
bool has5 = primes.contains(5);
size_t count = primes.count(3);
bool empty = primes.empty();
primes.erase(2);
primes.clear();
Set<int> a = {1, 2, 3, 4};
Set<int> b = {3, 4, 5, 6};
Set<int> union_ab = a | b;
Set<int> intersect = a & b;
Set<int> diff = a - b;
Set<int> sym_diff = a ^ b;
bool is_sub = a.is_subset_of(b);
bool is_super = a.is_superset_of(b);
Set Operations Summary
| Operation | Operator | Meaning |
| Union | a \| b | Elements in a or b |
| Intersection | a & b | Elements in both a and b |
| Difference | a - b | Elements in a but not b |
| Symmetric Diff | a ^ b | Elements in a or b but not both |
When to Use
- Unique element collections
- Fast membership testing (O(1) average)
- Mathematical set operations
See: Set class in cl_Set.hpp
5. Queue<T> - FIFO Queue
File: cl_Queue.hpp STL Equivalent: std::queue<T>
Purpose: Wrapper around std::queue for FIFO operations.
Description
Simple first-in-first-out queue with conversion from Cell.
Key Features
Queue<int> q;
Queue<int> q2(myCell);
q.push(10);
int front = q.pop();
size_t n = q.size();
bool empty = q.empty();
When to Use
- Breadth-first search algorithms
- Task scheduling
- Any FIFO processing
See: Queue class in cl_Queue.hpp
6. Bitset<N> - Fixed-Size Bitset
File: cl_Bitset.hpp STL Equivalent: std::bitset<N>
Purpose: Wrapper around std::bitset<N> for compile-time fixed-size bit arrays.
Description
Compile-time sized bitset for flags and boolean arrays.
Key Features
Bitset<64> flags;
flags.set(5);
flags.reset(5);
flags.flip(5);
flags.reset();
bool isSet = flags.test(5);
index_t numSet = flags.count();
index_t size = flags.size();
std::bitset<N>& raw = flags.data();
When to Use
- Fixed number of boolean flags known at compile time
- Bit manipulation with known size
- Memory-efficient boolean arrays
Limitations
- Size must be compile-time constant
- Use DynamicBitset for runtime-sized bit arrays
See: Bitset class in cl_Bitset.hpp
7. DynamicBitset - Runtime-Sized Bitset
File: cl_DynamicBitset.hpp, cl_DynamicBitset.cpp STL Equivalent: None (custom implementation)
Purpose: Runtime-resizable bitset with advanced features.
Description
Advanced bitset implementation with:
- Runtime-determined size
- Locking mechanism for immutability and fast hashing
- Hash-based comparison (FNV-64 algorithm)
- Bitwise operations (|, &, ^)
- Efficient bit extraction
- Serialization support
Key Features
DynamicBitset bits(1000);
bits.set(42);
bits.reset(42);
bits.set(10, true);
bits.flip(5);
bits.flip();
bits.reset();
bool isSet = bits.test(42);
index_t numSet = bits.count();
index_t size = bits.size();
index_t mem = bits.memory();
Cell<index_t> indices;
bits.where(indices);
bits.where(indices, true);
bits.where(indices, false);
bits.lock();
size_t hash = bits.hash();
bool locked = bits.is_locked();
bits.unlock();
if (bits1 == bits2) {
}
DynamicBitset result = bits1 | bits2;
DynamicBitset result = bits1 & bits2;
DynamicBitset result = bits1 ^ bits2;
bits1 |= bits2;
bits1 &= bits2;
bits1 ^= bits2;
string binStr = bits.to_string();
string hexStr = bits.to_hex();
bits.set_from_hex("A3F2");
index_t val = bits.to_int();
bits.set_index(42);
index_t idx = bits.index();
Locking Mechanism
The locking mechanism serves two purposes:
- Immutability: Prevents modification of bitset after finalization
- Fast Comparison: Cached FNV-64 hash enables O(1) inequality checks
DynamicBitset a(100), b(100);
a.lock();
b.lock();
if (a == b) {
}
Note: reset() (clear all bits) automatically unlocks the bitset.
Serialization
DynamicBitset supports multiple serialization formats:
DynamicBitset bits(128);
string hex = bits.to_hex();
bits.set_from_hex(hex);
string bin = bits.to_string();
const uint64_t* raw = bits.data();
Performance Notes
- where() method: one algorithm; walks the two-level summary bitmaps, so it skips every zero data word (cost: all level-2 words + touched words + set bits). The aAssumeSparse flag is accepted and ignored.
- Bitwise operations: Optimized with pointer arithmetic, vectorizable
- Hash comparison: O(1) for inequality, O(n) for equality confirmation
- Storage: Uses uint64_t blocks (8 bytes each), efficient for large bit arrays
When to Use
- Runtime-determined boolean arrays
- Cohomology/topology computations (set operations on facets)
- Hash-based bitset comparisons (use in maps/sets)
- Need to extract indices of set bits efficiently
Lesson Learned: The where_sparse() Optimization Paradox
During development of the where_sparse() routine, six different AI models suggested "obvious" optimizations:
- Hoisting bounds checks out of the inner loop
- Loop splitting (separate fast loop for full blocks vs. partial blocks)
- Aggressive masking to eliminate inner-loop logic
The silicon reality: Micro-benchmarking revealed the original, unoptimized loop was 82% faster than the theoretically "superior" version.
Why the simple loop won:
- Branch Predictability: Because unused bits in the final block are zeroed by construction (class invariant), the branch if (tIndex < mNumberOfBits) is true ~100% of the time. Modern branch predictors handle this with virtually zero clock-cycle cost.
- Instruction Cache Density: The simple loop resulted in smaller binary code. The "optimized" loop-splitting approach doubled the code size, increasing I-cache pressure and preventing effective compiler auto-vectorization.
- Low-Latency Invariants: Relying on class invariants (high bits always zero) is cheaper than enforcing them at runtime via masking.
Silicon Guardrail Rule: Profile before you perfect. Modern silicon is smarter than most algorithms. Keep hot loops simple and compact—more code is rarely faster code.
See also: doc/lessons_learned.md for the full case study and additional performance lessons.
See: DynamicBitset class in cl_DynamicBitset.hpp and .cpp
8. ShiftRegister<T> - Fixed-Capacity FIFO with Revert
File: cl_ShiftRegister.hpp STL Equivalent: None (custom circular buffer)
Purpose: Fixed-capacity circular buffer with newest-first ordering and one-step revert capability.
Description
A specialized container that maintains the N most recent values, with:
- Newest value at index 0, oldest at index N-1
- Fixed capacity determined at construction
- One-step revert capability (undo last push)
- Efficient memory management with malloc/free
Key Features
ShiftRegister<double> history(5);
ShiftRegister<double> temps(5, 20.0);
ShiftRegister<int> recent = {1, 2, 3, 4, 5};
history.push(100.5);
history.push(200.3);
double newest = history(0);
double oldest = history(history.size()-1);
history.push(300.0);
history.revert();
size_t current = history.size();
size_t max = history.capacity();
bool isEmpty = history.empty();
bool isFull = history.full();
history.clear();
history.fill(0.0);
history.reserve(10);
history.free();
Revert Capability
Critical: revert() can only be called once after each push().
The shift register allocates one extra backup slot internally:
ShiftRegister<int> reg(3);
reg.push(1); reg.push(2); reg.push(3);
reg.push(4);
reg.revert();
reg.push(5);
reg.revert();
Use case: Time integration where you may need to reject a timestep:
ShiftRegister<Vector<real>> history(3);
history.push(initialState);
for (size_t step = 0; step < numSteps; ++step) {
Vector<real> newState = time_integrate(history(0), dt);
history.push(newState);
if (!check_convergence(newState)) {
history.revert();
dt *= 0.5;
continue;
}
}
Iteration
ShiftRegister<double> data(10, 1.0);
for (double val : data) {
}
When to Use
- Time-stepping algorithms (storing previous timestep values)
- Moving window computations (moving averages, gradients)
- Iterative solvers with history dependence (BDF methods)
- Undo functionality for single operations
Performance Notes
- Uses std::malloc/free for memory (not new/delete)
- Efficient push(): O(capacity) using std::move_backward
- Fixed capacity: no dynamic resizing overhead
- Revert is O(capacity) but only available immediately after push()
See: ShiftRegister class in cl_ShiftRegister.hpp
9. Genome<B, N> - Genetic Algorithm Encoding
File: cl_Genome.hpp STL Equivalent: None (custom genetic algorithm encoding)
Purpose: Encode real-valued parameters as bit strings for genetic algorithms.
Description
Template class for genetic algorithm optimization:
- B: Bits per parameter (resolution = 2^B levels)
- N: Number of parameters
- Supports linear and logarithmic parameter scaling
- Implements crossover, mutation, and fitness tracking
Tip: Use B ≥ 10 for continuous parameters (1024 levels). Use log scaling for parameters spanning orders of magnitude.
Key Features
Vector<real> minVals = {0.1, 1.0, 0.001};
Vector<real> maxVals = {10.0, 100.0, 1.0};
Bitset<3> logScale;
logScale.set(0);
Genome<8, 3> individual(minVals, maxVals, logScale);
Vector<real> params = {0.5, 50.0, 0.1};
individual.set_values(params);
individual.randomize();
Vector<real> decoded(3);
individual.get_values(decoded);
Genome<8, 3> mom(minVals, maxVals, logScale);
Genome<8, 3> dad(minVals, maxVals, logScale);
Genome<8, 3> child(minVals, maxVals, logScale);
child.inherit(&mom, &dad);
individual.set_fitness(0.042);
real fitness = individual.fitness();
bool alive = individual.is_alive();
individual.kill();
Genetic Algorithm Workflow
const size_t BITS = 12;
const size_t PARAMS = 5;
const size_t POP_SIZE = 100;
Cell<Genome<BITS, PARAMS>*> population(POP_SIZE, nullptr);
for (auto& genome : population) {
genome = new Genome<BITS, PARAMS>(mins, maxs, scales);
genome->randomize();
}
for (size_t gen = 0; gen < MAX_GENERATIONS; ++gen) {
for (auto& genome : population) {
Vector<real> params(PARAMS);
genome->get_values(params);
real fitness = objective_function(params);
genome->set_fitness(fitness);
}
opGenomeSort<BITS, PARAMS> sorter;
sort(population, sorter);
Cell<Genome<BITS, PARAMS>*> nextGen(POP_SIZE, nullptr);
for (size_t i = 0; i < POP_SIZE/10; ++i) {
nextGen(i) = population(i);
}
for (size_t i = POP_SIZE/10; i < POP_SIZE; ++i) {
size_t momIdx = tournament_select(population);
size_t dadIdx = tournament_select(population);
nextGen(i)->inherit(population(momIdx), population(dadIdx));
}
population = nextGen;
}
Parameter Encoding
- Linear scale: value = min + (max - min) × (bits / (2^B - 1))
- Log scale: value = exp(log(min) + (log(max) - log(min)) × (bits / (2^B - 1)))
Use log scale for parameters spanning orders of magnitude (e.g., conductivity: 0.001 to 100).
When to Use
- Parameter optimization via genetic algorithms
- Multi-objective optimization problems
- Non-gradient-based optimization
- Discrete parameter search
See: Genome class in cl_Genome.hpp
10. StringList - C-String Array for I/O
File: cl_StringList.hpp, cl_StringList.cpp STL Equivalent: None (C-compatible string array)
Purpose: Fixed-size C-string array for interfacing with C libraries (e.g., Exodus).
Description
Low-level string container using char** for compatibility with C APIs.
Key Features
StringList names(10);
names.push("node_block_1");
names.push("element_block_2");
const char* first = names.item(0);
char** raw = names.data();
When to Use
- Only when interfacing with C libraries requiring char**
- Exodus file I/O
- Otherwise use Cell<string>
Limitations
- Fixed size at construction
- Manual memory management (RAII via destructor)
- Not recommended for general use
See: StringList class in cl_StringList.hpp and .cpp
Container Selection Guide
Quick Reference
| Need | Use |
| Dynamic array of values | Cell<T> |
| Fast key-value lookup | Map<Key, Value> |
| Sorted key-value pairs | OrderedMap<Key, Value> |
| Unique element collection | Set<T> |
| FIFO queue | Queue<T> |
| Fixed-size boolean flags (compile-time) | Bitset<N> |
| Dynamic boolean array with operations | DynamicBitset |
| Recent value history with rollback | ShiftRegister<T> |
| Genetic algorithm parameters | Genome<B, N> |
| C API string interface | StringList |
Performance Characteristics
| Container | Access | Insert | Search | Memory Strategy |
| Cell | O(1) | O(1) amortized | O(n) | STL allocator |
| Map | O(1) avg, O(n) worst | O(1) avg | O(1) avg | Hash table |
| OrderedMap | O(log n) | O(log n) | O(log n) | Red-black tree |
| Set | O(1) avg | O(1) avg | O(1) avg | Hash table |
| Queue | O(1) front | O(1) | N/A | STL deque |
| Bitset<N> | O(1) | O(1) | O(1) | Stack (compile-time) |
| DynamicBitset | O(1) | O(1) | O(1) | malloc uint64 blocks |
| ShiftRegister | O(1) | O(N) | N/A | malloc +1 backup |
| Genome | N/A | N/A | N/A | Embedded Bitset<N×B> |
Common Patterns
Pattern 1: Building and Sorting a Cell
Cell<index_t> nodeIDs;
nodeIDs.reserve(estimatedSize);
for (auto* node : nodes) {
nodeIDs.push(node->id());
}
sort(nodeIDs);
unique(nodeIDs);
Pattern 2: Map with Default Values
Map<index_t, real> values;
real& val = values[nodeID];
val += contribution;
Pattern 3: Set Operations for Filtering
Set<index_t> boundaryNodes = {...};
Set<index_t> activeNodes = {...};
Set<index_t> boundaryActive = boundaryNodes & activeNodes;
Set<index_t> interior = activeNodes - boundaryNodes;
Pattern 4: DynamicBitset for Mesh Topology
DynamicBitset elementFlags(numElements);
for (index_t e = 0; e < numElements; ++e) {
if (element_touches_node(e, targetNode)) {
elementFlags.set(e);
}
}
Cell<index_t> touchingElements;
elementFlags.lock();
elementFlags.where(touchingElements);
Pattern 5: ShiftRegister for Adaptive Time Integration
ShiftRegister<Vector<real>> history(3, initialState);
for (size_t step = 0; step < numSteps; ++step) {
Vector<real> newState = bdf3_step(
history(0),
history(1),
history(2),
dt
);
history.push(newState);
if (!converged(newState, tol)) {
history.revert();
dt *= 0.5;
continue;
}
dt = adaptive_dt(newState);
}
Design Philosophy
Why Wrappers?
BELFEM wraps STL containers for several reasons:
- Consistent Interface: All containers use similar naming (e.g., set_size() vs. resize())
- Enhanced Debugging: Bounds checking with descriptive error messages in debug builds
- Zero Overhead: Release builds compile to identical STL performance
- Domain Extensions: Additional functionality for FEM/physics (e.g., unique(), set operations)
- Future Flexibility: Can switch implementations without changing client code
Debug vs. Release Behavior
Most containers have different behavior in debug and release builds:
Cell<int> c(5, 0);
int bad = c(10);
int bad = c(10);
This provides safety during development while maintaining full performance in production.
Recommendation: Always test in both debug and release modes. Use static analysis tools (e.g., clang-tidy, valgrind) to catch UB in release builds.
Memory Management
See "Memory Management Strategies" table at the top for details.
Best Practices
1. Prefer Cell Over std::vector
Cell<Node*> nodes;
std::vector<Node*> nodes;
2. Reserve Memory When Size is Known
Cell<index_t> ids;
ids.reserve(
mesh->number_of_nodes());
for (
auto* node :
mesh->nodes()) {
ids.push(node->id());
}
3. Use Appropriate Map Type
Map<id_t, Element*> elementMap;
OrderedMap<id_t, Element*> sorted;
4. Lock DynamicBitsets Before Comparison
DynamicBitset a(100), b(100);
a.lock();
b.lock();
if (a == b) {
}
Caution: Don't forget to unlock() if you need to modify again.
5. DynamicBitset where() Has One Strategy
DynamicBitset flags(10000);
Cell<index_t> indices;
flags.where(indices);
6. Understand ShiftRegister Revert Limitation
ShiftRegister<double> reg(5);
reg.push(1.0);
reg.push(2.0);
reg.revert();
reg.push(3.0);
reg.revert();
Examples from BELFEM Codebase
Example 1: Mesh Node Storage
Cell<Node*> mNodes;
mNodes.reserve(nodeCount);
for (index_t i = 0; i < nodeCount; ++i) {
mNodes.push(new Node(i, coords));
}
Example 2: Element-to-Node Connectivity
Cell<Node*> mNodes;
Node* node = mNodes(localIndex);
Example 3: Cohomology Facet Operations
DynamicBitset facet1(numNodes);
DynamicBitset facet2(numNodes);
DynamicBitset boundary = facet1 ^ facet2;
boundary.lock();
Map<size_t, DynamicBitset*> facetMap;
facetMap[boundary.hash()] = &boundary;
Thread Safety and MPI
Important: BELFEM containers are not thread-safe by default.
- Reading: Multiple threads can safely read from const containers
- Writing: Use external synchronization (mutexes, atomics) for concurrent writes
- MPI: Each rank has separate container instances (no shared memory)
- Use comm module for synchronization (e.g., all-gather for Cells)
Example with OpenMP:
Cell<int> shared(100);
#pragma omp parallel for
for (int i = 0; i < 100; ++i) {
int val = shared(i);
#pragma omp critical
shared(i) = compute(val);
}
Related Modules
- linalg: Vector, Matrix containers for numerical linear algebra
- mesh: Uses Cell extensively for node/element storage
- fem: Uses containers throughout for DOF management, assembly
- comm: MPI communication helpers for container synchronization
- homology: Uses DynamicBitset for topology operations
See Also
- Linalg Module - Linear algebra containers (Vector, Matrix)
- Mesh Module - Mesh data structures using containers
- Homology Module - Cohomology algorithms using bitsets
- CLAUDE.md (repository root) - Documentation organization guidelines
- Documentation Guidelines - How to document code
- C++ Documentation: make doc (Doxygen)
Revision History:
- 2026-01-16: Initial version incorporating feedback from multiple AI reviewers (Grok, ChatGPT, CBorg, Gemini, Opus)
1.18.0