CODEWITHSUNDEEP
c++sortingstdvector
BlueAxis
BlueAxis

Reputation: 3

[C++][std::sort] How does it work on 2D containers?

I have this vector object that contains vector of ints

std::vector<std::vector<int>> vec;

I have been trying to figure out how std::sort(vec.begin(), vec.end()) works on it. Here are my observations:

  1. 2D vectors are sorted by size.
  2. If some of inner vectors has the same size, the vector with lesser value of first element will have lesser index value.

I have been generating a few 2D vectors now, and it seems that these two are always true. However, I am doubting about my second assumption. Does std::sort really work this way, or it was just some luck that made my assumptions correct?

Upvotes: 0

Views: 94

Answers (2)

eerorika
eerorika

Reputation: 238461

Sorting vector elements works the same way as sorting any other type. std::sort uses the comparison object given as an argument. If none was passed explicitly, std::less is the default.

std::less uses operator<. As per vector documentation, it:

Compares the contents of lhs and rhs lexicographically. The comparison is performed by a function equivalent to std::lexicographical_compare.

Lexicographical comparison is a operation with the following properties:

  • Two ranges are compared element by element.
  • The first mismatching element defines which range is lexicographically less or greater than the other.
  • If one range is a prefix of another, the shorter range is lexicographically less than the other.
  • If two ranges have equivalent elements and are of the same length, then the ranges are lexicographically equal.
  • An empty range is lexicographically less than any non-empty range.
  • Two empty ranges are lexicographically equal.

In short, lexicographical sorting is the same as sorting used for dictionaries (ignoring oddities of some languages).

2D vectors are sorted by size.

Not quite. {1}, {3, 4}, {1, 2, 5} would be sorted as {1}, {1, 2, 5}, {3, 4}.

Upvotes: 6

NathanOliver
NathanOliver

Reputation: 181027

std::sort uses operator < by default to sort. Since std::vector has an overloaded operator < it uses that. std::vector::operator < does a lexicographical compare meaning it returns the vector that has the first smaller element. That means {1, 1, 2} is less than {1, 1, 3} since the 2 is less than 3. If the vectors are of different length but the smaller one has the same elements that the larger one has then the smaller one is returned. That means that

int main()
{
    std::vector a{5, 1}, b{10};
    std::cout << (a < b);
}

Prints 1 since 5 is less than 10.

int main()
{
    std::vector a{5, 10}, b{5};
    std::cout << (a < b);
}

Prints 0 since a is larger than b but they have the same common element.

Upvotes: 4

Related Questions