# UNDF: UNDF-2026-000000553
# thrift-0001: t_cpp_generator is_struct_storage_not_throwing() std::find O(M²) → O(1) with unordered_set

## File
`compiler/cpp/src/thrift/generate/t_cpp_generator.cc`

## Lines
5100–5140 (`is_struct_storage_not_throwing`)

## Severity
**LOW** — Compiler path (thrift IDL compilation, not runtime). The function traverses nested struct fields to determine if a C++ struct can be declared `noexcept`. When a struct field is itself a struct, its members are appended to the `members` vector and a deduplication check via `std::find` is performed. With deeply nested IDL definitions (struct trees with N total fields), the total dedup work is O(M²) where M is the flattened member count. Called 3 times per struct during C++ code generation. Only manifests with large, deeply nested Thrift IDL schemas (rare but possible in enterprise Thrift deployments).

## Complexity Analysis

**Defective:**
```
members = tstruct->get_members()  // size M0
for i in 0..members.size():       // grows as nested structs are flattened
  if type is struct:
    for each nested_field:
      std::find(members.begin(), members.end(), nested_field)  // O(M) each
      → total O(M²) if many nested structs
```

**Fixed:** Replace dedup check with `std::unordered_set<t_field*>` for O(1) membership test.

## Defective Snippet

```cpp
// compiler/cpp/src/thrift/generate/t_cpp_generator.cc, lines 5100-5138
bool t_cpp_generator::is_struct_storage_not_throwing(t_struct* tstruct) const {
  vector<t_field*> members = tstruct->get_members();  // starts at M0

  for (size_t i = 0; i < members.size(); ++i) {  // size grows during iteration
    t_type* type = get_true_type(members[i]->get_type());
    // ...
    if (type->is_struct()) {
      const vector<t_field*>& more = ((t_struct*)type)->get_members();
      for (auto it = more.begin(); it < more.end(); ++it) {
        if (std::find(members.begin(), members.end(), *it) == members.end())  // O(M) scan
          members.push_back(*it);
      }
      continue;
    }
    // ...
  }
  return true;
}
```

## Fixed Snippet

```cpp
bool t_cpp_generator::is_struct_storage_not_throwing(t_struct* tstruct) const {
  vector<t_field*> members = tstruct->get_members();
  std::unordered_set<t_field*> seen(members.begin(), members.end());  // O(M0) build

  for (size_t i = 0; i < members.size(); ++i) {
    t_type* type = get_true_type(members[i]->get_type());
    // ...
    if (type->is_struct()) {
      const vector<t_field*>& more = ((t_struct*)type)->get_members();
      for (auto it = more.begin(); it < more.end(); ++it) {
        if (seen.find(*it) == seen.end()) {   // O(1) hash lookup
          members.push_back(*it);
          seen.insert(*it);
        }
      }
      continue;
    }
    // ...
  }
  return true;
}
```

## Notes
- `t_field*` is a pointer — suitable as unordered_set key (pointer equality/hash)
- Called 3 times per struct: constructor, copy constructor, and noexcept check (lines 1247, 1299, 1409)
- For a Thrift IDL with S structs each containing N fields that reference other structs: O(S × N²) total
- Typical Thrift IDL: small struct counts, low impact. Large enterprise IDL (e.g., 100 structs × 20 nested fields) would see ~40,000 comparisons vs ~2,000 with fix
- `std::unordered_set` is in C++11 standard; already included in this translation unit via `<algorithm>` and `<vector>` include path
