std::sort, который также отслеживает количество уникальных записей на каждом уровне.

Как заявил @bjskishore123, вы можете использовать карту, чтобы гарантировать правильный порядок вашего набора. В качестве бонуса у вас будет оптимизированная структура для поиска (карта, конечно).

Вставка/поиск на карте занимает время O (log (n)), а обход вектора - O (n). Итак, алгоритм равен O(n*log(n)). Это такая же сложность, как и любой алгоритм сортировки, который должен сравнивать элементы: например, сортировка слиянием или быстрая сортировка.

Вот пример кода для вас:

int tmp[] = {5,5,5,5,5,5,2,2,2,2,7,7,7,7,1,1,1,1,6,6,6,2,2,2,8,8,8,5,5};
std::vector<int> values(tmp, tmp + sizeof(tmp) / sizeof(tmp[0]));
std::map<int, int> map_values;
for_each(values.begin(), values.end(), [&](int value)
{
    map_values[value]++;
});

for(std::map<int, int>::iterator it = map_values.begin();  it != map_values.end(); it++)
{
    std::cout << it->first << ": " << it->second << "times";
}

Выход:

1: 4times
2: 7times
5: 8times
6: 3times
7: 4times
8: 3times

Я не думаю, что вы можете сделать это за один проход. Допустим, вы предоставляете свой собственный comparator для сортировки, который каким-то образом пытается подсчитать дубликаты.

Однако единственное, что вы можете зафиксировать в сортировщике, это значение (может быть ссылка, но не имеет значения) текущих двух сравниваемых элементов . У вас нет другой информации, потому что std::sort больше ничего не передает сортировщику.

Теперь, как работает std::sort, элементы будут меняться местами, пока они не достигнут нужного места в отсортированном векторе. Это означает, что один элемент может быть отправлен сортировщику несколько раз, что делает невозможным точный подсчет. Вы можете подсчитать, сколько раз определенный элемент и все другие значения, равные ему, были перемещены, но не можете точно определить, сколько из них там находится.

Вместо использования вектора

При сохранении номеров по одному используйте контейнер std::multiset

Он хранится внутри в отсортированном порядке.

При сохранении каждого числа используйте карту, чтобы отслеживать количество вхождений каждого числа.

map<int, int> m;

Каждый раз, когда добавляется число, выполните

m[num]++; 

Таким образом, нет необходимости в другом проходе для подсчета количества вхождений, хотя вам нужно выполнить итерацию по карте, чтобы получить количество каждого вхождения.

=============================================================================

НИЖЕ ПРЕДСТАВЛЯЕТСЯ АЛЬТЕРНАТИВНОЕ РЕШЕНИЕ, КОТОРОЕ НЕ РЕКОМЕНДУЕТСЯ . ДАВАТЬ ЭТО, КАК ВЫ ПРОСИЛИ, СПОСОБ ИСПОЛЬЗОВАНИЯ STD::SORT.

В приведенном ниже коде используется функция сравнения для подсчета вхождений.

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

struct Elem
{
    int index;
    int num;
};

std::map<int, int> countMap; //Count map
std::map<int, bool> visitedMap;
bool compare(Elem a, Elem b)
{
    if(visitedMap[a.index] == false)
    {
        visitedMap[a.index] = true;
        countMap[a.num]++;
    }
    if(visitedMap[b.index] == false)
    {
        visitedMap[b.index] = true;
        countMap[b.num]++;
    }
    return a.num < b.num;
}

int main()
{
    vector<Elem> v;
    Elem e[5] = {{0, 10}, {1, 20}, {2, 30}, {3, 10}, {4, 20} };
    for(size_t i = 0; i < 5; i++)
        v.push_back(e[i]);

    std::sort(v.begin(), v.end(), compare);

    for(map<int, int>::iterator it = countMap.begin(); it != countMap.end(); it++)
        cout<<"Element : "<<it->first<<" occurred "<<it->second<<" times"<<endl;
} 

Вывод:

Element : 10 occurred 2 times
Element : 20 occurred 2 times
Element : 30 occurred 1 times

Если у вас много дубликатов, самый быстрый способ выполнить эту задачу, вероятно, состоит в том, чтобы сначала подсчитать дубликаты с помощью хэш-карты, то есть O(n), а затем отсортировать карту, то есть O(m log m), где m — количество уникальных значений.

Что-то вроде этого (в С++ 11):

#include <algorithm>
#include <unordered_map>
#include <utility>
#include <vector>

std::vector<std::pair<int, int>> uniqsort(const std::vector<int>& v) {
  std::unordered_map<int, int> count;
  for (auto& val : v) ++count[val];
  std::vector<std::pair<int, int>> result(count.begin(), count.end());
  std::sort(result.begin(), result.end());
  return result;
}

Есть много вариаций на тему, в зависимости от того, что именно вам нужно. Например, возможно, вам даже не нужно сортировать результат; может быть, достаточно просто иметь карту подсчета. Или, может быть, вы бы предпочли, чтобы результатом была отсортированная карта от int до int, и в этом случае вы могли бы просто построить обычный std::map вместо этого. (Это будет O(n log m).) Или, может быть, вы знаете что-то о значениях, которые ускоряют их сортировку (например, тот факт, что они представляют собой небольшие целые числа в известном диапазоне). И так далее.