Идиоматический C ++ для нахождения диапазона строк одинаковой длины по заданному вектору строк (упорядоченный по длине)

Question

с учетом std::vector< std::string >, вектор упорядочен по длине строки, как я могу найти диапазон силы равной длины?

Я с нетерпением жду идиоматического решения в C ++.

Я нашел это решение:

// any idea for a better name? (English is not my mother tongue)
bool less_length( const std::string& lhs, const std::string& rhs )
{
    return lhs.length() < rhs.length();
}

std::vector< std::string > words;
words.push_back("ape");
words.push_back("cat");
words.push_back("dog");
words.push_back("camel");
size_t length = 3;
// this will give a range from "ape" to "dog" (included):
std::equal_range( words.begin(), words.end(), std::string( length, 'a' ), less_length );

Есть ли стандартный способ сделать это (прекрасно)?

Answer 1

Я ожидаю, что вы могли бы написать компаратор следующим образом:

struct LengthComparator {
    bool operator()(const std::string &lhs, std::string::size_type rhs) {
        return lhs.size() < rhs;
    }
    bool operator()(std::string::size_type lhs, const std::string &rhs) {
        return lhs < rhs.size();
    }
    bool operator()(const std::string &lhs, const std::string &rhs) {
        return lhs.size() < rhs.size();
    }
};

Тогда используйте это:

std::equal_range(words.begin(), words.end(), length, LengthComparator());

Я ожидаю, что третья перегрузка operator() никогда не используется, потому что предоставляемая информация избыточна. Диапазон должен быть предварительно отсортирован, поэтому бессмысленно, чтобы алгоритм сравнивал два элемента из диапазона, он должен сравнивать элементы из диапазона с поставляемой вами целью. Но стандарт не гарантирует этого. [Изменить: и определение всех трех означает, что вы можете использовать один и тот же класс компаратора, чтобы сначала упорядочить вектор, что может быть удобно].

Это работает для меня (gcc 4.3.4), и хотя я думаю, что это будет работать и для вашей реализации, я менее уверен, что это действительно допустимо. Он реализует сравнения, которые, как говорит описание equal_range, будут верны для результата, и 25.3.3 / 1 не требует, чтобы параметр шаблона T должен был точно соответствовать типу объектов, на которые ссылаются итераторы. Но, возможно, я пропустил какой-то текст, добавляющий больше ограничений, поэтому я бы сделал больше тралений стандартов перед тем, как использовать его в чем-то важном.

Answer 2

Ваш путь определенно не однотипен, но необходимость создания фиктивной строки с заданной длиной выглядит не очень элегантно и не очень читабельно.

Я бы, возможно, написал свою собственную вспомогательную функцию (т. Е. string_length_range), инкапсулирующую простой, простой цикл в списке строк. Нет необходимости использовать std:: инструменты для всего.

Answer 3

std::equal_range выполняет бинарный поиск. Это означает, что вектор words должен быть отсортирован, что в данном случае означает, что его длина не должна уменьшаться.

Я думаю, что ваше решение хорошее, определенно лучше, чем написание собственной реализации бинарного поиска, которая, как известно, подвержена ошибкам и трудно доказать, что она правильна.

Если бинарный поиск не был вашим намерением, то я согласен с Александром. Просто простой цикл по словам является самым чистым.