在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.