CODEWITHSUNDEEP
c++sortingiteratorcomparator
user248884
user248884

Reputation: 911

Custom Comparator function using iterators

I have a 2D jagged vector (each row may be of different size) and a vector which represents the cost of the path in the particular row of the 2D jagged vector.

Lets call the 2D jagged vector as allpaths and the cost vector as cost. As mentioned cost[i] is the cost of the path given by allpaths[i]. allpaths[i] represents a vector of vertices in the path.

I want to sort allpaths on basis of their cost. If the cost is equal, I want to sort it on the basis of the number of vertices (size of the vector).

To do this, I have first made a vector of pairs and then sorted it. To save memory, the second argument of the pair is an iterator instead of the whole vector :

vector <pair<int, vector<string>::iterator>> V;
for(int i=0; i <allpaths.size(); i++)
    V.push_back(make_pair(cost[i], allpaths[i].begin()));
sort(V.begin(), V.end(), cmp);

The custom comparator function is as follows:

bool cmp(const pair<int, vector<string>::iterator> A, const pair<int, vector<string>::iterator> B)
{
    if(A.first == B.first)
        return *(A.second).size() < *(B.second).size();
    return A.first < B.first;
}

This returns a ton of compiler error. What is the correct way to do this? I think the error is here: *(A.second).size() < *(B.second).size()

How does one dereference an iterator to a 1D vector?

The code snippet is here

Upvotes: 1

Views: 549

Answers (2)

CygnusX1
CygnusX1

Reputation: 21778

You didn't provide a self-contained piece of code, so I cannot solve all your problems. However, I see some problems, as follows:

  • If you have a std::vector<T> with T = std::pair<int, std::vector<int>::iterator> then your comparator should take two elements of const T&. Instead, you take the whole std::vector<T>. That will not work.

  • std::vector<int>::iterator has no member function size(). As a result you cannot have A.second->size() and B.second->size(). You really need an std::vector here, not just an iterator. An iterator knows only about the element it is pointing to, not the whole vector.

However, as I explained in the comment, std::vector has a specialised swap which will work in constant time. The sorting algorithm will use that swap inside. So, you really do not need to replace an std::vector with an iterator (or a pointer to the vector).

What usually happens under the hood is that std::vector object itself is just a pointer to some dynamically allocated array (and an info about it's size). std::swap will just swap the pointer value (and size info), without copying the actual contents of the array.

Upvotes: 1

Slavadir
Slavadir

Reputation: 71

Your cmp function should accept parameters which are members of your vector, not the type of the vector itself. That is: pair<int, vector<int>::iterator>.

Upvotes: 0

Related Questions