C ++ API для возврата последовательностей общим способом

Question

Если я пишу библиотеку и у меня есть функция, которая должна возвращать последовательность значений, я мог бы сделать что-то вроде:

std::vector<int> get_sequence();

Однако это требует от пользователя библиотеки использовать контейнер std :: vector <>, а не разрешать ему использовать любой контейнер, который он хочет использовать. Кроме того, он может добавить дополнительную копию возвращаемого массива (в зависимости от того, может ли компилятор оптимизировать это или нет), что может оказать негативное влияние на производительность.

Вы можете теоретически разрешить использование произвольных контейнеров (и избежать ненужного дополнительного копирования), создав шаблонную функцию, которая принимает начало и конец:

template<class T_iter> void get_sequence(T_iter begin, T_iter end);

Функция сохранит значения последовательности в диапазоне, заданном итераторами. Но проблема в том, что вам необходимо знать размер последовательности, чтобы у вас было достаточно элементов от begin до end, чтобы сохранить все значения в последовательности.

Я думал об интерфейсе, таком как:

template<T_insertIter> get_sequence(T_insertIter inserter);

, который требует, чтобы T_insertIter был итератором вставки (например, созданным с помощью std::back_inserter(my_vector)), но это кажется слишком простым для неправильного использования, так как компилятор с радостью принял бы итератор без вставки, но во время выполнения работал бы неправильно 1017 *

Итак, есть ли лучший способ разработки универсальных интерфейсов, которые возвращают последовательности произвольной длины?

Answer 1

Пусть get_sequence возвращает (пользовательский) класс forward_iterator, который генерирует последовательность по требованию. (Это также может быть более продвинутый тип итератора, например bidirectional_iterator, если это целесообразно для вашей последовательности.)

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

Вам понадобится какой-то конечный итератор. Не зная точно, как вы генерируете последовательность, трудно сказать, как именно вы должны это реализовать. Одним из способов было бы, чтобы ваш класс итератора имел статическую функцию-член, возвращающую конечный итератор, например:

static const my_itr& end() { static const my_itr e(...); return e; };

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

for (my_itr i = get_sequence(); i != my_itr::end(); ++i) { ... }

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

#include <iterator>

class integer_sequence_itr
  : public std::iterator<std::forward_iterator_tag, int>
{
 private:
  int i;

 public:
  explicit integer_sequence_itr(int start) : i(start) {};

  const int& operator*()  const { return i; };
  const int* operator->() const { return &i; };

  integer_sequence_itr& operator++() { ++i; return *this; };
  integer_sequence_itr  operator++(int)
    { integer_sequence_itr copy(*this); ++i; return copy; };

  inline bool operator==(const integer_sequence_itr& rhs) const
    { return i == rhs.i; };

  inline bool operator!=(const integer_sequence_itr& rhs) const
    { return i != rhs.i; };
}; // end integer_sequence_itr

//Example:  Print the integers from 1 to 10.
#include <iostream>

int main()
{
  const integer_sequence_itr stop(11);

  for (integer_sequence_itr i(1); i != stop; ++i)
    std::cout << *i << std::endl;

  return 0;
} // end main

Answer 2

Э-э-э ... Только мои два цента, но:

void get_sequence(std::vector<int> & p_aInt);

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

template <typename T>
void get_sequence(T & p_aInt)
{
    p_aInt.push_back(25) ; // Or whatever you need to add
}

Это скомпилирует только для векторов, списков и deque (и аналогичных контейнеров). Если вам нужен большой набор возможных контейнеров, код будет:

template <typename T>
void get_sequence(T & p_aInt)
{
    p_aInt.insert(p_aInt.end(), 25) ; // Or whatever you need to add
}

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

Answer 3

Почему ваш интерфейс должен быть независимым от контейнера? Скотт Мейерс в своей «Эффективной STL» дает веские основания для , а не попыток сделать ваш код независимым от контейнера, независимо от того, насколько сильным является соблазн. По сути, контейнеры предназначены для совершенно другого использования: вы, вероятно, не хотите сохранять свои выходные данные на карте или в наборе (они не являются интервальными контейнерами), поэтому у вас остались вектор, список и дек, и почему вы хотите иметь вектор, где вам нужен список и наоборот? Они совершенно разные, и вы получите лучшие результаты, используя все функции одной из них, чем пытаетесь заставить обе работать. Что ж, просто подумайте о том, чтобы прочитать «Эффективный STL»: оно стоит вашего времени.

Если вы знаете что-то о своем контейнере, вы можете сделать что-то вроде

