Though implementation problem

phantomotap · 05-15-2008, 05:45 AM

Quote:

It's not possible to declare a friend from a template type from what I understand, so the iterator cannot directly make the base class a friend.

Actually, you can, and it is really just a syntax issue, but I think it is supposed to be fixed in the next standard. Every compiler I've used has some way around the issue. This should work for GCC and MSVC:

Code:

#if defined(__GNUC__)
  #define TYPE_FRIENDLY(Type_t) friend class typify<Type_t>::type
#endif

#if defined(_MSC_VER)
  #if (_MSC_VER >= 1300)
    #define TYPE_FRIENDLY(Type_t) friend typename Type_t
  #endif
#endif

Quote:

How would I go about making a customizable helper class? Or does it not need to be customized? The helper class would delegate the functions calls between the iterator and the base. Both the base and the iterator could make it friend, if it knew the actual name of this class (not passed as a template type, that is).

Use a template class for the coupler. You can declare an instance of a template class using a type passed as a parameter to a template class as a friend, no problem.

Quote:

So... anyway, suggestions, if you wouldn't mind, as to how to accomplish this.
I was thinking I could use it to enhance the relationship between an iterator and its base class. An iterator should be used to specify a range within the base class, and not a range within the data stored in the class. So if it resizes, and data is moved, the iterator would be invalidated. The base class notifies the iterator of this and allows the iterator to set a new position within the new memory region. Or it could simply tell the iterator that it is now invalidated, to catch mistakes.

Read up on the observer pattern--where the iterator would be registered implicitly as part of obtaining the iterator.

Quote:

Another would be that the iterator can ask the parent for the value at pos X, allow for greater customization of the iterator (it could work better, with more classes). And the best of all is that it could ask the parent to set data, as well. This is especially useful in a ranged iterator which emulates iterator behaviour (since there's not 1 element to change, there's several).

That's what all iterators do after a fashion--even this not range iterator, ranged iterator of yours. A vector based iterator need not do this, but an iterator for a table based container, for example, must do this. (The 'X' in most cases is "my position".)

Quote:

I was thinking of specializing std::backward_copy too. But I would need to specialize a version which uses my iterators, which again would leave the work with the iterators (the iterator would have to do the work!). So by better communication with the base class, it could avoid doing
*dst++ = *src++;
Would would be inefficient.

It would probably be faster if this iterator of yours did do most of the work--with an appropriate allocator/sharing the allocation object of the container object. If the iterator is used to overwrite existing data the container object need not be involved, but if the iterator is used to extend data, append/insert additional data, spawning an instance of a list and inserting all the new data in the target container object would be much better than calling the container object for each insertion--at least for vector based containers.

Soma

Elysia · 05-15-2008, 05:54 AM

Thanks for the insights.

Quote:

Originally Posted by phantomotap

It would probably be faster if this iterator of yours did do most of the work--with an appropriate allocator/sharing the allocation object of the container object. If the iterator is used to overwrite existing data the container object need not be involved, but if the iterator is used to extend data, append/insert additional data, spawning an instance of a list and inserting all the new data in the target container object would be much better than calling the container object for each insertion--at least for vector based containers.

Yes, I was planning on delegating (right word?) a call to the base telling it that we want to replace region X with region Y, which should be far better then just calling once for each character.

**CornedBee** · 05-15-2008, 07:30 AM

There's no need for anything templated here. The iterators only need to be friends of the specific instantiation they belong to.

Code:

template <typename T>
class foo
{
  class inner;
  friend class inner;
  class inner
  {
    friend class foo<T>;
  };
};

Elysia · 05-15-2008, 07:35 AM

Only, the iterators are free classes and not nested and do not belong to any specific class.
It's supposed to be a generic iterator.

On a side note, does Microsoft's implementation of STL really not care at all between the difference of constant iterators and non-constant iterators?

Code:

	_OutIt __CLRCALL_OR_CDECL _Copy_backward_opt(_InIt _First, _InIt _Last, _OutIt _Dest,
		random_access_iterator_tag, _Nonscalar_ptr_iterator_tag, _Range_checked_iterator_tag)
	{ // copy [_First, _Last) backwards to [..., _Dest), arbitrary iterators
	// if _OutIt is range checked, this will make sure there is enough space for the copy
	// Last and first iterators are constant, while _Dest is not! _Last - _First will produce a new const_iterator,
	// which in turn cannot be subtracted from a non-constant iterator.
	_OutIt _Result = _Dest - (_Last - _First);
	_Copy_backward_opt(_First, _Last, _CHECKED_BASE(_Dest),
		forward_iterator_tag(), _Nonscalar_ptr_iterator_tag(), _Range_checked_iterator_tag());
	return _Result;
	}

