Container description
I am building a container that is meant to store sorted unsigned integer values in a very RAM efficient manner. The idea is to group values by common radix. Instead of
std::vector<unsigned int> V = {1234,1254,1264,1265,1267,1268,1271,1819,1832,1856,
1867,1892,3210,3214,3256,3289};
I would have something like
MyContainer V =
{
{12..
..34, ..54, ..64, ..65, ..67, ..68, ..71
},
{18..
..19, ..32, ..56, ..67, ..92
}
{32..
..10, ..14, ..56, ..89
}
};
Briefly, here is the organization of this container...
class MyContainer
{
// attribute
std::vector<Block> data;
// methods
// ..
}
class Block
{
// attributes
unsigned short radix;
std::vector<unsigned short> suffixs; // contains all the suffix associated with this radix
// methods
// ..
}
While advice about this data structure would be welcome, the core of my question is about the implementation of the iterator.
Iterator
I am having issues when building the iterator. It is my first time building a classic iterator design pattern and I am likely making mistakes. Here are the attributes of my iterator
class Iterator
{
// attributes
std::vector<Block>::iterator bigP; // points to a Block
std::vector<unsigned short>::iterator smallP; // points to an unsigned int within the Block pointed by bigP
std::vector<Block>::iterator bigPEnd;
// methods
// ...
}
Q1: Should MyContainer::iterator contains iterators (as it is currently the case) or should it contain pointers? Why?
I thought that when the iterator points to the last unsigned int of a Block, then the operator++() should push bigP to the next Block and push smallP to the first element of the
It seems wrong to me that I have to include an iterator to the data.end() (called bigPEnd) but I ended up adding it when I realize that when the operator++() is called while the MyContainer::iterator points to the last unsigned int of the last Block, I had to know that I can't set smallP to bigP->begin() as this would lead to a segmentation fault as *bigP does not exist.
Q2: Do I need a pointer to the last element of data? How to avoid it?
I am also facing a similar issue when building an MyContainer::iterator for an empty vector. Typically, I would construct an iterator with
MyContainer::iterator MyContainer::begin()
{
return iterator(data.begin(), data.front().suffixs.begin(), data.end());
// ^^ ^^ ^^
// bigP smallP bigPEnd
}
However, data.front() will lead to a segmentation fault when data is empty. If I used pointers I could set smallP to nullptr when data is empty and when bigP == data.end() whether or not the data is empty.
Q3: How can I deal with smallP when there is nothing to point to?
Can you please give me some advice on the implementation of this iterator?
Aucun commentaire:
Enregistrer un commentaire