C++

Forum

 
Compile Errors of Substring Sort Program

AlexCantor (145)
Need help in fixing compile errors using VS2022 please:

Error (active) E0757 variable "size_t" is not a type name
ucrt\corecrt_memory.h 38

Need help in updating this program to use C++20 features please.

Need help in making this program easier to understand please.

These programs are from "Art of Writing Efficient Programs by Fedor Pikus"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
// 01a_substring_sort.C

// 01 with two call sources to compare()
#include <algorithm>
#include <chrono>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <memory>
#include <random>
#include <vector>

using std::chrono::duration_cast;
using std::chrono::milliseconds;
using std::chrono::system_clock;
using std::cout;
using std::endl;
using std::minstd_rand;
using std::unique_ptr;
using std::vector;

bool compare1(const char* s1, const char* s2, unsigned int l);
bool compare2(const char* s1, const char* s2, unsigned int l);

int main() {
#include "00_substring_sort_prep.C"

    size_t count = 0;
    std::sort(vs.begin(), vs.end(), [&](const char* a, const char* b) { ++count; return compare1(a, b, L); });
    system_clock::time_point t2 = system_clock::now();
    cout << "Sort time: " << duration_cast<milliseconds>(t2 - t1).count() << "ms (" << count << " comparisons)" << endl;
    std::sort(vs.begin(), vs.end(), [&](const char* a, const char* b) { ++count; return compare2(a, b, L); });
    system_clock::time_point t3 = system_clock::now();
    cout << "Second sort time: " << duration_cast<milliseconds>(t3 - t2).count() << "ms (" << count << " comparisons)" << endl;
}





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
// 00_substring_sort_prep.C   

   //constexpr unsigned int L = 1 << 24, N = 1 << 20; // Use with options A, B
    constexpr unsigned int L = 1 << 18, N = 1 << 14;  // Use with option C
    //constexpr unsigned int L = 1 << 22, N = 1 << 18;  // Use with option C, takes longer
    //constexpr unsigned int L = 1 << 8, N = 1 << 3;

    //system_clock::time_point t0 = system_clock::now();
    unique_ptr<char[]> s(new char[L]);
    vector<const char*> vs(N);
    {
        minstd_rand rgen;
        using rand_t = minstd_rand::result_type;
        if(0) for (char* p = s.get(), *end = p + L; p != end; p += sizeof(rand_t)) {    // Option A
            const rand_t x = rgen();
            ::memcpy(p, &x, sizeof(x));
        }
        else if(0) for (unsigned int i = 0; i < L; ++i) {       // Option B
            s[i] = 'a' + (rgen() % ('z' - 'a' + 1));
        }
        else {    // Option C
            ::memset(s.get(), 'a', L*sizeof(char));
            for (unsigned int i = 0; i < L/1024; ++i) {
                s[rgen() % (L - 1)] = 'a' + (rgen() % ('z' - 'a' + 1));
            }
        }
        s[L-1] = 0;
        for (unsigned int i = 0; i < N; ++i) {
            vs[i] = &s[rgen() % (L - 1)];
        }
        //cout << "s=" << s.get() << endl;
        //for (unsigned int i = 0; i < N; ++i) cout << "vs[" << i << "]=" << vs[i] << endl;
    }
    system_clock::time_point t1 = system_clock::now();
    //cout << "Prep time(L=" << L << ", N=" << N << "): " << duration_cast<milliseconds>(t1 - t0).count() << "ms" << endl;




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
// 01a_substring_sort_a.C

// Comparison function for substring sort, called from two places
int compare(char c1, char c2);

bool compare1(const char* s1, const char* s2, unsigned int l) {
    if (s1 == s2) return false;
    for (unsigned int i1 = 0, i2 = 0; i1 < l; ++i1, ++i2) {
        int res = compare(s1[i1], s2[i2]);
        if (res != 0) return res > 0;
    }
    return false;
}





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 

// 01a_substring_sort_b.C

// Comparison function for substring sort, called from two places
int compare(char c1, char c2);

bool compare2(const char* s1, const char* s2, unsigned int l) {
    if (s1 == s2) return false;
    for (unsigned int i1 = 0, i2 = 0; i1 < l; ++i1, ++i2) {
        int res = compare(s1[i1], s2[i2]);
        if (res != 0) return res < 0;
    }
    return false;
}



1
2
3
4
5
6
7
8
9
10
11
 
// 01a_substring_sort_c.C


// Comparison function for substring sort
int compare(char c1, char c2) {
    if (c1 > c2) return 1;
    if (c1 < c2) return -1;
    return 0;
}

Last edited on
thmm (703)
What are the errors ?
AlexCantor (145)
Error (active) E0757 variable "using" is not a type name
01a_substring_sort.C 13


Error C2054 expected '(' to follow 'constexpr'
00_substring_sort_prep.C 4

Last edited on
Peter87 (11238)
Error (active) E0757 variable "size_t" is not a type name

Either write std::size_t or use using std::size_t; like you've done with all the other standard library names.
Last edited on
Peter87 (11238)
Error (active) E0757 variable "using" is not a type name

Make sure the compiler is compiling the code as C++ and not C.

I don't know how Visual Studio handles files with a .C extension by default but since Windows normally treats upper case the same as lower case I wouldn't be surprised if it treated .C the same as .c and therefore assumed it should be compiled as C code.
seeplus (6597)
As 1 file, this compiles OK with VS2022:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
#include <algorithm>
#include <chrono>
#include <cstring>
#include <iostream>
#include <memory>
#include <random>
#include <vector>

int compare(char c1, char c2) {
	if (c1 > c2) return 1;
	if (c1 < c2) return -1;
	return 0;
}

bool compare1(const char* s1, const char* s2, unsigned int l) {
	if (s1 == s2) return false;

	for (unsigned int i1 = 0, i2 = 0; i1 < l; ++i1, ++i2) {
		int res = compare(s1[i1], s2[i2]);

		if (res != 0) return res > 0;
	}

	return false;
}

bool compare2(const char* s1, const char* s2, unsigned int l) {
	if (s1 == s2) return false;

	for (unsigned int i1 = 0, i2 = 0; i1 < l; ++i1, ++i2) {
		int res = compare(s1[i1], s2[i2]);

		if (res != 0) return res < 0;
	}

	return false;
}

int main() {
	//constexpr unsigned int L = 1 << 24, N = 1 << 20; // Use with options A, B
	constexpr unsigned int L = 1 << 18, N = 1 << 14;  // Use with option C
	//constexpr unsigned int L = 1 << 22, N = 1 << 18;  // Use with option C, takes longer
	//constexpr unsigned int L = 1 << 8, N = 1 << 3;

	//system_clock::time_point t0 = system_clock::now();
	std::unique_ptr<char[]> s(new char[L]);
	std::vector<const char*> vs(N);

	{
		std::minstd_rand rgen;

		using rand_t = std::minstd_rand::result_type;

		if (0)
			for (char* p = s.get(), *end = p + L; p != end; p += sizeof(rand_t)) {    // Option A
				const rand_t x = rgen();

				::memcpy(p, &x, sizeof(x));
			} else if (0)
				for (unsigned int i = 0; i < L; ++i) {       // Option B
					s[i] = 'a' + (rgen() % ('z' - 'a' + 1));
				} else {    // Option C
					::memset(s.get(), 'a', L * sizeof(char));
					for (unsigned int i = 0; i < L / 1024; ++i) {
						s[rgen() % (L - 1)] = 'a' + (rgen() % ('z' - 'a' + 1));
					}
				}

			s[L - 1] = 0;
			for (unsigned int i = 0; i < N; ++i) {
				vs[i] = &s[rgen() % (L - 1)];
			}

			//cout << "s=" << s.get() << endl;
			//for (unsigned int i = 0; i < N; ++i) cout << "vs[" << i << "]=" << vs[i] << endl;
	}

	std::chrono::system_clock::time_point t1 = std::chrono::system_clock::now();
	//cout << "Prep time(L=" << L << ", N=" << N << "): " << duration_cast<milliseconds>(t1 - t0).count() << "ms" << endl;
	size_t count = 0;

	std::sort(vs.begin(), vs.end(), [&](const char* a, const char* b) { ++count; return compare1(a, b, L); });

	std::chrono::system_clock::time_point t2 = std::chrono::system_clock::now();

	std::cout << "Sort time: " << duration_cast<std::chrono::milliseconds>(t2 - t1).count() << "ms (" << count << " comparisons)" << '\n';

	std::sort(vs.begin(), vs.end(), [&](const char* a, const char* b) { ++count; return compare2(a, b, L); });

	std::chrono::system_clock::time_point t3 = std::chrono::system_clock::now();
	std::cout << "Second sort time: " << std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2).count() << "ms (" << count << " comparisons)" << '\n';
}


