I made a collection for which I want to provide an STL-style, random-access iterator. I was searching around for an example implementation of an iterator but I didn't find any. I know about the need for const overloads of [] and * operators. What are the requirements for an iterator to be "STL-style" and what are some other pitfalls to avoid (if any)?
Additional context: This is for a library and I don't want to introduce any dependency on it unless I really need to. I write my own collection to be able to provide binary compatibility between C++03 and C++11 with the same compiler (so no STL which would probably break).
This question is related to
c++
iterator
const-iterator
Thomas Becker wrote a useful article on the subject here.
There was also this (perhaps simpler) approach that appeared previously on SO: How to correctly implement custom iterators and const_iterators?
The iterator_facade documentation from Boost.Iterator provides what looks like a nice tutorial on implementing iterators for a linked list. Could you use that as a starting point for building a random-access iterator over your container?
If nothing else, you can take a look at the member functions and typedefs provided by iterator_facade and use it as a starting point for building your own.
I was trying to solve the problem of being able to iterate over several different text arrays all of which are stored within a memory resident database that is a large struct.
The following was worked out using Visual Studio 2017 Community Edition on an MFC test application. I am including this as an example as this posting was one of several that I ran across that provided some help yet were still insufficient for my needs.
The struct containing the memory resident data looked something like the following. I have removed most of the elements for the sake of brevity and have also not included the Preprocessor defines used (the SDK in use is for C as well as C++ and is old).
What I was interested in doing is having iterators for the various WCHAR two dimensional arrays which contained text strings for mnemonics.
typedef struct tagUNINTRAM {
// stuff deleted ...
WCHAR ParaTransMnemo[MAX_TRANSM_NO][PARA_TRANSMNEMO_LEN]; /* prog #20 */
WCHAR ParaLeadThru[MAX_LEAD_NO][PARA_LEADTHRU_LEN]; /* prog #21 */
WCHAR ParaReportName[MAX_REPO_NO][PARA_REPORTNAME_LEN]; /* prog #22 */
WCHAR ParaSpeMnemo[MAX_SPEM_NO][PARA_SPEMNEMO_LEN]; /* prog #23 */
WCHAR ParaPCIF[MAX_PCIF_SIZE]; /* prog #39 */
WCHAR ParaAdjMnemo[MAX_ADJM_NO][PARA_ADJMNEMO_LEN]; /* prog #46 */
WCHAR ParaPrtModi[MAX_PRTMODI_NO][PARA_PRTMODI_LEN]; /* prog #47 */
WCHAR ParaMajorDEPT[MAX_MDEPT_NO][PARA_MAJORDEPT_LEN]; /* prog #48 */
// ... stuff deleted
} UNINIRAM;
The current approach is to use a template to define a proxy class for each of the arrays and then to have a single iterator class that can be used to iterate over a particular array by using a proxy object representing the array.
A copy of the memory resident data is stored in an object that handles reading and writing the memory resident data from/to disk. This class, CFilePara contains the templated proxy class (MnemonicIteratorDimSize and the sub class from which is it is derived, MnemonicIteratorDimSizeBase) and the iterator class, MnemonicIterator.
The created proxy object is attached to an iterator object which accesses the necessary information through an interface described by a base class from which all of the proxy classes are derived. The result is to have a single type of iterator class which can be used with several different proxy classes because the different proxy classes all expose the same interface, the interface of the proxy base class.
The first thing was to create a set of identifiers which would be provided to a class factory to generate the specific proxy object for that type of mnemonic. These identifiers are used as part of the user interface to identify the particular provisioning data the user is interested in seeing and possibly modifying.
const static DWORD_PTR dwId_TransactionMnemonic = 1;
const static DWORD_PTR dwId_ReportMnemonic = 2;
const static DWORD_PTR dwId_SpecialMnemonic = 3;
const static DWORD_PTR dwId_LeadThroughMnemonic = 4;
The Proxy Class
The templated proxy class and its base class are as follows. I needed to accommodate several different kinds of wchar_t text string arrays. The two dimensional arrays had different numbers of mnemonics, depending on the type (purpose) of the mnemonic and the different types of mnemonics were of different maximum lengths, varying between five text characters and twenty text characters. Templates for the derived proxy class was a natural fit with the template requiring the maximum number of characters in each mnemonic. After the proxy object is created, we then use the SetRange() method to specify the actual mnemonic array and its range.
// proxy object which represents a particular subsection of the
// memory resident database each of which is an array of wchar_t
// text arrays though the number of array elements may vary.
class MnemonicIteratorDimSizeBase
{
DWORD_PTR m_Type;
public:
MnemonicIteratorDimSizeBase(DWORD_PTR x) { }
virtual ~MnemonicIteratorDimSizeBase() { }
virtual wchar_t *begin() = 0;
virtual wchar_t *end() = 0;
virtual wchar_t *get(int i) = 0;
virtual int ItemSize() = 0;
virtual int ItemCount() = 0;
virtual DWORD_PTR ItemType() { return m_Type; }
};
template <size_t sDimSize>
class MnemonicIteratorDimSize : public MnemonicIteratorDimSizeBase
{
wchar_t (*m_begin)[sDimSize];
wchar_t (*m_end)[sDimSize];
public:
MnemonicIteratorDimSize(DWORD_PTR x) : MnemonicIteratorDimSizeBase(x), m_begin(0), m_end(0) { }
virtual ~MnemonicIteratorDimSize() { }
virtual wchar_t *begin() { return m_begin[0]; }
virtual wchar_t *end() { return m_end[0]; }
virtual wchar_t *get(int i) { return m_begin[i]; }
virtual int ItemSize() { return sDimSize; }
virtual int ItemCount() { return m_end - m_begin; }
void SetRange(wchar_t (*begin)[sDimSize], wchar_t (*end)[sDimSize]) {
m_begin = begin; m_end = end;
}
};
The Iterator Class
The iterator class itself is as follows. This class provides just basic forward iterator functionality which is all that is needed at this time. However I expect that this will change or be extended when I need something additional from it.
class MnemonicIterator
{
private:
MnemonicIteratorDimSizeBase *m_p; // we do not own this pointer. we just use it to access current item.
int m_index; // zero based index of item.
wchar_t *m_item; // value to be returned.
public:
MnemonicIterator(MnemonicIteratorDimSizeBase *p) : m_p(p) { }
~MnemonicIterator() { }
// a ranged for needs begin() and end() to determine the range.
// the range is up to but not including what end() returns.
MnemonicIterator & begin() { m_item = m_p->get(m_index = 0); return *this; } // begining of range of values for ranged for. first item
MnemonicIterator & end() { m_item = m_p->get(m_index = m_p->ItemCount()); return *this; } // end of range of values for ranged for. item after last item.
MnemonicIterator & operator ++ () { m_item = m_p->get(++m_index); return *this; } // prefix increment, ++p
MnemonicIterator & operator ++ (int i) { m_item = m_p->get(m_index++); return *this; } // postfix increment, p++
bool operator != (MnemonicIterator &p) { return **this != *p; } // minimum logical operator is not equal to
wchar_t * operator *() const { return m_item; } // dereference iterator to get what is pointed to
};
The proxy object factory determines which object to created based on the mnemonic identifier. The proxy object is created and the pointer returned is the standard base class type so as to have a uniform interface regardless of which of the different mnemonic sections are being accessed. The SetRange() method is used to specify to the proxy object the specific array elements the proxy represents and the range of the array elements.
CFilePara::MnemonicIteratorDimSizeBase * CFilePara::MakeIterator(DWORD_PTR x)
{
CFilePara::MnemonicIteratorDimSizeBase *mi = nullptr;
switch (x) {
case dwId_TransactionMnemonic:
{
CFilePara::MnemonicIteratorDimSize<PARA_TRANSMNEMO_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_TRANSMNEMO_LEN>(x);
mk->SetRange(&m_Para.ParaTransMnemo[0], &m_Para.ParaTransMnemo[MAX_TRANSM_NO]);
mi = mk;
}
break;
case dwId_ReportMnemonic:
{
CFilePara::MnemonicIteratorDimSize<PARA_REPORTNAME_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_REPORTNAME_LEN>(x);
mk->SetRange(&m_Para.ParaReportName[0], &m_Para.ParaReportName[MAX_REPO_NO]);
mi = mk;
}
break;
case dwId_SpecialMnemonic:
{
CFilePara::MnemonicIteratorDimSize<PARA_SPEMNEMO_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_SPEMNEMO_LEN>(x);
mk->SetRange(&m_Para.ParaSpeMnemo[0], &m_Para.ParaSpeMnemo[MAX_SPEM_NO]);
mi = mk;
}
break;
case dwId_LeadThroughMnemonic:
{
CFilePara::MnemonicIteratorDimSize<PARA_LEADTHRU_LEN> *mk = new CFilePara::MnemonicIteratorDimSize<PARA_LEADTHRU_LEN>(x);
mk->SetRange(&m_Para.ParaLeadThru[0], &m_Para.ParaLeadThru[MAX_LEAD_NO]);
mi = mk;
}
break;
}
return mi;
}
Using the Proxy Class and Iterator
The proxy class and its iterator are used as shown in the following loop to fill in a CListCtrl object with a list of mnemonics. I am using std::unique_ptr so that when the proxy class i not longer needed and the std::unique_ptr goes out of scope, the memory will be cleaned up.
What this source code does is to create a proxy object for the array within the struct which corresponds to the specified mnemonic identifier. It then creates an iterator for that object, uses a ranged for to fill in the CListCtrl control and then cleans up. These are all raw wchar_t text strings which may be exactly the number of array elements so we copy the string into a temporary buffer in order to ensure that the text is zero terminated.
std::unique_ptr<CFilePara::MnemonicIteratorDimSizeBase> pObj(pFile->MakeIterator(m_IteratorType));
CFilePara::MnemonicIterator pIter(pObj.get()); // provide the raw pointer to the iterator who doesn't own it.
int i = 0; // CListCtrl index for zero based position to insert mnemonic.
for (auto x : pIter)
{
WCHAR szText[32] = { 0 }; // Temporary buffer.
wcsncpy_s(szText, 32, x, pObj->ItemSize());
m_mnemonicList.InsertItem(i, szText); i++;
}
And now a keys iterator for range-based for loop.
template<typename C>
class keys_it
{
typename C::const_iterator it_;
public:
using key_type = typename C::key_type;
using pointer = typename C::key_type*;
using difference_type = std::ptrdiff_t;
keys_it(const typename C::const_iterator & it) : it_(it) {}
keys_it operator++(int ) /* postfix */ { return it_++ ; }
keys_it& operator++( ) /* prefix */ { ++it_; return *this ; }
const key_type& operator* ( ) const { return it_->first ; }
const key_type& operator->( ) const { return it_->first ; }
keys_it operator+ (difference_type v ) const { return it_ + v ; }
bool operator==(const keys_it& rhs) const { return it_ == rhs.it_; }
bool operator!=(const keys_it& rhs) const { return it_ != rhs.it_; }
};
template<typename C>
class keys_impl
{
const C & c;
public:
keys_impl(const C & container) : c(container) {}
const keys_it<C> begin() const { return keys_it<C>(std::begin(c)); }
const keys_it<C> end () const { return keys_it<C>(std::end (c)); }
};
template<typename C>
keys_impl<C> keys(const C & container) { return keys_impl<C>(container); }
Usage:
std::map<std::string,int> my_map;
// fill my_map
for (const std::string & k : keys(my_map))
{
// do things
}
That's what i was looking for. But nobody had it, it seems.
You get my OCD code alignment as a bonus.
As an exercise, write your own for values(my_map)
First of all you can look here for a list of the various operations the individual iterator types need to support.
Next, when you have made your iterator class you need to either specialize std::iterator_traits for it and provide some necessary typedefs (like iterator_category or value_type) or alternatively derive it from std::iterator, which defines the needed typedefs for you and can therefore be used with the default std::iterator_traits.
disclaimer: I know some people don't like cplusplus.com that much, but they provide some really useful information on this.
Here is sample of raw pointer iterator.
You shouldn't use iterator class to work with raw pointers!
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <assert.h>
template<typename T>
class ptr_iterator
: public std::iterator<std::forward_iterator_tag, T>
{
typedef ptr_iterator<T> iterator;
pointer pos_;
public:
ptr_iterator() : pos_(nullptr) {}
ptr_iterator(T* v) : pos_(v) {}
~ptr_iterator() {}
iterator operator++(int) /* postfix */ { return pos_++; }
iterator& operator++() /* prefix */ { ++pos_; return *this; }
reference operator* () const { return *pos_; }
pointer operator->() const { return pos_; }
iterator operator+ (difference_type v) const { return pos_ + v; }
bool operator==(const iterator& rhs) const { return pos_ == rhs.pos_; }
bool operator!=(const iterator& rhs) const { return pos_ != rhs.pos_; }
};
template<typename T>
ptr_iterator<T> begin(T *val) { return ptr_iterator<T>(val); }
template<typename T, typename Tsize>
ptr_iterator<T> end(T *val, Tsize size) { return ptr_iterator<T>(val) + size; }
Raw pointer range based loop workaround. Please, correct me, if there is better way to make range based loop from raw pointer.
template<typename T>
class ptr_range
{
T* begin_;
T* end_;
public:
ptr_range(T* ptr, size_t length) : begin_(ptr), end_(ptr + length) { assert(begin_ <= end_); }
T* begin() const { return begin_; }
T* end() const { return end_; }
};
template<typename T>
ptr_range<T> range(T* ptr, size_t length) { return ptr_range<T>(ptr, length); }
And simple test
void DoIteratorTest()
{
const static size_t size = 10;
uint8_t *data = new uint8_t[size];
{
// Only for iterator test
uint8_t n = '0';
auto first = begin(data);
auto last = end(data, size);
for (auto it = first; it != last; ++it)
{
*it = n++;
}
// It's prefer to use the following way:
for (const auto& n : range(data, size))
{
std::cout << " char: " << static_cast<char>(n) << std::endl;
}
}
{
// Only for iterator test
ptr_iterator<uint8_t> first(data);
ptr_iterator<uint8_t> last(first + size);
std::vector<uint8_t> v1(first, last);
// It's prefer to use the following way:
std::vector<uint8_t> v2(data, data + size);
}
{
std::list<std::vector<uint8_t>> queue_;
queue_.emplace_back(begin(data), end(data, size));
queue_.emplace_back(data, data + size);
}
}
I was/am in the same boat as you for different reasons (partly educational, partly constraints). I had to re-write all the containers of the standard library and the containers had to conform to the standard. That means, if I swap out my container with the stl version, the code would work the same. Which also meant that I had to re-write the iterators.
Anyway, I looked at EASTL. Apart from learning a ton about containers that I never learned all this time using the stl containers or through my undergraduate courses. The main reason is that EASTL is more readable than the stl counterpart (I found this is simply because of the lack of all the macros and straight forward coding style). There are some icky things in there (like #ifdefs for exceptions) but nothing to overwhelm you.
As others mentioned, look at cplusplus.com's reference on iterators and containers.
Source: Stackoverflow.com