C ++ API for returning sequences in a general way

Question

If I write a library, and I have a function that should return a sequence of values, I could do something like:

std::vector<int> get_sequence(); 

However, for this, the library user needs to use the std :: vector <> container, and not allow them to use any container that they want to use. In addition, it can add an additional copy of the returned array (depending on whether the compiler can optimize it or not), which can adversely affect performance.

Theoretically, you can allow the use of arbitrary containers (and avoid unnecessary additional copying) by creating a template function that starts and ends it:

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

Then the function will save the sequence values ​​in the range specified by iterators. But the problem is that this requires knowing the size of the sequence so that you have enough elements between begin and end to save all the values ​​in the sequence.

I thought of an interface, for example:

 template<T_insertIter> get_sequence(T_insertIter inserter); 

which requires the T_insertIter to be an insert iterator (e.g. created using std::back_inserter(my_vector) ), but this seems too easy to use because the compiler would happily accept an iterator without insert, but would behave incorrectly at runtime.

So, is there a best practice for developing common interfaces that return sequences of arbitrary length?

Answer 1

Gets the get_sequence (custom) forward_iterator class, which generates a sequence on demand. (It could also be a more advanced type of iterator like bidirectional_iterator , if that is practical for your sequence.)

Then the user can copy the sequence to any type of container that they need. Or they can just loop directly on your iterator and skip the container completely.

You will need some kind of final iterator. Not knowing exactly how you generate the sequence, it's hard to say exactly how you should implement this. One way would be for your iterator class to have a static member function returning the final iterator, for example:

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

where ... represents any parameters needed to create the final iterator (which a private constructor can use). Then your loop will look like this:

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

Here is a trivial example of a direct iterator class that generates a sequence of consecutive integers. Obviously, this could easily be turned into an iterator with bidirectional or random access, but I wanted this example to be small.

 #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

Why do you need your interface for container independent? Scott Meyers, in his Effective STL, provides good arguments for not trying to make your code container independent, no matter how powerful the temptation is. Basically, containers are intended for a completely different use: you probably don't want to store your output on a map or install (they are not interval containers), so you are left with a vector, list and deque, and why you want to have a vector in which do you need a list and vice versa? They are completely different, and you will get better results using all the functions of one of them than trying to make both work. Well, just think about reading Effective STL: it's worth your while.

If you know something about your container, you might consider making something like

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

or maybe

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

or even control what you do with a strategy, for example

 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 3

Err ... Only my two cents, but:

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

This will remove the potential return using the copy problem. Now, if you really want to avoid overlaying the container, you can try something like:

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

This will compile only for vectors, lists, and deque (and similar containers). If you need a large set of possible containers, the code will look like this:

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

But, as stated in other posts, you must agree to limit your interface to only one type of container.

Answer 4

One thing that you need to pay special attention to is if you mean DLLs or the like with a library. Then problems may arise if the consumer of the library, say, the application, is built with a different compiler than the library itself.

Consider the case when in your example you return the value std::vector<> by value. Then the memory will be allocated in the context of the library, but freed in the context of the application. Two different compilers can allocate / release differently, and therefore chaos can occur.

Answer 5

If you already manage the memory for your sequence, you can return a pair of iterators for the caller to use in a loop or algorithm call.

If the returned sequence must manage its own memory, then everything is more confusing. You can use the @paercebal solution, or you can implement your own iterators that support shared_ptr in the sequence that they execute.

Answer 6

std::list<int> bit nicer, IMO. Please note that this does not require an additional copy of the data in the list, since only pointers are copied.

It all depends on your customers. If you can expect them to become C ++ developers, give them one of the std container classes, I say.

The only thing that happens to me is that you do this:

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

Then the caller can use std::tr1::bind so that your get_sequence function will get_sequence any function on any object (or not) that they want. You simply call f for each item you create.

Answer 7

You can do something like

 template<typename container> container get_sequence(); 

and require that the type of container supplied conform to some standard interface (for example, having a push_back member and possibly a backup, so your interface user can use vector / deque / list).

Answer 8

You can statically send an iterator type using iterator_traits

Something like that:

 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

To display the sequences, I see two options. The first is something like

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

The second is something like

 struct sequence_generator { bool has_next() { ... } your_type next() { mutate_state(); return next_value; } private: // some state }; 

that you would like to turn it into a standard C ++ iterator (using boost::iterator_facade for convenience) to use it in standard algorithms ( copy , transform , ...).

See also boost::transform_iterator , combined with some iterator that returns integers in a sequence.

Answer 10

You can pass a functor to a function that takes a single value. Then the functor will be responsible for storing the value in any container that you are currently using.

 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)); } 

Note. Here I use the boost.function function to define the functor parameter. You do not need to raise so that it can be done. It just makes it a lot easier.

You can also use a function pointer instead of a functor, but I do not recommend it. It is error prone and there is no easy way to bind data to it.

Also, if your compiler supports C ++ 0x lambda functions, you can simplify the code by eliminating the explicit definition of a functor:

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

(I'm still using VS2008, so I'm not sure if I got the lambda syntax correctly)