template void get_sequence(T_Container & container)
{
  //...
  container.assign(iter1, iter2);
  //...
}

или, может быть

template void get_sequence(T_Container & container)
{
  //...
  container.resize(size);
  //use push_back or whatever
  //...
}

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

class AssignStrategy // for stl
{
public:
  template
  void fill(T_Container & container, T_Container::iterator it1, T_Container::iterator it2){
    container.assign(it1, it2);
  }
};

class ReserveStrategy // for vectors and stuff
{
public:
  template
  void fill(T_Container & container, T_Container::iterator it1, T_Container::iterator it2){
    container.reserve(it2 - it1);
    while(it1 != it2)
      container.push_back(*it1++);
  }
};


template 
void get_sequence(T_Container & container)
{
  //...
  T_FillStrategy::fill(container, iter1, iter2);
  //...
}

Answer 4

Стоит обратить особое внимание на то, что под library имеется в виду DLL или аналог. Тогда могут возникнуть проблемы, если потребитель библиотеки, скажем, приложение, собран с другим компилятором, чем сама библиотека.

Рассмотрим случай, когда вы в своем примере возвращаете std::vector<> по значению. Затем память будет выделяться в контексте библиотеки, но освобождаться в контексте приложения. Два разных компилятора могут распределять / освобождать по-разному, поэтому может возникнуть хаос.

Answer 5

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

Если возвращаемая последовательность должна управлять своей собственной памятью, то все становится более запутанным. Вы можете использовать решение @ paercebal или реализовать собственные итераторы, которые содержат shared_ptr в последовательности, которую они повторяют.

Answer 6

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

struct vector_adder {
  vector_adder(std::vector<int>& v) : v(v) {}
  void operator()(int n) { v.push_back(n); }
  std::vector<int>& v;
};

void gen_sequence(boost::function< void(int) > f) {
  ...
  f(n);
  ...
}

main() {
  std::vector<int> vi;
  gen_sequence(vector_adder(vi));
}

Примечание: я использую здесь boost.function для определения параметра functor. Вам не нужно повышение, чтобы быть в состоянии сделать это. Это просто делает это намного проще.

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

Кроме того, если ваш компилятор поддерживает лямбда-функции C ++ 0x, вы можете упростить код, исключив явное определение функтора:

main() {
  std::vector<int> ui;
  gen_sequence([&](int n)->void{ui.push_back(n);});
}

(я все еще использую VS2008, поэтому я не уверен, правильно ли я понял лямбда-синтаксис)

Answer 7

Для вывода последовательностей я вижу два варианта. Первое что-то вроде

template <typename OutputIter>
void generate_sequence(OutputIter out)
{
    //...
    while (...) { *out = ...; ++out; }
}

Второй что-то вроде

struct sequence_generator
{
    bool has_next() { ... }
    your_type next() { mutate_state(); return next_value; }

private:
    // some state
};

, который вы хотите превратить в стандартный итератор C ++ (для удобства используйте boost::iterator_facade), чтобы использовать его в стандартных алгоритмах (copy, transform, ...).

Взгляните также на boost::transform_iterator в сочетании с некоторыми итераторами, возвращающими целые числа в последовательности.

Answer 8

Вы можете статически распределить тип итератора, используя iterator_traits

Примерно так:

template<T_insertIter> get_sequence(T_insertIter inserter)
{
   return get_sequence(inserter, typename iterator_traits<Iterator>::iterator_category());
}

template<T_insertIter> get_sequence(T_insertIter inserter, input_iterator_tag);

Answer 9

Вы могли бы сделать что-то вроде

template<typename container>
container get_sequence();

и требует, чтобы поставляемый тип контейнера соответствовал некоторому стандартному интерфейсу (например, наличие члена push_back и, возможно, резерв, чтобы пользователь вашего интерфейса мог использовать vector / deque / list).

Answer 10

std::list<int> немного приятнее, ИМО. Обратите внимание, что для этого не потребуется дополнительная копия данных в списке, поскольку копируются только указатели.

Это полностью зависит от ваших потребителей. Если вы ожидаете, что они разработчики на C ++, дайте им один из классов-контейнеров std, скажу я.

Единственное, что приходит мне в голову, это то, что вы делаете это:

void get_sequence(std::tr1::function<void(int)> f);

Тогда вызывающая сторона может использовать std::tr1::bind, чтобы ваша get_sequence функция вызывала любую функцию на любом объекте (или нет), который они хотят. Вы просто продолжаете вызывать f для каждого создаваемого вами элемента.