It really seems as it just treats them as mere classes that emulates the behaviour of a pointer.
What to do about this...?

**CornedBee** · 05-15-2008, 07:45 AM

Quote:

Only, the iterators are free classes and not nested and do not belong to any specific class.
It's supposed to be a generic iterator.

So you want to friend a typedef? Ah, that's different.

Quote:

_Last - _First will produce a new const_iterator

No, that's incorrect. _Last - _First will produce a signed integer (the iterator's difference_type), and subtracting that from _Dest therefore produces the same type as _Dest.

Elysia · 05-15-2008, 07:49 AM

Quote:

Originally Posted by CornedBee

So you want to friend a typedef? Ah, that's different.

Yep, that's what I was after.

Quote:

No, that's incorrect. _Last - _First will produce a signed integer (the iterator's difference_type), and subtracting that from _Dest therefore produces the same type as _Dest.

Yes, with a normal iterator, perhaps, but not with my iterator class (which I'm trying to pass to std::backward_copy).
Although I don't remember why I cancelled the plans to add an overloaded operator - that returns a uint32_t (in32_t).

That seems kind of stupid. An iterator shouldn't return an integer (or should it?). I have a Iterator::Difference non-member for that. To find the difference between two iterators (or how far apart they are).
Perhaps my iterators are just too incompatible, in case I could need to transform them into an STL iterator...

**CornedBee** · 05-15-2008, 07:51 AM

Quote:

Yes, with a normal iterator, perhaps, but not with my iterator class.

Then the iterator is broken, sorry. If you don't conform to the concept, don't expect it to work with the algorithms.
The requirement is that for
Iterator it1, it2;
it1 - it2 == distance between the iterators
and typeof(it1 - it2) == iterator_traits<Iterator>::difference_type.

Elysia · 05-15-2008, 07:54 AM

Quote:

Originally Posted by CornedBee

Then the iterator is broken, sorry. If you don't conform to the concept, don't expect it to work with the algorithms.

Yes, that's what I'm struggling with.
I think I'm just going to make a member to create an STL iterator from it since STL's iterators are just so inheritably unsafe. Not to mention they'll be incompatible with my algorithms anyway.

So conversion to/from STL iterators may be necessary...
I wonder if just constructing iterator/const_iterator and giving it a pointer will suffice?

**CornedBee** · 05-15-2008, 08:01 AM

Quote:

I wonder if just constructing iterator/const_iterator and giving it a pointer will suffice?

Huh? You mean string::iterator? No, the only ways to obtain valid iterators to a container are the member functions (begin(), end(), and sometimes find() or similar) and modification of existing iterators.

phantomotap · 05-15-2008, 08:04 AM

Quote:

There's no need for anything templated here. The iterators only need to be friends of the specific instantiation they belong to.

My understanding: He wants 'template <> class container', 'template <> class iterator', and a third class that functions as a bidirectional proxy, and he wants anyone to be able to provide a different 'template <> class container' that will work and work well with his implementation of 'template <> class iterator' by utilizing a specific instantiation/implementation of the proxy. Because he assumes that the proxy may need access to private details he wants to be able to declare any instantiation/implementation of the proxy as a friend of 'template <> class iterator'. The standard lacks the syntax specifics to declare a type passed as a template parameter as a friend so he can't just take the proxy class as a parameter to his implementation. A simple and portable way around the issue is in naming the proxy 'template <> class proxy' which would still allow any customization by means of template specialization.

Of course, I may have misunderstood what he wants.

Soma

Elysia · 05-15-2008, 08:22 AM

Quote:

Originally Posted by phantomotap

My understanding: He wants 'template <> class container', 'template <> class iterator', and a third class that functions as a bidirectional proxy, and he wants anyone to be able to provide a different 'template <> class container' that will work and work well with his implementation of 'template <> class iterator' by utilizing a specific instantiation/implementation of the proxy. Because he assumes that the proxy may need access to private details he wants to be able to declare any instantiation/implementation of the proxy as a friend of 'template <> class iterator'. The standard lacks the syntax specifics to declare a type passed as a template parameter as a friend so he can't just take the proxy class as a parameter to his implementation. A simple and portable way around the issue is in naming the proxy 'template <> class proxy' which would still allow any customization by means of template specialization.

Of course, I may have misunderstood what he wants.

Soma

I think I'll get to adding something like that later, but it's about like that.
Say that CStringEx::resize is called and resizes the internal buffer. The function will now attempt to notify any iterators bound to it of this change and allow that iterator to update its members to reflect that.

Another example is that CIterator::operator * is called. The iterator then attempts to notify the base class that "we are going to change this for this." The base class will know what to do.

Another example is specialization of std::backward_copy and std::copy.
Instead of doing
*dst++ = *src++;
It could call CIterator::backward_copy or CIterator::copy, which in turn would call CStringEx::backward_copy or CStringEx::copy and let it copy the entire range at once.

Presumably, this communication is done by calling protected or private members. Therefore, the classes may need to be friends of each other or specific functions.
But...

Code:

template<typename T> void foo(T class)
{
    friend class T; // Doesn't work
}

An even better way is a proxy between the classes - just like the traits.
By doing this, I could specify the class that acts as proxy and call public methods in that class.

CIterator::copy calls CProxy::copy.
CProxy::copy could then call CStringEx::copy.

If I wanted different behaviour, I could make a new class, derive from CProxy and overload the functions where I wanted different behaviour.
This also adds an advantage that I can keep communication in free functions. Like
CIterator::copy would call CProxy::copy which would call ::copy_helper.
This would work better with free functions.

But regarding the iterator, I need to do:

Code:

std::copy_backward(vIndex, vCopyEnd, vCopyStart);

But my iterators are incompatible with STL, so I'm providing functions to get an STL iterator instead:

Code:

std::copy_backward(vIndex.GetSTLIterator(), vCopyEnd.GetSTLIterator(), vCopyStart.GetSTLIterator());

Now the question is: how do I implement them? Can I simply do such as:

Code:

std::iterator<type> it(m_pPos);
return it;

Or must it be in the lines of:

Code:

Template typename std::basic_string<VecT>::const_iterator CConstIteratorTmpl::GetSTLIterator()
{
	std::basic_string<VecT> t;
	typename std::basic_string<VecT>::const_iterator it = t.begin();
	it._Myptr = this->m_pCurPos;
	return it;
}

?

phantomotap · 05-15-2008, 08:57 AM

O_o

Anyway, as for your iterator problems: your conceptual iterator implementation is a problem because it violates the nature of iterators... primarily because you seem to be trying too hard to avoid traditional iterators.

Quote:

Now the question is: how do I implement them?

Code:

std::iterator<type> it(m_pPos);
return it;

Compatibility with the STL iterators implies certain constructs. That is all. There is no magic. You can certainly make that code work, but that will not change the coding burden. Trying to fit a incompatible implementation into the normal iterator interface will remain a problem. Eventually, if you want STL compatibility, you will have to write it.

In all honesty, you need to provide for the minimum of a traditional bidirectional iterator implementation for your class first; then you can write your global iterator, your "not a range iterator, ranged iterator", "bidirectional observer iterator thing", and others in terms of the traditional iterator and container interfaces.

What exactly is incompatible about the default iterator returned when you use 'begin()'--whatever it may be called?

Soma

Elysia · 05-15-2008, 09:08 AM

Here is the base class for my iterators:

Code:

 template<typename VecT, typename VecTraits, typename Base, typename BaseIterator, typename DerefType> class CIteratorBase:
			public boost::addable<CIteratorBaseTmpl, uint32_t>,
			public boost::subtractable<CIteratorBaseTmpl, uint32_t>,
			public boost::addable<CIteratorBaseTmpl>,
			public boost::subtractable<CIteratorBaseTmpl>
			//public std::iterator<std::random_access_iterator_tag, VecT>
		{
		public:
			CIteratorBase();
			CIteratorBase(DerefType* pStartPos, const VecT* pRangeStart, const VecT* pRangeEnd);
			CIteratorBase(const CConstIterator<VecT, VecTraits, Base>& rSrc);
			CIteratorBase(const CIterator<VecT, VecTraits, Base>& rSrc);
			CIteratorBase& operator ++ ();
			CIteratorBase operator ++ (int);
			CIteratorBase& operator -- ();
			CIteratorBase operator -- (int);
			CIteratorBase& operator += (uint32_t nPos);
			CIteratorBase& operator -= (uint32_t nPos);
			CIteratorBase& operator += (const CIteratorBaseTmpl& vPos);
			CIteratorBase& operator -= (const CIteratorBaseTmpl& vPos);
			DerefType& operator * () const;
			CIteratorValue<uint32_t, DerefType, VecTraits, Base, CIteratorBase, DerefType>* operator -> ();
			bool valid();
			friend bool operator < <> (const CIteratorBaseTmpl& rLeft, const CIteratorBaseTmpl& rRight);
			friend bool operator == <> (const CIteratorBaseTmpl& rLeft, const CIteratorBaseTmpl& rRight);
			friend bool operator > <> (const CIteratorBaseTmpl& rLeft, const CIteratorBaseTmpl& rRight);
			friend bool operator != <> (const CIteratorBaseTmpl& rLeft, const CIteratorBaseTmpl& rRight);
			CIteratorBase& operator = (const CIteratorBase& rSrc);
			void SetSafe();

			friend uint32_t Difference <> (const CIteratorBaseTmpl& v1, const CIteratorBaseTmpl& v2);

		protected:
			/*template<typename T> */void Copy(const CIteratorBaseTmpl& rObj);

			DerefType* m_pCurPos;
			const VecT* m_pRangeStart;
			const VecT* m_pRangeEnd;
			bool bUnsafe;
			CIteratorValue<uint32_t, DerefType, VecTraits, Base, CIteratorBaseTmpl, DerefType> m_Value;
#ifdef _DEBUG
			void DebugChecks() const;
#endif
		};

The incompability is this line in STL:

Code:

	_OutIt _Result = _Dest - (_Last - _First);

As I explained, using operator - on my iterator will cause it to return an object of itself, not the distance between them.
OK, so it might be fine, but again, it's mixing iterators. _Last and _First are constant. They are incompatible with _Dest which is non-constant.
STL is incredibly unsafe. It completely disregards the const and assigns anyway.

Even trying to fit an iterator into this design gives incredible amount of headaches.
I didn't even want a const_iterator at first but I had to due to const functions.
There I need to provide conversion.

STL is working in extremely unsafe ways that just won't be compatible with my implementations, I can almost guarantee that.

And since you asked... my iterator functions:

Code:

 // Iterators
		typedef Iterators::CIterator<T, Traits, CTmplStringBase> iterator;
		typedef Iterators::CConstIterator<T, Traits, CTmplStringBase> const_iterator;
		iterator begin();
		iterator end();
		//iterator EndOfString();
		const_iterator const_begin() const;
		const_iterator const_end() const;

The iterators are completely different types. They are NOT compatible.

**laserlight** · 05-15-2008, 09:21 AM

Quote:

OK, so it might be fine, but again, it's mixing iterators. _Last and _First are constant. They are incompatible with _Dest which is non-constant.
STL is incredibly unsafe. It completely disregards the const and assigns anyway.

Eh, it sounds like you misunderstand const correctness. Whether _Last and _First are constant or not, (_Last - _First) should be fine since neither _Last nor _First should be modified under the usual semantics of operator-. Likewise, _Dest - (_Last - _First) should be acceptable even if _Dest is non-const and both _Last and _First are const. How is this incredibly unsafe?

EDIT:
Gah, I hate this poor terminology. What you mean is: "_Last and _First are iterators to const objects. They are incompatible with _Dest which is an iterator to a non-const object.
STL is incredibly unsafe. It completely disregards the const and assigns anyway."

But of course, this is still nonsense. The difference between two (random access) iterators is a distance (an integer). Therefore, it does not matter whether they point to const or non-const objects, so long as they point to objects in the same range (or one past the end of the range). Subtracting an integer from a (random access) iterator results in an iterator that is further back in the range. This is all consistent with pointer arithmetic.

However, by defining an operator- that does not follow the normal semantics for iterators, you have introduced an incompatibility. It is not the STL that is unsafe, but your code that is surprising (or even shocking).

Elysia · 05-15-2008, 09:23 AM

Well, nevermind. It makes your head boggle any way you look at it.
I'm still unsure of the recommended solution, however.
An iterator is not a pointer, but the STL seems to treat them like it.
It's just incompatible with my current implementation.

05-15-2008, 07:30 AM	#168
CornedBee Cat without Hat Join Date: Apr 2003 Posts: 8,492	There's no need for anything templated here. The iterators only need to be friends of the specific instantiation they belong to. Code: template <typename T> class foo { class inner; friend class inner; class inner { friend class foo<T>; }; }; __________________ All the buzzt! CornedBee "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code." - Flon's Law
CornedBee is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
WS_POPUP, continuation of old problem	blurrymadness	Windows Programming	1	04-20-2007 06:54 PM
Laptop Problem	Boomba	Tech Board	1	03-07-2006 06:24 PM
implementation file	bejiz	C++ Programming	5	11-28-2005 01:59 AM
Sorting problem.. well actually more of a string problem	fatdunky	C Programming	5	11-07-2005 11:34 PM
Memory Problem - I think...	Unregistered	C Programming	4	10-24-2001 12:14 PM