Hi,
I have data that looks like:

x               f(x)
------        ---------
0.5            7.8
0.9            6.7
-5.4          6.6
0.0            6.6
1.5            7.8


The number of points is variable but in the majority of cases is under 
MaxSize=16

I used a "small vector optimization" container like

template <typename Traits>   // Traits contain the type of x and of f(x) and 
MaxSize
class Container {

private:
   typedef  std::pair<double, double> EntryType;
   boost::array< EntryType, Traits::MaxSize > mOnStack;
   std::vector< EntryType > mOnFreeStore;
};

Container<T> c (...);  // constructor with some signature

I will do the brief exercise of implementing this and its iterator and then 
test for my use-cases whether it will be faster overall
compared to using a plain vector

In my use cases, I construct my container once and after that do a lot of 
[] unchecked accesses.


At some points, rarely, I do

std::sort( c.begin(), c.end(), comparator() );

and

std::lower_bound( c.begin(), c.end(), e );

std::lower_bound requires a forward iterator and therefore an iterator that 
is default-constructible.


I tried

template <typename T>
class ContainerIterator {   // I templated this to provide the const and 
non-const version
   ContainerIterator( Container<T>&, size_t currentIndex );
   // types and operations....
private:
  Container<T>& mContainer;
  size_t  mIndex;
};

this didn't work because for ContainerIterator  to model 
random_access_iterator, it needs to provide ContainerIterator().
So I changed the reference to a pointer and set

....
   ContainerIterator()
   : mContainer(0), mIndex(0)

the problem is that under gcc43/linux
std::lower_bound(c.begin(). c.end(), e)  crashes as it tries to access at 
some stage elements of the container with the index 0.
I suspect it does so after having used the default constructor.

comments and ideas are welcome,

Hicham Mouline wrote:
[BIG CUT]
> the problem is that under gcc43/linux
> std::lower_bound(c.begin(). c.end(), e)  crashes as it tries to access at 
> some stage elements of the container with the index 0.

Last time I tried that function it worked fine (I am using linux as well).

> 
> comments and ideas are welcome,
> 

This might give you an idea:
http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.8

Hicham Mouline wrote:

> this didn't work because for ContainerIterator  to model 
> random_access_iterator, it needs to provide ContainerIterator().
> So I changed the reference to a pointer and set
> 
> ...
>    ContainerIterator()
>   : mContainer(0), mIndex(0)
> 
> the problem is that under gcc43/linux
> std::lower_bound(c.begin(). c.end(), e)  crashes as it tries to
> access at some stage elements of the container with the index 0.
> I suspect it does so after having used the default constructor.

A default-constructed iterator is allowed to be singular. Have you 
forgotten to copy/assign the container pointer member?


Martin

-- 
Quidquid latine scriptum est, altum videtur.

"Martin Eisenberg" <martin.eisenberg@udo.edu> wrote in message 
news:h8df5v$1np$1@news.eternal-september.org...
> Hicham Mouline wrote:
>
>> this didn't work because for ContainerIterator  to model
>> random_access_iterator, it needs to provide ContainerIterator().
>> So I changed the reference to a pointer and set
>>
>> ...
>>    ContainerIterator()
>>   : mContainer(0), mIndex(0)
>>
>> the problem is that under gcc43/linux
>> std::lower_bound(c.begin(). c.end(), e)  crashes as it tries to
>> access at some stage elements of the container with the index 0.
>> I suspect it does so after having used the default constructor.
>
> A default-constructed iterator is allowed to be singular. Have you
> forgotten to copy/assign the container pointer member?

Yep, in the assign operator, not the copy ctor
Thanks for that.