Как проверить, является ли C ++ STL список палиндроми c или нет?

Question

Я хочу проверить, является ли данный список C ++ STL палиндроми c или нет?

bool isPalindromic(list <int> c);

int main(){

 list<int> l;
l.push_front(12);
l.push_front(35);
l.push_front(34);
l.push_front(35);
l.push_front(12);

isPalindromic(l);
}

output : true 

Answer 1

Вы можете использовать std::equal, чтобы проверить, равен ли список с начала списку с конца. Страница cppreference для std :: equal даже содержит пример для этого.

EDIT (по запросу): на основе примера, предоставленного cppreference:

std::equal(s.begin(), s.begin() + s.size()/2, s.rbegin());

строка выше проверяет, является ли строка палиндромом. Но в нашем случае это не будет работать, так как begin() списка возвращает BidirectionalIterator, а не RandomAccessIterator строки *1011*, поэтому мы не можем выполнить s.begin() + s.size()/2 часть. Чтобы заставить его работать, мы должны изменить наш код на:

bool is_palindrome(const std::list<int>& l) //use templated version std::list<T> if needed
{
    return std::equal(l.begin(), l.end(), l.rbegin());
}

Это, конечно, не идеально, так как он выполняет итерацию от начала до конца списка, хотя он может просто заканчиваться после середины, но это просто и работает.

Answer 2

Палиндром означает «одно и то же чтение вперед и назад», поэтому просто сравните c с std::reverse(c).

Answer 3

Простое решение, которое позволяет избежать ненужных сравнений, выполняемых std::equal(begin, end, rbegin):

template<typename T>
bool is_palindrome(const std::list<T>& list) {
    auto it1 = list.begin();
    auto it2 = list.end();
    if (list.size() % 2 == 0) {
        while (it1 != it2)
            if (!(*it1++ == *--it2))
                return false;
    } else {
        while (it1 != --it2)
            if (!(*it1++ == *it2))
                return false;
    }
    return true;
}

Обратите внимание, что, поскольку C ++ 11 std::list::size имеет постоянную сложность по времени.

Пример:

std::list<int> l{12, 35, 34, 35, 12};
std::cout << std::boolalpha << is_palindrome(l);   // Output: true

Демонстрация с основами c контрольные примеры