Custom (readonly) container and iterators ?

[OReubens]

I'm working on writing some classes around a ROM hardware addon card. The classes expose the data on the ROM as a container with iterators, much like a vector or a list.

The classes don't have any data themselves, since all the data is on the ROM.

I'm having some dillemma's as to how to approach/implement the classes. If you were to write somethign like this... Or were using something like this written by someone else.... How would you expect this to be done ?

1)
Make all the member functions static, make a private constructor to prevent making instances.
This works, but may look a bit weird...

   for (auto it = RomTable::begin(); it != RomTable::end(); ++it)

2)
expect users to make a (dummy) instance, then use it as a regular container.
this might be a bit counter intuitive since the class has no datamembers.

3)
create a single instance, expect users to use that everywhere. make the constructor inaccessible.
Some C++ 'purists' might perceive this as global data and thus not a good solution ?

4) Somethign else entirely ?



--

Additionally. Do I need to provide both a const_iterator and an iterator ? There's nothing to be modified, so I'm guessing an iterator isn't needed (?) Or will some STL stuff not work without an iterator ? I'm obviously not fussed about the STL functions that make changes to the container to not work (like sort, fill, swap...)

[laserlight]

It sounds like the singleton pattern approach is correct here, except that of course it won't be a singleton per se but limited by the number of ROM addon cards.

Do I need to provide both a const_iterator and an iterator ? There's nothing to be modified, so I'm guessing an iterator isn't needed (?) Or will some STL stuff not work without an iterator ? I'm obviously not fussed about the STL functions that make changes to the container to not work (like sort, fill, swap...)

I think just providing const_iterator is correct. The STL stuff that won't work shouldn't work anyway.

[superbonzo]

If you were to write somethign like this... Or were using something like this written by someone else.... How would you expect this to be done ?

if the 'RomTable' has other members other then range access, I'd go with laserlight's suggestion of a singleton with const-only range accessors (begin() const/end() const/cbegin/cend).

if the 'RomTable' is just and only a non-mutable sequence with fixed iterator category then you could provide just the iterator class, eventually contructed from some sort of RomTable opaque 'handle':

for( auto it = RomIterator( rom_handle ), it_end = RomIterator(); it != it_end; ++it)
	...

this pattern is also not uncommon in STL and STL-inspired libraries, although I've seen it used only with input iterators or iterator adaptors ...

[OReubens]

The table's iterators are bidirectional at least.
The class is "random access" or at least, perceived to be (I can do RomTable[14]) with low overhead.

if a random access iterator only need to guarantee that something like iterator+16 will work, it's random access even. if it also needs to guarantee contiguous memory it won't be.

Functionally the class has a lot more than just STL access. it also behaves like a map in that you can access items based on a key

const RomItem& = RomTable["Root/System/Network/Protocol"];
or as parts
const RomItem& = RomTable["Root"]["System"]["Network"]["Protocol"];

There's functions to search in the ROM with various methods (by index, by name, by subname, by contents, by date, ...)

The input iterator idea while interesting, doesn't suit this particular needs

It's not actually ROM even... it's flash memory. So users "regularly" upgrade the contents through a certified/secure flash process.

[laserlight]

The class is "random access" or at least, perceived to be (I can do RomTable[14]) with low overhead.

if a random access iterator only need to guarantee that something like iterator+16 will work, it's random access even. if it also needs to guarantee contiguous memory it won't be.

I think this is a matter of whether the "low overhead" is insignificant enough that using expressions like (iterator + 16) everywhere does not pose a performance concern. If so, then provide a random access iterator. Otherwise, stick to a bidirectional iterator to discourage such access (which can still be done in a way using std::advance).

[monarch_dodra]

I don't see why you'd want a singleton here. The question should never be "can it be a singleton" but "does it have to be a singleton".

The answer to both is no anyways. For example, if your rom table has "sensor data" in the lower half, and "history data" in the higher half. I know I'd want to create 2 different RomTables to handle them.

