I have a custom doubly-linked list class and I want to implement iterator for it so I can use functions like std::sort and the one provided below. What can be done about it?
For example, now I have the implementation but it's bad. The following string
std::cout << list.end() - list.begin() << std::endl;
outputs
-179191768
where list is my list class with 10 elements in it.
The function I want to work:
template <typename I, typename C>
void quickSort(I begin, I end, C cmp) {
if (begin >= end) throw new exception_incorrectSelection;
I i = begin, j = end;
T pivot = *(i + (j - i) / 2);
while (i <= j) {
while (cmp(*i, pivot)) ++i;
while (cmp(pivot, *j)) --j;
if (i <= j) {
std::iter_swap(i, j);
++i;
--j;
}
}
if (j > begin) quickSort(begin, j, cmp);
if (i < end) quickSort(i, end, cmp);
}
It breaks on exeption check for the reason expressed earlier.
Iterators come in various categories. For a doubly-linked list, you'd normally implement a bidirectional iterator. A bidirectional iterator won't support std::sort, but will support many (most?) other algorithms, such as find, find_if, accumulate, and so on.
You could write an iterator for a doubly-linked list that supported the RandomAccessIterator concept (e.g., supported iterator + int and iterator - int) but it's open to question whether you'd really want to--you normally expect a random access iterator to provide constant time addition and subtraction, but with a linked list, they'd be linear time instead. As such, even though you're supporting the concept in terms of the operations it's required to support, you're violating the requirements on complexity:
The
RandomAccessIteratorconcept adds support for constant-time advancement with +=, +, -=, and -, as well as the computation of distance in constant time with -. Random access iterators also support array notation via subscripting.
[emphasis added]
So, although you could make it work with std::sort if you wanted, it's probably not a great idea to do so.
That leaves two choices: go ahead and produce the same interface anyway, and live with the fact that the random-access operations will have linear complexity, or rewrite your algorithm to work with what bidirectional iterators can provide. That would look something like this:
template <typename I, typename C>
void quickSort(I begin, I end, C cmp) {
if (begin >= end) throw new exception_incorrectSelection;
I i = begin, j = end;
T pivot = *(i + std::distance(i, j) / 2); // <--
while (i <= j) {
while (cmp(*i, pivot)) ++i;
while (cmp(pivot, *j)) --j;
if (i <= j) {
std::iter_swap(i, j);
++i;
--j;
}
}
if (j > begin) quickSort(begin, j, cmp);
if (i < end) quickSort(i, end, cmp);
}
At least as usually implemented, std::distance will do something like this:
template <class Iter>
size_t distance(Iter a, Iter b) {
size_t ret = 0;
while (a != b) {
++a;
++ret;
}
return ret;
}
...so as long as your iterator supports ++ and !=, that'll normally be enough for it to work with std::distance.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments