我需要帮助来搜索容器中的元素。
例如:我在容器中有以下单词:
crr.push_back("fred");
crr.push_back("barney");
crr.push_back("pavel");
crr.push_back("zoot");
crr.push_back("jim");
crr.push_back("peter");
crr.push_back("patrick");
我用它来寻找:
const bool Contains(vector<char*>& Vec, char* Element)
{
if (find(Vec.begin(), Vec.end(), Element) != Vec.end())
return true;
return false;
}
int main()
{
if (Contains(crr, "patrick"))
{
system("cls");
printf("Found\n");
}
else
{
system("cls");
printf("Nah\n");
}
}
它支持 Found
因为在容器中找到了 "patrick"
,但是我需要找到所有单词,例如,以 'p' 开头的单词
。例如,输出可能是:
pavel
peter
patrick
我如何实现这一点?谢谢。
最佳答案
您可以复制所有以'p'
开头的单词进入 std::vector<std::string>
容器,然后显示其内容。这可以在线性时间运行中完成,即 O(n)。空间复杂度也是线性的,因为您需要一个专用 vector 来存储以 'p'
开头的每个单词.
您可以使用函数模板 std::copy_if
来实现这一点通过提供合适的谓词,例如以下 lambda starts_with_p
:
// returns true whether the string starts with 'p', false otherwise
auto starts_with_p = [](std::string word) {
if (word.front() == 'p')
return true;
return false;
};
现在,只需使用 std::copy_if
使用该谓词:
std::vector<std::string> matched_words;
std::copy_if(crr.begin(), crr.end(),
std::back_inserter(matched_words), starts_with_p);
载体matched_words
包含原始容器中以 'p'
开头的所有单词.您现在可以轻松地显示它们:
for (const auto& word: matched_words)
std::cout << word << std::endl;
如果您不想要线性空间复杂度而是常数一,即 O(1),并且您的容器 crr
支持随机访问迭代器,你可以先对你的集合进行排序crr
与 std::sort
函数模板并使用 std::equal_range
对其执行二进制搜索为了获得所有以'p'
开头的单词的子范围:
std::sort(crr.begin(), crr.end());
auto cmp_1st_char = [](std::string a, std::string b) {
return a.front() < b.front();
};
auto p = std::equal_range(crr.begin(), crr.end(), "p", cmp_1st_char);
for (auto it = p.first; it != p.second; ++it)
std::cout << *it << std::endl;
但是请注意,排序的运行时间复杂度为 O(n log n)。因此,对于这两种选择,您将面临运行时间和空间复杂性之间的权衡。
关于c++ - 在容器中查找以给定字符开头的所有单词,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52180695/