Как доза алгоритма доступа к компонентам структуры данных в STL

Question

Стандартная библиотека шаблонов (STL) предоставляет структуры данных и алгоритмы . Тем не менее, это не тот случай, что каждый алгоритм может использоваться с каждой структурой данных . Предположим, что STL поддерживает использование алгоритма A со структурой данных D.

(a) Как устанавливается связь между A и D. Другими словами, как A получает компоненты D? Приведи примеры.

(b) STL гарантирует (то есть, обещает) что-то о результате использования A с D. Какова гарантия?

---

A) STL также предоставляет различные «итераторы» для доступа к элементам на структурах данных. Существуют различные типы итераторов, они могут перемещаться линейно от начала до конца, некоторые могут перемещаться в обоих направлениях, а некоторые могут свободно перемещаться по любому элементу в D. Тип итератора, поддерживаемого D, будет определять тип A, который могут быть выполнены с помощью D.

B) Если A может быть запущен на D, то STL гарантирует временную сложность (O (N)), что потребуется, чтобы завершить А.

Здравствуйте! Я изучаю теоретический экзамен. Мне было интересно, все ли вы думаете, что я что-то пропустил в своих ответах здесь.

Answer 1

«(a) Как установлена ​​связь между A и D. Другими словами, как A-компоненты доступа D? Приведите примеры».

Это делается через итераторы. Итераторы - это клей между алгоритмами и структурами данных в STL. Я буду использовать C++ 11 для моего примера:

std::vector<int> vec{1, 5, 3, 4}; 
std::list<int> l{1, 4, 8, 3}; 

auto foundInVecItem = std::find(vec.begin(), vec.end(), 3); 
//Note: same algorithm used for different data structure. 
auto foundInVecItem = std::find(l.begin(), l.end(), 3); 

Это работает, потому что std::find не делает никаких предположений о структуре данных, которая использует для поиска. Он использует концепцию ForwardIterator для ее реализации. Вы можете посмотреть категории итераторов here.

std::find можно было бы реализовать что-то (упрощенный, так как это просто для обучения), как это:

template <class ForwardIterator> 
ForwardIterator find(ForwardIterator b, ForwardIterator e, 
        typename ForwardIterator::value_type v) { 
    while (b != e) { 
     if (*b == v) { 
     return b; 
     } 
    } 
    return e; 

}

Важным моментом здесь является то, что интерфейс итератора используется для доступа к элементам std::list или std::vector, поэтому алгоритм не заботится о структуре данных, пока они обеспечивают ForwardIterator.

б) STL гарантирует (то есть, обещает) что-то о результате использования A с D. Какова гарантия? "

Извините, это слишком общее, что вы подразумеваете под этим вопросом? Если вы имеете в виду большую нотацию O, а именно асимптотические вычислительные затраты, да. Стандарт обещает ограниченную большую стоимость O для каждого алгоритма, учитывая структуру данных. Это зависит от алгоритма и структуры данных. Например, std::advance, который продвигает итератор на несколько шагов, гарантированно будет O(1) для RandomAccessIterator s и O(n) для остальных из них.

«A) STL также предоставляет различные« итераторы »для доступа к элементам в структурах данных.Существуют различные типы итераторов, они могут перемещаться линейно от начала до конца, некоторые могут перемещаться в обоих направлениях, а некоторые могут свободно перемещаться по любому элементу в D. Тип итератора, поддерживаемого D, будет определять тип A, который могут быть выполнены с помощью D. «

Вы можете посмотреть на итераторных категории here.

» B) Если A может быть запущен на D, то STL гарантирует временную сложность (O (п)) что он должен будет заполнить A. »

Да, это правильно. Спецификация гарантирует асимптотические вычислительные затраты на операцию, учитывая структуру данных.