В данном посте я покажу как можно отсортировать смешанные данные, т.е. строки, которые содержат числа, слова, даты и.т.д.
Допустим у нас имеется файл содержащий данные в виде:
34 Jack 2016-01-22
43 Oliver 2016-01-23
3 Charlie 2016-01-20
7 Harry 2016-01-19
78 Alfie 2016-01-22
13 Thomas 2016-01-22
32 Joshua 2016-01-11
21 William 2016-01-08
17 James 2016-01-25
2 Amelia 2016-01-26
54 Daniel 2016-01-22
33 Lily 2016-01-17
11 Emily 2016-01-22
то есть каждая строка содержит цифры и слова. Нам надо отсортировать данный список по порядку так чтобы все строки содержащие цифры шли по возрастанию.
Стандартные методы сортировка естественно не подходят, но способ всё-таки есть — это натуральная сортировка.
См. листинг:
#pragma hdrstop
#pragma argsused
#ifdef _WIN32
#include <tchar.h>
#else
typedef char _TCHAR;
#define _tmain main
#endif
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;
struct Symbol {
bool is_number;
string string;
};
vector<Symbol>Tokenize(string const &input) {
string const number = "0123456789";
vector<Symbol>result;
if (!input.empty()) {
bool inside_number_token =
isdigit(static_cast<unsigned char>(input[0])) != 0;
string::size_type start_current_token = 0;
string::size_type start_next_token = 0;
do {
if (inside_number_token) {
start_next_token =
input.find_first_not_of(number, start_current_token);
}
else {
start_next_token =
input.find_first_of(number, start_current_token);
}
string const string =
input.substr(start_current_token,
start_next_token - start_current_token);
Symbol symbol;
symbol.is_number = inside_number_token;
symbol.string = string;
result.push_back(symbol);
start_current_token = start_next_token;
inside_number_token = !inside_number_token;
}
while (start_current_token != string::npos);
}
return result;
}
int ConvertToInteger(string const &number_as_string) {
istringstream converter(number_as_string);
int ganze = 0;
converter >> ganze;
return ganze;
}
struct NaturalSortOrder {
bool operator()(string const &lhs, string const &rhs) const {
vector<Symbol> const tokens_lhs = Tokenize(lhs);
vector<Symbol> const tokens_rhs = Tokenize(rhs);
for (vector<Symbol>::size_type index = 0;
index < tokens_lhs.size() && index < tokens_rhs.size(); ++index) {
Symbol const &token_lhs = tokens_lhs[index];
Symbol const &token_rhs = tokens_rhs[index];
if (token_lhs.is_number && token_rhs.is_number) {
int const number_lhs = ConvertToInteger(token_lhs.string);
int const number_rhs = ConvertToInteger(token_rhs.string);
if (number_lhs != number_rhs) {
return number_lhs < number_rhs;
}
}
else {
if (token_lhs.string != token_rhs.string) {
return token_lhs.string < token_rhs.string;
}
}
}
return false;
}
};
int _tmain(int argc, _TCHAR* argv[]) {
vector<string>filenames;
ifstream input_file("C:\myfile.txt");// файл в котором надо отсортировать данные
char line[100];
while (!input_file.eof()) {
input_file.getline(line, sizeof(line));
filenames.push_back(line);
}
sort(filenames.begin(), filenames.end(), NaturalSortOrder());
for (vector<string>::const_iterator iter = filenames.begin();
iter != filenames.end(); ++iter) {
cout << *iter << "\n";
}
system("pause");
return 0;
}
Результат:
Соответственно, если нам надо наоборот сделать сортировку по убыванию, то достаточно поменять оператор «<» в строке 135 на «>»
return number_lhs > number_rhs;
и тогда мы получим:
