Writing your own STL Container
Here's a sequence pseudo-container I pieced together from § 23.2.1\4 Note that the iterator_category should be one of std::input_iterator_tag, std::output_iterator_tag,std::forward_iterator_tag,std::bidirectional_iterator_tag,std::random_access_iterator_tag. Also note that the below is technically more strict than required, but this is the idea. Note that the vast majority of the "standard" functions are technically optional, due to the awesomeness that is iterators.
template <class T, class A = std::allocator<T> >
class X {
public:
typedef A allocator_type;
typedef typename A::value_type value_type;
typedef typename A::reference reference;
typedef typename A::const_reference const_reference;
typedef typename A::difference_type difference_type;
typedef typename A::size_type size_type;
class iterator {
public:
typedef typename A::difference_type difference_type;
typedef typename A::value_type value_type;
typedef typename A::reference reference;
typedef typename A::pointer pointer;
typedef std::random_access_iterator_tag iterator_category; //or another tag
iterator();
iterator(const iterator&);
~iterator();
iterator& operator=(const iterator&);
bool operator==(const iterator&) const;
bool operator!=(const iterator&) const;
bool operator<(const iterator&) const; //optional
bool operator>(const iterator&) const; //optional
bool operator<=(const iterator&) const; //optional
bool operator>=(const iterator&) const; //optional
iterator& operator++();
iterator operator++(int); //optional
iterator& operator--(); //optional
iterator operator--(int); //optional
iterator& operator+=(size_type); //optional
iterator operator+(size_type) const; //optional
friend iterator operator+(size_type, const iterator&); //optional
iterator& operator-=(size_type); //optional
iterator operator-(size_type) const; //optional
difference_type operator-(iterator) const; //optional
reference operator*() const;
pointer operator->() const;
reference operator[](size_type) const; //optional
};
class const_iterator {
public:
typedef typename A::difference_type difference_type;
typedef typename A::value_type value_type;
typedef typename const A::reference reference;
typedef typename const A::pointer pointer;
typedef std::random_access_iterator_tag iterator_category; //or another tag
const_iterator ();
const_iterator (const const_iterator&);
const_iterator (const iterator&);
~const_iterator();
const_iterator& operator=(const const_iterator&);
bool operator==(const const_iterator&) const;
bool operator!=(const const_iterator&) const;
bool operator<(const const_iterator&) const; //optional
bool operator>(const const_iterator&) const; //optional
bool operator<=(const const_iterator&) const; //optional
bool operator>=(const const_iterator&) const; //optional
const_iterator& operator++();
const_iterator operator++(int); //optional
const_iterator& operator--(); //optional
const_iterator operator--(int); //optional
const_iterator& operator+=(size_type); //optional
const_iterator operator+(size_type) const; //optional
friend const_iterator operator+(size_type, const const_iterator&); //optional
const_iterator& operator-=(size_type); //optional
const_iterator operator-(size_type) const; //optional
difference_type operator-(const_iterator) const; //optional
reference operator*() const;
pointer operator->() const;
reference operator[](size_type) const; //optional
};
typedef std::reverse_iterator<iterator> reverse_iterator; //optional
typedef std::reverse_iterator<const_iterator> const_reverse_iterator; //optional
X();
X(const X&);
~X();
X& operator=(const X&);
bool operator==(const X&) const;
bool operator!=(const X&) const;
bool operator<(const X&) const; //optional
bool operator>(const X&) const; //optional
bool operator<=(const X&) const; //optional
bool operator>=(const X&) const; //optional
iterator begin();
const_iterator begin() const;
const_iterator cbegin() const;
iterator end();
const_iterator end() const;
const_iterator cend() const;
reverse_iterator rbegin(); //optional
const_reverse_iterator rbegin() const; //optional
const_reverse_iterator crbegin() const; //optional
reverse_iterator rend(); //optional
const_reverse_iterator rend() const; //optional
const_reverse_iterator crend() const; //optional
reference front(); //optional
const_reference front() const; //optional
reference back(); //optional
const_reference back() const; //optional
template<class ...Args>
void emplace_front(Args&&...); //optional
template<class ...Args>
void emplace_back(Args&&...); //optional
void push_front(const T&); //optional
void push_front(T&&); //optional
void push_back(const T&); //optional
void push_back(T&&); //optional
void pop_front(); //optional
void pop_back(); //optional
reference operator[](size_type); //optional
const_reference operator[](size_type) const; //optional
reference at(size_type); //optional
const_reference at(size_type) const; //optional
template<class ...Args>
iterator emplace(const_iterator, Args&&...); //optional
iterator insert(const_iterator, const T&); //optional
iterator insert(const_iterator, T&&); //optional
iterator insert(const_iterator, size_type, T&); //optional
template<class iter>
iterator insert(const_iterator, iter, iter); //optional
iterator insert(const_iterator, std::initializer_list<T>); //optional
iterator erase(const_iterator); //optional
iterator erase(const_iterator, const_iterator); //optional
void clear(); //optional
template<class iter>
void assign(iter, iter); //optional
void assign(std::initializer_list<T>); //optional
void assign(size_type, const T&); //optional
void swap(X&);
size_type size() const;
size_type max_size() const;
bool empty() const;
A get_allocator() const; //optional
};
template <class T, class A = std::allocator<T> >
void swap(X<T,A>&, X<T,A>&); //optional
Also, whenever I make a container, I test with a class more or less like this:
#include <cassert>
struct verify;
class tester {
friend verify;
static int livecount;
const tester* self;
public:
tester() :self(this) {++livecount;}
tester(const tester&) :self(this) {++livecount;}
~tester() {assert(self==this);--livecount;}
tester& operator=(const tester& b) {
assert(self==this && b.self == &b);
return *this;
}
void cfunction() const {assert(self==this);}
void mfunction() {assert(self==this);}
};
int tester::livecount=0;
struct verify {
~verify() {assert(tester::livecount==0);}
}verifier;
Make containers of tester objects, and call each one's function() as you test your container. Do not make any global tester objects. If your container cheats anywhere, this tester class will assert and you'll know that you cheated accidentally somewhere.
Write C++ container that fits neatly into STL
It is not very difficult (for simple data stuctures). You should read the chapter about containers in the C++ standard. You can download the draft of the upcoming C++1x standard here :
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/#mailing2011-04
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf
You might want to use boost::iterateror_facade when writing the iterators.
http://www.boost.org/doc/libs/1_46_1/libs/iterator/doc/iterator_facade.html
Push _back for your own STL container C++
You are asking getmember() to return the first element of the array, but setmember() never fills in that element unless T is char, unsigned char, or bool, and N is 1. In any other combination, setmember() is storing the value past the end of the array. If you want to store a value in the last element, use N-1 instead (no need to calculate y as it will match N):
template <class T, int N>
void mysequence<T, N>::setmember(T value) {
memblock[N-1] = value;
}
But, that is no use in a multi-element array. Since you want to mimic push_back(), you need to have setmember() store the value in the last available element instead:
template <class T, int N>
class mysequence{
T memblock[N];
int count;
public:
mysequence() : count(0) {}
void setmember(T value);
T getmember(int x);
};
template <class T, int N>
void mysequence<T, N>::setmember(T value) {
if (count < N) {
memblock[count-1] = value;
++count;
}
else
throw length_error("sequence is full");
}
template <class T, int N>
T mysequence<T, N>::getmember(int x) {
if ((x < 0) || (x >= count))
throw out_of_range("x is out of range");
return memblock[x];
}
int main()
{
mysequence < int, 14 > myints;
myints.setmember(9);
cout << myints.getmember(0);
}
Or, you could simply get rid of your array and use a real vector instead:
template <class T>
class mysequence{
vector<T> memblock;
public:
void setmember(T value);
T getmember(int x);
};
template <class T>
void mysequence<T>::setmember(T value) {
memblock.push_back(value);
}
template <class T>
T mysequence<T>::getmember(int x) {
return memblock[x];
}
int main()
{
mysequence < int > myints;
myints.setmember(9);
cout << myints.getmember(0);
}
Writing a modern function interface to produce a populated container
The first approach is type erasure based.
template<class T>
using sink = std::function<void(T&&)>;
A sink is a callable that consumes instances of T. Data flows in, nothing flows out (visible to the caller).
template<class Container>
auto make_inserting_sink( Container& c ) {
using std::end; using std::inserter;
return [c = std::ref(c)](auto&& e) {
*inserter(c.get(), end(c.get()))++ = decltype(e)(e);
};
}
make_inserting_sink takes a container, and generates a sink that consumes stuff to be inserted. In a perfect world, it would be make_emplacing_sink and the lambda returned would take auto&&..., but we write code for the standard libraries we have, not the standard libraries we wish to have.
Both of the above are generic library code.
In the header for your collection generation, you'd have two functions. A template glue function, and a non-template function that does the actual work:
namespace impl {
void populate_collection( sink<int> );
}
template<class Container>
Container make_collection() {
Container c;
impl::populate_collection( make_inserting_sink(c) );
return c;
}
You implement impl::populate_collection outside the header file, which simply hands over an element at a time to the sink<int>. The connection between the container requested, and the produced data, is type erased by sink.
The above assumes your collection is a collection of int. Simply change the type passed to sink and a different type is used. The collection produced need not be a collection of int, just anything that can take int as input to its insert iterator.
This is less than perfectly efficient, as the type erasure creates nearly unavoidable runtime overhead. If you replaced void populate_collection( sink<int> ) with template<class F> void populate_collection(F&&) and implemented it in the header file the type erasure overhead goes away.
std::function is new to C++11, but can be implemented in C++03 or before. The auto lambda with assignment capture is a C++14 construct, but can be implemented as a non-anonymous helper function object in C++03.
We could also optimize make_collection for something like std::vector<int> with a bit of tag dispatching (so make_collection<std::vector<int>> would avoid type erasure overhead).
Now there is a completely different approach. Instead of writing a collection generator, write generator iterators.
The first is an input iterator that call some functions to generate items and advance, the last is a sentinal iterator that compares equal to the first when the collection is exhasted.
The range can have an operator Container with SFINAE test for "is it really a container", or a .to_container<Container> that constructs the container with a pair of iterators, or the end user can do it manually.
These things are annoying to write, but Microsoft is proposing Resumable functions for C++ -- await and yield that make this kind of thing really easy to write. The generator<int> returned probably still uses type erasure, but odds are there will be ways of avoiding it.
To understand what this approach would look like, examine how python generators work (or C# generators).
// exposed in header, implemented in cpp
generator<int> get_collection() resumable {
yield 7; // well, actually do work in here
yield 3; // not just return a set of stuff
yield 2; // by return I mean yield
}
// I have not looked deeply into it, but maybe the above
// can be done *without* type erasure somehow. Maybe not,
// as yield is magic akin to lambda.
// This takes an iterable `G&& g` and uses it to fill
// a container. In an optimal library-class version
// I'd have a SFINAE `try_reserve(c, size_at_least(g))`
// call in there, where `size_at_least` means "if there is
// a cheap way to get the size of g, do it, otherwise return
// 0" and `try_reserve` means "here is a guess asto how big
// you should be, if useful please use it".
template<class Container, class G>
Container fill_container( G&& g ) {
Container c;
using std::end;
for(auto&& x:std::forward<G>(g) ) {
*std::inserter( c, end(c) ) = decltype(x)(x);
}
return c;
}
auto v = fill_container<std::vector<int>>(get_collection());
auto s = fill_container<std::set<int>>(get_collection());
note how fill_container sort of looks like make_inserting_sink turned upside down.
As noted above, the pattern of a generating iterator or range can be written manually without resumable functions, and without type erasure -- I've done it before. It is reasonably annoying to get right (write them as input iterators, even if you think you should get fancy), but doable.
boost also has some helpers to write generating iterators that do not type erase and ranges.
Creating my own Iterators for non stl container
I never really used iterators before, is it correct ?
It's a good start. The idea is correct, but you are missing a few things. First, you don't have enough operators. Make sure you check the reference and provide every operator that you can sensibly provide (the only ones that may or may not be useful are random-access operators, because it could be harder to implement for this case). Second, you need to provide the iterator traits for your iterator class. This is usually done by creating the necessary nested typedefs in your iterator class (you could also specialize the std::iterator_traits template for your class, but I would say that this is only when you really cannot add the nested typedefs).
Can I inherit my MatrixIterator from
std::iteratorso stl would be able to understand it as a usual iterator ?
No, you should not, in general, inherit from the std::iterator class. The STL is a template library (generic programming (GP)) and therefore, does not use the base-class inheritance model as in OOP. The STL algorithms take iterators as template arguments, and will generically use them as required by the algorithm (or as possible by the iterator_category trait associated to the iterator type). This is generic programming, not object-oriented programming, it's apples and oranges.
Do you know a better way to do something similar ?
Well, one convenient way to do this is by using a class template like boost::iterator_facade (see ref) which provides a sort of automated "fill in the blanks" mechanism creating iterators. It uses the well-known and very useful Curiously Recurring Template Pattern (or CRTP for short). This is useful because implementing all the operators required for iterators can be quite verbose and repetitive, and the usually only really rely on just a few core operations (which is all you need to "fill in" when using a CRTP class like boost::iterator_facade).
Convention on printing STL containers for approval tests
I'm not aware of any convention or standard proposal for printing containers. However the {fmt} library can print anything range- and tuple-like: https://fmt.dev/latest/api.html#ranges-and-tuple-formatting so you could probably integrate it with ApprovalTests and avoid defining ostream insertion operators yourself.
Disclaimer: I'm the author of {fmt}.
Related Topics
Variable Initialization in C++
How Could Pairing New[] With Delete Possibly Lead to Memory Leak Only
Benefits of Initialization Lists
Propagating 'Typedef' from Based to Derived Class For 'Template'
Writing Bmp Image in Pure C/C++ Without Other Libraries
How to Retrieve All Keys (Or Values) from a Std::Map and Put Them into a Vector
What Exactly Is a Reentrant Function
The New Syntax "= Default" in C++11
Opencv Better Detection of Red Color
Selectively Disable Gcc Warnings For Only Part of a Translation Unit
Why Vector≪Bool≫::Reference Doesn't Return Reference to Bool
Why Do C and C++ Support Memberwise Assignment of Arrays Within Structs, But Not Generally
A Std::Map That Keep Track of the Order of Insertion
Why Does C++11'S Lambda Require "Mutable" Keyword For Capture-By-Value, by Default