As laserlight said: "I think just providing const_iterator is correct. The STL stuff that won't work shouldn't work anyway." Either that, or define your class as "container of const data".

[OReubens]

I think this is a matter of whether the "low overhead" is insignificant enough that using expressions like (iterator + 16) everywhere does not pose a performance concern.

What I meant is that obtaining iterator+16 is more complex than in a regular vector/array where this is just a matter of doing pointer+offset.
Calculating the RomTable iterator to do iterator+16 takes a couple calculations and a driver call.
The actual value of the offset isn't of any matter in this, doing iterator+=1 or iterator+=10000 takes the same amount of time.

So yes, there is overhead, but the overhead is not related to the relative change in offset.


I understand that a list iterator is bidirectional and not random access because the time taken to do +20 is "more or less" 20 times more than doing a +1. This is not the case in what I'm doing. Every change in the iterator is equally fast (or equally slow if you want )

Either that, or define your class as "container of const data".

Do you mean there there is a "standard" way to define/implement a "container of const data", which this container in essense is?

It's not a container of
const sometype myvar[somecount];
though.
All the access to the actual data happens through driver calls.

[laserlight]

The actual value of the offset isn't of any matter in this, doing iterator+=1 or iterator+=10000 takes the same amount of time.

So yes, there is overhead, but the overhead is not related to the relative change in offset.

I see, so random access iterators do make sense here

[OReubens]

Okay, making some more progress in this. i'm not sure yet if I'm entirely happy with it just yet

I scrapped the "everything is static" concept.
While you can do something like this (maybe looking a bit awkward)

for (auto it = RomTable<Type>::begin(); it != RomTable<Type>::end(); ++it)
...

There's no way to make static operators. and use [] operators or any of the other nice operator stuff.

const Type& = RomTable<Type>::[14]; // not valid syntax! even if worked, it looks even more wonky.

Going with the "singleton" / precreate a single instance idea

template <typename Type>
class RomTable
{
public: 
     // ... Stuff here


    static const RomTable<Type> instance;  // singleton instance

private:
   RomTable() {} // make constructor inaccessible
};

I can make everything work. but it's somewhat elaborate syntax

for (auto it = RomTable<Type>::instance.begin(); it != RomTable<Type>::instance.end(); it++)

solvable with a define
#define RomType RomTable<Type>::instance
but not everyone likes using defines for such things.

The nice part is that I can access the instance from the iterator, making some things slightly easier.


The alternative is not making an object myself, instead expecting users of the classes to instantiate an object. with the potential "problem" that all objects will basically be "the same" and iterators being interchangable which could be confusing.

RomTable<Type> foo;
RomTable<Type> bar;

for (auto it = foo.begin(); it != bar.end(); ++it)

the above works, and I can't really prevent/detect it.


Still interested in knowing if there are standardized approaches to const data.

[monarch_dodra]

The alternative is not making an object myself, instead expecting users of the classes to instantiate an object. with the potential "problem" that all objects will basically be "the same" and iterators being interchangable which could be confusing.

RomTable<Type> foo;
RomTable<Type> bar;

for (auto it = foo.begin(); it != bar.end(); ++it)

the above works, and I can't really prevent/detect it.

Nobody in their right mind would write code like this. Besides, standard containers would have exactly the same problem.

Just FYI, what you want is not strictly a container since the object does not "own" the data.

What you want is just an object that can give you a "const view" into your ROM.

Question 1) Does your container even need to be templated? Doesn't ROM just contain arbitrary binary data that needs to be interpreted by the client?
Question 2) I still don't understand why you can't model your class as a container that holds const data. You just construct it defining a upper bound and a lower bound of your ROM data, and you're all set...

[OReubens]

Nobody in their right mind would write code like this. Besides, standard containers would have exactly the same problem.

I realise nobody in their right mind would write the exact bit of code as above, but in a larger setting, it may end up happening that you're comparing 2 "incompatible" iterators.

