problem with iterators

Yes, it is a good idea if that's permitted.

It's the worst idea EVER!!! The only way to do it is to have your iterator class resort the items each time an iterator reference is requested... which is... very inefficient and very not C++ standard.

Just do the random access iterator, and use std::sort() from std algorithms to sort whenever you need a sorted list. Don't forget that your iterator has to be inhertid from std iterator to be able to use std algorithms.

Pravesh Koirala (267)

@TheDestroyer
.
Will you please explain that why its such a bad idea.

@TheDestroyer: The use of external libraries is forbidden, meaning std::sort() is out of the question, same as all the STL.

+1 @Pravesh. We want to know why this is such a bad idea. It looks just fine to me.

I explained already. Doing this requires the method that returns the iterators to sort the items each time it's called in order to give a member from the sorted list (speed inefficient).

The other solution is to do it like std::map, and have 2 versions of the of the array internally, 1 saved like vectors normally do (c-array internally), and the second like std::map, where it takes a logarithmic time to fit the new element to the array to have it sorted. In the latter solution, you have double the space and a logarithmic insertion time; i.e., in O notation (O(log(n)). While you can have that logarithmic proportionality with a single call if you use an efficient algorithm for sorting, like merge sort.

The easier solution is, to do it the right way, and write a sorting function that uses iterators, and write a normal class similar to vectors. This is the best efficient way to do it, because; although the user will type 2 more lines to have a sorted list, but it will be his choice to waste more computational power if he needs a sorted list in the right time.

It seems that you misunderstood the idea. The caller will not sort each time the iterator is dereferenced. The caller will maintain a separate array with the indices to the original vector (sorted).

That is the second solution I provided. Maintaining a separate item is just like what std::map does, which is speed and space inefficient; and makes inserting items a logarithmic operation (considering you a programming genius that's gonna use binary search and not linear search to insert the right item in the right place).

And anyway, you're asking about iterators. With iterators, the only ways to do it are the 2 options I mentioned. You have no other choices.

Agree, guys?

Correct. But then it is not the worst idea ever. It is one possible solution with what it was given. That's what we wanted clarified. :-)

Thanks all for replies.

@ TheDestroyer.
i'm doing this for a school project, that expressly requires there must be an iterator that returns elements in th same order they have been inserted in the vector and one that returns sorted elements.

The worst idea ever is saving 2 versions of the same data (even if you're saving the indices); OR, having the method that returns the iterators resort each time it's call (which you're not gonna use, definitely).

And that's why std has maps and has vectors, each has its own job. Combining stuff isn't the smartest idea. Either create something similar to vectors (which was your request from the beginning), or something similar to maps.

Cheers :)

Last edited on

@NickName

then I'd be surprised that your school is asking you to have 2 different types of iterators for the same container. However, use the maps method and it should be accepted.

> The worst idea ever is saving 2 versions of the same data ...

I suppose you would be a lot happier in a world without CPU caches, disk caches, DNS caches, ...

there must be an iterator that returns elements in th same order they have been inserted in the vector
and one that returns sorted elements.

My idea was to have a 2nd array in the vector class to store sorted
indices of the array of elements and to iterate on this one.

If performance of adding or removing elements from the sequence is important, a binary search tree holding the indices (so that the iterator that needs to iterate in sorted order can do an in-order traversal of the tree) would be a better idea.

@JLBorges
Thanks for your suggestion, but talking about performance, i forgot to say that a basic requirement for this class is that all elements must be accessed in constant time, which means array-like right?
So i think that binary search three is not for this case, but tell me if i'm wrong!

> that all elements must be accessed in constant time,

In either case (array or tree), moving the iterator from one element to the next takes constant time. This is a general requirement for iterators - one must be able to iterate over a sequence in O(N) time.

The performance I was talking about was the time taken to insert or remove an element into/from the sequence. This would be O(N) for the array implementation - we need to always keep the indices in sorted order. And O( log N ) for a binary search tree implementation.

Thanks for fast answer, but what im trying to say is that also with iterators i must be able to make something like this:

1
2
3

//suppose to have creation of myVector here
myVector<int>::sortIterator start = vec.begin();
int k = start[4];

where start[4] access have to be O(1).
If i keep indices in a tree, will i be able to random access in constant time?

Last edited on

> where start[4] access have to be O(1).
> If i keep indices in a tree, will i be able to random access in constant time?

No, with a tree you will not get a random access iterator.

So it is a choice between:
array - random access in O(1), push_back and pop_back in O(N)
tree - random access in O(N), push_back and pop_back in amortised O( log N )

Last edited on

Ok, i'll go on with arrays then! Access in O(1) is fundamental for this project.
Thank you!

In either case (array or tree), moving the iterator from one element to the next takes constant time. This is a general requirement for iterators - one must be able to iterate over a sequence in O(N) time.

With all due respect, this whole statement is not true.

first: not all containers have constant time for access, and list is an example, it has linear time. In vectors and deques it's constant, and that's why you can access stuff with [] operator, while in lists you need to iterate to reach the value, and that's why it's linear.

second: O(N) is linear, constant is O(1).

Last edited on