Как написать функцию, которая принимает итератор или коллекцию в общем виде?

Question

Я был программистом на Java почти исключительно последние 8 лет или около того, а недавно я снова играл на C ++. Вот проблема, с которой я столкнулся в связи с итераторами в C ++ STL и Java.

В Java вы можете написать метод, который принимает итератор, например:

void someMethod(Iterator<String> data) {
    // ...
}

Вы передаете Iterator, и метод не должен знать, какова основная коллекция этого итератора, и это хорошо.

В C ++ нет общего базового класса для итераторов (насколько я знаю). Мне нужно написать такую ​​функцию:

void some_function(std::vector<std::string>::const_iterator data) {
    // ...
}

Другими словами, some_function знает, что итератор является итератором над vector. Это нехорошо, потому что я хочу, чтобы функция работала независимо от того, что является базовой коллекцией итератора.

Как я могу сделать это в C ++? Если это на самом деле невозможно, то каков наилучший способ создать функцию в C ++, которая принимает коллекцию в качестве параметра, но ей не нужно знать, какой именно тип коллекции?

Добавление

Спасибо за ответы. В дополнение к ответам я нашел некоторую полезную информацию по этому вопросу в параграфе 7.5 (Черты итератора) книги Стандартная библиотека C ++: учебное пособие и справочник (Николас М. Йосуттис). В параграфе 7.5.1 объясняется, как писать специализированные версии функций для разных категорий итераторов.

Answer 1

Вы, вероятно, хотите рассмотреть шаблон функции. Посмотрите, как работают некоторые из std <algorithm> шаблонов функций, например std::for_each.

, например

template< class Iterator >
void some_function( Iterator first, Iterator last )
{
    // ...
}

Затем вы можете вызвать функцию, сгенерированную из этого шаблона, с различными типами итерируемых диапазонов.

, например

std::vector< double > my_doubles;
// ... populate doubles
some_function( my_doubles.begin(), my_doubles.end() );


std::set< Custom > my_custom_class_set;
// ... populate ...
some_function( my_custom_class_set.begin(), my_custom_class_set.end() );

int raw_array[50];
// ... populate ...
some_function( raw_array, raw_array + 50 );

Answer 2

Это пример одного из больших различий между C ++ и Java. Единственный инструмент абстракции, который есть в Java, - это полиморфизм времени выполнения (интерфейсы и абстрактные классы). В C ++ вы этим не ограничены. Вы можете создать псевдонимы для типов и позволить классам иметь другие связанные / вложенные типы. Во многих случаях это позволяет вам избежать полиморфизма во время выполнения. Универсальность во время компиляции имеет то преимущество, что она довольно быстрая (нет вызовов виртуальных функций, есть встроенные возможности). Кроме того, это облегчает управление в течение всей жизни, когда у вас нет сборщика мусора. Вы можете просто создавать объекты в стеке.

Вот (непроверенный) пример:

template<typename Iter>
typename std::iterator_traits<Iter>::value_type
sum(Iter begin, Iter end) {
   typedef typename std::iterator_traits<Iter>::value_type vt;
   vt accum = vt();
   while (begin!=end) {
      accum += *begin;
      ++begin;
   }
   return accum;
}

Здесь "Iter" - это просто имя. На самом деле это не накладывает никаких ограничений на тип. Если вы захотите создать экземпляр этого шаблона с типом, который не является итератором (по крайней мере, в структурном смысле), вы получите ошибку во время компиляции (типизированная утка во время компиляции). Итак, часть вашей работы - документирование того, какого типа вы ожидаете. Обычно это делается путем выбора некоторых описательных имен параметров шаблона (например, ForwardIterator) и комментариев.

Я должен также упомянуть, что множественные функции «sum» будут «созданы», если вы будете использовать этот шаблон функции с различными типами итераторов. Если вы не хотите такого дублирования кода и / или действительно нуждаетесь в полиморфизме во время выполнения, вы можете применить метод, называемый «стирание типа». Стирание типа для итераторов не является частью стандартной библиотеки. Кроме того, я никогда не чувствовал необходимости применять эту технику для итераторов. Но вы найдете использование стирания типов в других библиотеках, таких как boost :: any и boost :: function.

Есть несколько других приемов шаблонов, которые вы можете использовать, чтобы различать разные категории итераторов (см. «Диспетчеризация тегов») или ограничивать шаблон функции (см. «SFINAE»). Если вы заинтересованы в стирании типов, попробуйте поискать googling для c ++, стирание типов, итератор. Вы в основном создаете класс дескриптора, который управляет полиморфным объектом (через указатель). Этот полиморфный объект оборачивает некоторый другой объект, тип которого вы хотите «стереть» (скрыть).

Answer 3

Лучше всего указать в соглашении об именах тип итератора и впоследствии тип свойств, которыми должен обладать итератор. Ниже приведены некоторые общие правила именования для итераторов:

template<typename Iterator>
void foo_iterator(Iterator begin, Iterator end)
{
   typedef typename std::iterator_traits<Iterator>::value_type T;
   ....
}

template<typename RandomIterator>
void foo_random_iterator(RandomIterator begin, RandomIterator end)
{
   typedef typename std::iterator_traits<RandomIterator>::value_type T;
   ....
}

template<typename ForwardIterator>
void foo_forward_iterator(ForwardIterator begin, ForwardIterator end)
{
   typedef typename std::iterator_traits<ForwardIterator>::value_type T;
   ....
}

template<typename ReverseIterator>
void foo_forward_iterator(ReverseIterator begin, ReverseIterator end)
{
   typedef typename std::iterator_traits<ReverseIterator>::value_type T;
   ....
}

template<typename InputIterator>
void foo_input_iterator(InputIterator begin, InputIterator end)
{
   typedef typename std::iterator_traits<InputIterator>::value_type T;
   ....
}

template<typename OutputIterator>
void foo_output_iterator(OutputIterator out)
{
   // We don't have a type T, as we can't "always"
   // know the type, as this type of iterator is a sink.
   ....
}

Ниже приведено общее определение для контейнеров типа последовательности, которые включают в себя vector и deque.

template <typename T,
          class Allocator,
          template <class,class> class Sequence>
inline void foo_sequence(Sequence<T,Allocator>& sequence)
{
   ....
}

Answer 4

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

Итак, в приведенном выше примере вы можете переписать функцию следующим образом:

template<typename T>
void some_function(std::forward_iterator<T> data) {
   ...
}

для чего-то, что требует возможности перемещать итератор вперед (++) по коллекции.