CODEWITHSUNDEEP
c++sorting
Adeeb
Adeeb

Reputation: 1271

How does sorting in c++ work?

I'm a Java developer. I'm currently learning C++. I've been looking at code samples for sorting. In Java, one normally gives a sorting method the container it needs to sort e.g

sort(Object[] someArray)

I've noticed in C++ that you pass two args, the start and end of the container. My question is that how is the actual container accessed then?

Here's sample code taken from Wikipedia illustrating the the sort method

#include <iostream>
#include <algorithm>
#include <vector>
int main() {
 std::vector<int> vec;
 vec.push_back(10); vec.push_back(5); vec.push_back(100); 
 std::sort(vec.begin(), vec.end());
 for (int i = 0; i < vec.size(); ++i) 
     std::cout << vec[i] << ' ';
}

Upvotes: 2

Views: 932

Answers (5)

Baptiste Wicht
Baptiste Wicht

Reputation: 7663

vec.begin() and vec.end() are returning iterators iterators. The iterators are kind of pointers on the elements, you can read them and modify them using iterators. That is what sort is doing using the iterators.

If it is an iterator, you can directly modify the object the iterator is referring to: 

*it = X;

The sort function does not have to know about the containers, which is the power of the iterators. By manipulating the pointers, it can sort the complete container without even knowing exactly what container it is.

You should learn about iterators (http://www.cprogramming.com/tutorial/stl/iterators.html)

Upvotes: 3

Joseph Mansfield
Joseph Mansfield

Reputation: 110648

vec.begin() and vec.end() do not return the first and last elements of the vector. They actually return what is known as an iterator. An iterator behaves very much like a pointer to the elements. If you have an iterator i that you initialised with vec.begin(), you can get a pointer to the second element in the vector just by doing i++ - the same as you would if you had a point to the first element in an array. Likewise you can do i-- to go backwards. For some iterators (known as random access iterators), you can even do i + 5 to get an iterator to the 5th element after i.

This is how the algorithm accesses the container. It knows that all of the elements that it should be sorting are between begin() and end(). It navigates around the elements by doing simple iterator operations. It can then modify the elements by doing *i, which gives the algorithm a reference to the element that i is pointing at. For example, if i is set to vec.begin(), and you do *i = 5;, you will change the value of the first element of vec.

This approach allows you to pass only part of a vector to be sorted. Let's say you only wanted to sort the first 5 elements of your vector. You could do:

std::sort(vec.begin(), vec.begin() + 5);

This is very powerful. Since iterators behave very much like pointers, you can actually pass plain old pointers too. Let's say you have an array int array[] = {4, 3, 2, 5, 1};, you could easily call std::sort(array, array + 5) (because the name of an array will decay to a pointer to its first element).

Upvotes: 2

aschepler
aschepler

Reputation: 72271

Iterators act like references into part of a container. That is, *iter = z; actually changes one of the elements in the container.

std::sort actually uses a swap function on references to the contained objects, so that any iterators you have already initialized remain in the same order but the values those iterators refer to are changed.

Note that std::list also has member functions called sort. It works the other way around: any iterators you have already initialized keep the same values, but the order of those iterators changes.

Upvotes: 0

abarnert
abarnert

Reputation: 365597

The container doesn't have to be accessed. That's the whole point of the design behind the Standard Template Library (which became part of the C++ standard library): The algorithms don't know anything about containers, just iterators.

This means they can work with anything that provides a pair of iterators. Of course all STL containers provide begin() and end() methods, but you can also use a regular old C array, or an MFC or glib container, or anything else, just by writing your own iterators for it. (And for C arrays, it's as simple as a and a+a_len for the begin and end iterators.)

As for how it works under the covers: Iterators follow an implicit protocol: you can do things like ++it to advance an iterator to the next element, or *it to get the value of the current element, or *it = 3 to set the value of the current element. (It's a bit more complicated than this, because there are a few different protocols—iterators can be random-access or forward-only, const or writable, etc. But that's the basic idea.) So, if `sort is coded to restrict itself to the iterator protocol (and, of course, it is), it works with anything that conforms to that protocol.

To learn more, there are many tutorials on the internet (and in the bookstore); there's only so much an SO answer can explain.

Upvotes: 1

djechlin
djechlin

Reputation: 60748

begin() and end() return iterators. See e.g. http://www.cprogramming.com/tutorial/stl/iterators.html

Upvotes: 0

Related Questions