I've by now spent quite a bit of time looking at how the vector and array classes do their thing. Their iterators are NOT interchangeable. They might be on some implementations, but using it on VS2010 in debug you get an incompatible iterators debug message. Internally this is done by comparing the start of the memory pointer.

I'm not overly worried about this, other than getting unnecessary flak/lolz/comments from the people that will be consuming the classes in their own projects.

Just FYI, what you want is not strictly a container since the object does not "own" the data.
What you want is just an object that can give you a "const view" into your ROM.

Correct. I'm well aware of this. I'm just not sure as how to approach this type of concept. I'm quite experienced at c++ in general, an windows / MFC in particular.
"too much" time spent with MFC has somewhat put me away from STL for longer than I really wanted to, so I'm catching up. With the new C++11 stuff, I'm reworking the old C interface into a C++/STL friendly approach. Or... trying to at least.

I now have something that works, I'm just not sure if it will be what people used to STL will expect.

Question 1) Does your container even need to be templated? Doesn't ROM just contain arbitrary binary data that needs to be interpreted by the client?

It is templated for a reason. While all the data comes from one single source (the hardware addon card). the data is structured. In the old C interface you had to fumble around with unions and some weird ways of working.

In the new interface I'm keeping the data structured for the most part. Using the class with a specific type means you will only get a "view" on that type of information. THe template parameter as a result serves as a sort of filter on what the container will hold.

So RomTable<foo> returns all the foo objects. RomTable<bar> returns all the bar objects. There's quite a bit of code hidden behind getting that to work, work that in the old C interface everyone had to more or less repeat for their specific case. The new c++ interface even if it has wonky/confusing syntax will be a big improvement on user convenience in that respect. Of course, if I can avoid the wonky/confusing syntax, that's even better

Question 2) I still don't understand why you can't model your class as a container that holds const data. You just construct it defining a upper bound and a lower bound of your ROM data, and you're all set...

THat is what I'm doing atm.
The header just exploses a template class with a bunch of functions that make it look like an STL container (const_iterator begin(), const_iterator end(), .... operator[] (several types) as well as member functions that do stuff that goes beyond a simple container. the class has no data. however, all the data accessing stuff is located in the .cpp.



maybe to rephrase my question:
If a class has no data and returns objects or references of a specific type. And the data it returns is random access or sequential (according to user need) and is not related to the actual instance of the object created of that class. What kind of interface on that object to you expect.
I already scrapped a pure static interface because it excludes operators.

[D_Drmmr]

I can make everything work. but it's somewhat elaborate syntax

for (auto it = RomTable<Type>::instance.begin(); it != RomTable<Type>::instance.end(); it++)

solvable with a define
#define RomType RomTable<Type>::instance
but not everyone likes using defines for such things.

People don't need to use a define, they can just write

RomTable<Type>& RomType = RomTable<Type>::instance;

The nice part is that I can access the instance from the iterator, making some things slightly easier.

I'd be very reluctant to do that. Your implementation will depend on the singleton design so much that if you ever need to change the design not to use a singleton, you'll have to start from scratch. On the other hand, if an alternative implementation (not relying on the singleton design) is cumbersome then that would be an argument for using a singleton.

The alternative is not making an object myself, instead expecting users of the classes to instantiate an object. with the potential "problem" that all objects will basically be "the same" and iterators being interchangable which could be confusing.

The objects will have unexpected copy semantics, so I would not use such a design.

It is templated for a reason. While all the data comes from one single source (the hardware addon card). the data is structured. In the old C interface you had to fumble around with unions and some weird ways of working.

In the new interface I'm keeping the data structured for the most part. Using the class with a specific type means you will only get a "view" on that type of information. THe template parameter as a result serves as a sort of filter on what the container will hold.

So RomTable<foo> returns all the foo objects. RomTable<bar> returns all the bar objects. There's quite a bit of code hidden behind getting that to work, work that in the old C interface everyone had to more or less repeat for their specific case. The new c++ interface even if it has wonky/confusing syntax will be a big improvement on user convenience in that respect. Of course, if I can avoid the wonky/confusing syntax, that's even better
...
The header just exploses a template class with a bunch of functions that make it look like an STL container (const_iterator begin(), const_iterator end(), .... operator[] (several types) as well as member functions that do stuff that goes beyond a simple container. the class has no data. however, all the data accessing stuff is located in the .cpp.

How do you do that? Do you export the template for a certain set of supported template arguments? Or do the members of the template class just call some non-template functions, which are implemented in the .cpp file? How do you instantiate the singleton instance then?

I'm also wondering what happens in the c'tor of the class. If there is some code there that can fail (e.g. if the card is missing), then using a singleton as you've shown it would be a bad idea IMO, as a user's program may crash before it enters the main function. A better approach in that case would be to either have an explicit Initialize function or use a Meyers Singleton.
It may also be a good idea to separate the singleton from the template, such that it is easier to change the creation policy of the singleton independent of it's use in client code. I.e. something like

class RomTable
{
    template <class T>
    class View; // provides iterators, etc.

    static RomTable& Instance();

    template <class T>
    View<T>& GetView();
};

This allows the singleton to do stuff related to the driver and for the view class to provide a convenient interface to get specific types of data.

[monarch_dodra]

I realise nobody in their right mind would write the exact bit of code as above, but in a larger setting, it may end up happening that you're comparing 2 "incompatible" iterators.

I've by now spent quite a bit of time looking at how the vector and array classes do their thing. Their iterators are NOT interchangeable. They might be on some implementations, but using it on VS2010 in debug you get an incompatible iterators debug message. Internally this is done by comparing the start of the memory pointer.

I'm not overly worried about this, other than getting unnecessary flak/lolz/comments from the people that will be consuming the classes in their own projects.

Interchanging iterators creates undefined behavior, simple as that. What's to keep you from checking during debug that the iterators came from the same object? All you need is to keep a pointer to the mother instance. You remove it during release. I'm pretty sure that's how MSVC does it, no? I'm not quite sure why you'd be expecting "lolz"? Because they wrote crappy code and it compiles?

If a class has no data and returns objects or references of a specific type. And the data it returns is random access or sequential (according to user need) and is not related to the actual instance of the object created of that class. What kind of interface on that object to you expect.
I already scrapped a pure static interface because it excludes operators.

Have you though of a non-template class with a template getter?

eg:

RomTable& myRomTable = RomTable::Instance();//Get singleton instance of RomTable;
//Get all the "types"
RomTable::iterator<Type> it = myRomTable.begin<Type>();
RomTable::iterator<Type> it_end = myRomTable.end<Type>();
for( ... )
...

[OReubens]

People don't need to use a define, they can just write

RomTable<Type>& RomType = RomTable<Type>::instance;

Hmm... forgot about that. Seems that even if I hide the constructor, they can still alias their way into their own confusion :-)

I'd be very reluctant to do that. Your implementation will depend on the singleton design so much that if you ever need to change the design not to use a singleton, you'll have to start from scratch. On the other hand, if an alternative implementation (not relying on the singleton design) is cumbersome then that would be an argument for using a singleton.

I do not need the singleton design.
But even without... I do have a very hard tie between the type and the actual data. It is not like a regular container where you can instantiate hundreds of different instances of a same type all pointing to different data like in a vector.

vector<int> a;
vector<int> b;

2 instancs, 2 different sets of data.

This is not the case for me. The template parameters decide the set of data, regardless of the instance.

The objects will have unexpected copy semantics, so I would not use such a design.

emmm no... The class has no data to be copied, so there can't ever be unexpected copy semantics.

How do you do that? Do you export the template for a certain set of supported template arguments? Or do the members of the template class just call some non-template functions, which are implemented in the .cpp file? How do you instantiate the singleton instance then?

I expect the classes you pass to the RomTable template to have/implement a small set of functions. I've provided the obvious classes myself, but users can make their own.

I'm also wondering what happens in the c'tor of the class.

There is no constructor. Other than an empty one I set as private to prevent multiple instances being made. From your comments in this post I'm not sure doing this is still a good idea now.

I.e. something like

I'm not sure I see the benefit in this. It seems to be functionally more or less the same as what I'm already doing but you're adding an extra indirection.
Users would need to type something like
RomTable::View<Type>::Instance()

As opposed to the
RomTable<Type>::instance
with what I have so far.

Wherein lies the real benefit in the approach you are proposing here ?

[OReubens]

Interchanging iterators creates undefined behavior, simple as that. What's to keep you from checking during debug that the iterators came from the same object? All you need is to keep a pointer to the mother instance. You remove it during release. I'm pretty sure that's how MSVC does it, no? I'm not quite sure why you'd be expecting "lolz"? Because they wrote crappy code and it compiles?

You're right, I could test for it if I wanted to. I'm not sure it's worth the effort though. This is not a case where my code would have any problems with it, they're only making it confusing for themselves. The "expecting lolz" is more a general thing. Like I said, I'm not that experienced with using STL. MFC has been my main framework for quite a while, and that does things differently than in STL. I'm quickly building some STL experience as well

Have you though of a non-template class with a template getter?

eg:

RomTable& myRomTable = RomTable::Instance();//Get singleton instance of RomTable;
//Get all the "types"
RomTable::iterator<Type> it = myRomTable.begin<Type>();
RomTable::iterator<Type> it_end = myRomTable.end<Type>();
for( ... )
...

An interesting concept. And I can see where this sort of approach would be needed. In this particular case however, it only seems to add more "stuff to type" without any obvious benefit.

As far as I understand... The above also excludes the use of operators on the RomTable class since you're delegating the type to the iterator. Not what I want in this case, as the RomTable class has other member functions besides just the ones that make it seem like a STL container and the type is needed there also.



For now, unless someone can show me a better or more standardized approach...
I have

template <typename Type, typename Config=defaultConfig, typename Key=defaultKey>
class RomTable
{
public:
    typedef RomTable<Type,Config,Key> RomTable_type;
    typedef Type value_type;
    typedef Config config_type;
    typedef Key key_type;
    typedef const Type& const_reference;

    typedef RomTable_const_iterator<table_type> const_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    enum { KeyId = DetermineKeyId<Type, Key>::KeyId };

     // STL stuff
     const_iterator begin() const  {...}
     const_iterator end() const  {...}
     const_iterator cbegin() const  {...}
     const_iterator cend() const  {...}
     const_reverse_iterator rbegin() const  {...}
     const_reverse_iterator rend() const  {...}
     const_reverse_iterator crbegin() const  {...}
     const_reverse_iterator crend() const  {...}
     size_t size() const {...}
     size_t max_size() const {...}
     bool empty() const {...}
     const_reference at(size_t index) const {...}
     const_reference operator[](size_t index) const {...}
     const_reference front() const {...}
     const_reference back() const {...}
     
    // Other stuff
    const RomTable_type& operator[](std::string strKey) const {...}
    // more stuff...
};

THe Type, Key and Config classes are required to define certain functions/values to tie it all together.

So far everything works "in theory" (I still need to actually tie it all to the actual calls into the hardware card).

RomTable<MyType> obj;
for (auto it = obj.begin(); it!=obj.end(); ++it)
{
    it->SomeFunction_From_MyType();
    int i = it->Int_FromMyType;
}

It looks simple enough... if you forget for a moment that making another RomTable<MyType> is the same functional object as any other. Instantiation results in being no more than an "alias" for the functionally static RomTable<MyType>. Weird ? Maybe. Maybe "it's simple, it works" is more important than "it looks weird, smells funny, not standard, wonky, unfamiliar approach" ?