Thread: Though implementation problem

Thanks for the insights.

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.

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>;
  };
};

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...?

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.

_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.

Originally Posted by CornedBee

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

Yep, that's what I was after.

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...

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.

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?

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.

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;
}

?

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.

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).

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.