what's with the if (0) statements - If these are to choose different options, then use an enum or something.
seeplus (6597)
As a first refactor (keeping char* instead of using std::string), possibly:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
#include <algorithm>
#include <chrono>
#include <iostream>
#include <memory>
#include <random>
#include <vector>
#include <utility>

enum Opts {OPTA, OPTB, OPTC};

int compare(char c1, char c2) {
	if (c1 > c2) return 1;
	if (c1 < c2) return -1;
	return 0;
}

bool compare1(const char* s1, const char* s2, size_t l) {
	if (s1 != s2)
		for (size_t i1 {}; i1 < l; ++i1)
			if (const auto res { compare(s1[i1], s2[i1]) }; res)
				return res > 0;

	return false;
}

bool compare2(const char* s1, const char* s2, size_t l) {
	if (s1 != s2)
		for (size_t i1 {}; i1 < l; ++i1)
			if (const auto res { compare(s1[i1], s2[i1]) }; res)
				return res < 0;

	return false;
}

auto setOpt(Opts opt) {
	switch (opt) {
		case OPTA:
		case OPTB:
			return std::pair<size_t, size_t>{1 << 24, 1 << 29};

		case OPTC:
			return std::pair<size_t, size_t> {1 << 18, 1 << 14};

		default:
			return std::pair<size_t, size_t>{0, 0};
	}
}

auto init(auto opt, auto& s, auto L, auto N) {
	std::minstd_rand rgen;

	switch (opt) {
		case OPTA:
			std::cout << "Option A\n";

			for (char *p { s.get() }, *end { p + L }; p < end; p += sizeof(rgen)) {
				const auto x {rgen() };

				std::copy_n(reinterpret_cast<const char*>(&x), sizeof(rgen), p);
			}

			break;

		case OPTB:
			std::cout << "Option B\n";

			for (size_t i {}; i < L; ++i)
				s[i] = 'a' + (rgen() % ('z' - 'a' + 1));

			break;

		case OPTC:
			std::cout << "Option C\n";

			std::fill_n(s.get(), L * sizeof(char), 'a');

			for (size_t i {}; i < L / 1024; ++i)
				s[rgen() % (L - 1)] = 'a' + (rgen() % ('z' - 'a' + 1));

			break;

		default:
			std::cout << "Unknown option\n";
	}

	std::vector<const char*> vs(N);

	if (L) {
		s[L - 1] = 0;

		for (size_t i {}; i < N; ++i)
			vs[i] = &s[rgen() % (L - 1)];
	}

	return vs;
}

int main() {
	constexpr Opts opt { OPTA };

	const auto [L, N] {setOpt(opt)};
	const auto s { std::make_unique<char[]>(L) };

	const auto t0 { std::chrono::system_clock::now() };

	auto vs { init(opt, s, L, N) };

	const auto t1 { std::chrono::system_clock::now() };

	std::cout << "Prep time(L=" << L << ", N=" << N << "): " << duration_cast<std::chrono::milliseconds>(t1 - t0).count() << "ms" << '\n';

	size_t count {};

	std::sort(vs.begin(), vs.end(), [&](const char* a, const char* b) { ++count; return compare1(a, b, 1); });

	const auto t2 { std::chrono::system_clock::now() };

	std::cout << "Sort time: " << duration_cast<std::chrono::milliseconds>(t2 - t1).count() << "ms (" << count << " comparisons)" << '\n';

	size_t count1 {};

	std::sort(vs.begin(), vs.end(), [&](const char* a, const char* b) { ++count1; return compare2(a, b, 1); });

	const auto t3 { std::chrono::system_clock::now() };

	std::cout << "Second sort time: " << std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2).count() << "ms (" << count1 << " comparisons)" << '\n';
}

Last edited on
Topic archived. No new replies allowed.