Найти все слова в контейнере, которые начинаются с данного символа - PullRequest
Новая
       21

Найти все слова в контейнере, которые начинаются с данного символа

0 голосов
/ 05 сентября 2018

Мне нужна помощь с поиском предметов в контейнере.

Пример: у меня есть следующие слова в контейнере: 

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

Как я могу это понять? Спасибо.

1 Ответ

0 голосов
/ 06 сентября 2018

Вы можете скопировать все слова, которые начинаются с 'p', в контейнер std::vector<std::string> и затем отобразить его содержимое. Это можно сделать в линейном режиме, т. Е. O (n). Сложность пространства также линейна, так как вам нужен выделенный вектор для хранения каждого слова, которое начинается с 'p'.

Этого можно добиться с помощью шаблона функции std::copy_if, предоставив подходящий предикат , например следующую лямбду 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). Таким образом, с этими двумя вариантами вы сталкиваетесь с компромиссом между временем выполнения и сложностью пространства.

...