在C++中，我可以在不生成整個數據結構的情況下找到數據結構嗎？

Question

我有一個我想優化的函數，因爲它佔用了我程序運行時間的13.4％。

該函數返回一個相當大的容器，但大多數調用者不需要整個容器，因爲他們只是在數據結構中搜索符合特定條件的元素，然後拋出容器。但是，有幾個呼叫者使用整個容器。此外，返回的容器具有衆所周知的最大大小，並且在每次調用該函數時通常都非常接近該大小。

我希望優化此功能的一種方式是，當調用者只需要搜索特定項目時，不會生成整個數據結構，因爲這樣可以爲這些調用者節省大約一半的時間，因爲容器幾乎總是包含搜索的項目。是否有可能這樣做，並且仍然對需要整個容器的調用者具有相同的功能工作？或者，我可以實現一種適用於某種類型調用者的函數，另一種適用於另一種類型調用者，但是它們以某種方式共享邏輯？這是種什麼樣的整個設置是這樣的：我想優化

功能：

vector<Foo> Bar::generate() const { 
    vector<Foo> results; //Using a vector is arbitrary, it could be any container 
    results.reserve(100); 
    int n = 100; 
    while (n > 0 && this->shouldGenerate(n)) { 
     n--; 
     results.emplace_back(...); 
    } 
    return results 
} 

最常見的來電者：

Foo baz(Bar bar) { 
    vector<Foo> items = bar.generate(); 
    auto it = find_if(items.begin(), items.end(), my_pred); 
    if (it == items.end()) { 
     return Foo(); 
    } else { 
     return *it; 
    } 
} 

不常見的來電者：

void Qux::storeGeneratedFoos(Bar bar) { 
    this->foos = bar.generate(); 
} 

Answer 1

您可以嘗試在函數中使用static向量來避免每次重新分配空間，而r eturning對它的引用：

const vector<Foo> &Bar::generate() const { 
    static vector<Foo> results; //Using a vector is arbitrary, it could be any container 
    results.clear(); //clear from possible previous invocation 
    ... 
} 

然後baz()可以被定義爲

Foo baz(Bar bar) { 
    const vector<Foo> &items = bar.generate(); 
    ... 
} 

其他功能將不必修改該解決方案。

爲了減少代的數量，可以按如下方式創建一個模板函數：

template<class UnaryPredicate> 
Foo Bar::generate_if(UnaryPredicate pred) const { 
    Foo foo; 
    int n = 100; 
    while (n > 0 && this->shouldGenerate(n)) { 
     n--; 
     //instead of 'results.emplace_back(...);' do 
     foo = ...; 
     if (pred(foo)) 
      return foo; 
    } 
    return Foo(); 
} 

和baz()的定義修改爲

Foo baz(Bar bar) { 
    return bar.generate_if(my_pred); 
} 

Answer 2

我建議區分這兩種使用情況：這樣，你可以變得更快。由於運行時似乎是一個問題，我會盡量提高效率。

首先，概括髮電機：

template <typename Storage> 
void Bar::generate_impl(Storage & storage) const { 
    for (int n = 100; 
     n > 0 && shouldGenerate(n) and storage.go_on(); 
     --n) { 
     storage.add(/* some newly built Foo */); 
    } 
} 

那麼你可以有兩種類型的Storage。第一個將用於創建vector的原始用例。正如你看到的，它不會過早停止並存儲每個Foo通過：

struct MemorizingStorage { 
    vector<Foo> data; 
    MemorizingStorage() { data.reserve(100); } 
    void add(Foo const & f) { data.emplace_back(f); } 
    bool go_on() const { return true; } 
}; // MemorizingStorage 

第二個將是檢查一些Foo是否生成的使用情況。這個版本將不會存儲任何東西，但請記住無論任何Foo「添加」是正確的：

struct CheckingStorage { 
    Foo const & item; 
    bool found_it; 
    CheckingStorage(Foo const & f) : item(f), found_it(false) {} 
    void add(Foo const & f) { found_it = found_it or (item == f); } 
    bool go_on() const { return not found_it; } 
}; // CheckingStorage 

併爲您的用戶，您提供使用這些Storage小號Bar版本：

vector<Foo> Bar::generate() const { 
    MemorizingStorage storage; 
    generate_impl(storage); 
    return storage; // consider std::move if C++11 is applicable 
} 

bool Bar::is_generated(Foo const & item) const { 
    CheckingStorage storage(item); 
    generate_impl(storage); 
    return storage.found_it; 
} 

這是我能想到的最快方式：

• 當不需要時不需要創建任何向量。
• 它過早停止，當用戶只想知道，如果生成了一些Foo。

Answer 3

一種選擇是使自定義迭代器從Bar獲取項目。然後你可以使用自定義的迭代器直接在find_if，或者你可以用它來直接初始化使用兩個迭代器的構造函數或assign項目的vector：

class BarIterator : public std::iterator<std::input_iterator_tag, Foo> { 
    const Bar* bar; 
    int n; 
public: 
    BarIterator(const Bar& bar, int n); 
    Foo operator*() const; 
    bool operator==(const BarIterator& other) const; 
    bool operator!=(const BarIterator& other) const; 
    BarIterator& operator++(){ n--; return *this; } 
}; 

class Bar { 
    ... 
public: 
    BarIterator begin() const { return {*this, 100}; } 
    BarIterator end() const { return {*this, 0}; } 
    friend class BarIterator; 
}; 

Foo baz(const Bar& bar) { 
    auto it = std::find_if(bar.begin(), bar.end(), my_pred); 
    if (it == bar.end()) { 
     return Foo(); 
    } else { 
     return *it; 
    } 
} 

class Quz { 
    std::vector<Foo> foos; 
public: 
    void storeGeneratedFoos(const Bar& bar) { 
    foos.assign(bar.begin(), bar.end()); 
    } 
}; 

Live demo.