Skip to content

Commit 494c324

Browse files
cirosantillicirosantilli
committed
cpp: a bunch of random stuff
1 parent 04fed30 commit 494c324

6 files changed

Lines changed: 157 additions & 82 deletions

File tree

‎cpp/algorithm.cpp‎

Lines changed: 73 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -37,28 +37,93 @@ int main() {
3737
* Particularly important because of the copy and swap idiom.
3838
*/
3939

40-
// # randomize
40+
// # random_shuffle
4141
{
4242
std::vector<int> v{2, 0, 1};
4343
std::random_shuffle(v.begin(), v.end());
4444
}
4545

46-
// # copy
46+
#if __cplusplus >= 201703L
47+
/* # sample
48+
*
49+
* https://stackoverflow.com/questions/6942273/how-to-get-a-random-element-from-a-c-container/42484107#42484107
50+
*/
4751
{
48-
std::vector<int> v{2, 0, 1};
49-
std::vector<int> v2(5, 3);
50-
std::copy(v.begin(), v.end(), v2.begin() + 1);
51-
assert(v2 == std::vector<int>({3, 2, 0, 1, 3}));
52+
const std::vector<int> in{1, 2, 3, 5, 7};
53+
std::vector<int> out;
54+
size_t nelems = 3;
55+
std::sample(in.begin(), in.end(), std::back_inserter(out),
56+
nelems, std::mt19937{std::random_device{}()});
57+
std::set in_set(std::begin(in), std::end(in));
58+
std::set out_set(std::begin(out), std::end(out));
59+
60+
// The sample elements are distinct.
61+
assert(out_set.size() == nelems);
62+
63+
// The sample elements came from the input.
64+
std::set<int> intersect;
65+
std::set_intersection(
66+
in.begin(), in.end(), out.begin(), out.end(),
67+
std::inserter(intersect, intersect.begin())
68+
);
69+
assert(intersect.size() == nelems);
70+
71+
//for (auto i : out)
72+
// std::cout << i << std::endl;
5273
}
74+
#endif
5375

5476
/* # equal
5577
*
5678
* Compares ranges of two containers.
79+
*
80+
* Vs memcmp:
81+
* https://stackoverflow.com/questions/39262496/why-is-stdequal-much-slower-than-a-hand-rolled-loop-for-two-small-stdarray
5782
*/
5883
{
59-
std::vector<int> v {0, 1, 2 };
84+
std::vector<int> v1{0, 1, 2 };
6085
std::vector<int> v2{ 1, 2, 3};
61-
assert(std::equal(v.begin() + 1, v.end(), v2.begin()));
86+
assert(std::equal(v1.begin() + 1, v1.end(), v2.begin()));
87+
}
88+
89+
/* # copy
90+
*
91+
* Vs memcpy: can compile down to an assembly optimized memcpy for arrays apparently, so just always use this:
92+
* https://stackoverflow.com/questions/4707012/is-it-better-to-use-stdmemcpy-or-stdcopy-in-terms-to-performance
93+
*/
94+
{
95+
/* Newbie basic class usage. */
96+
{
97+
std::vector<int> v{0, 1, 2, 3, 4};
98+
std::vector<int> v2(v.size(), v.size());
99+
std::copy(v.begin() + 1, v.end() - 1, v2.begin() + 2);
100+
assert(v2 == std::vector<int>({5, 5, 1, 2, 3}));
101+
}
102+
103+
/* # std::begin
104+
*
105+
* # std::end
106+
*
107+
* Array usage.
108+
*
109+
* https://stackoverflow.com/questions/7593086/why-use-non-member-begin-and-end-functions-in-c11
110+
*/
111+
{
112+
int v1[]{0, 1, 2, 3, 4};
113+
int v2[]{5, 5, 5, 5, 5};
114+
int v3[]{5, 5, 1, 2, 3};
115+
std::copy(std::begin(v1) + 1, std::end(v1) - 1, std::begin(v2) + 2);
116+
assert(std::equal(std::begin(v2), std::end(v2), std::begin(v3)));
117+
}
118+
119+
/* Therefore, a more elegant class approach that uses exact same syntax as arrays. */
120+
{
121+
std::vector<int> v1{0, 1, 2, 3, 4};
122+
std::vector<int> v2{5, 5, 5, 5, 5};
123+
std::vector<int> v3{5, 5, 1, 2, 3};
124+
std::copy(std::begin(v1) + 1, std::end(v1) - 1, std::begin(v2) + 2);
125+
assert(std::equal(std::begin(v2), std::end(v2), std::begin(v3)));
126+
}
62127
}
63128

64129
/* # accumulate
@@ -125,7 +190,6 @@ int main() {
125190
* If you want to get the position of those items, use `equal_range`, `lower_bound` or `upper_bound`.
126191
*/
127192
{
128-
129193
std::vector<int> v{0, 1, 2};
130194
assert(std::binary_search(v.begin(), v.end(), 1) == true);
131195
assert(std::binary_search(v.begin(), v.end(), 3) == false);

‎cpp/array.cpp‎

Lines changed: 22 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,31 @@
1-
/* https://stackoverflow.com/questions/4424579/stdvector-versus-stdarray-in-c */
1+
/* # std::array
2+
*
3+
* https://stackoverflow.com/questions/4424579/stdvector-versus-stdarray-in-c
4+
*
5+
* Basically: never use raw arrays in C++, use this instead.
6+
* It is better in every sense.
7+
*/
28

39
#include "common.hpp"
410

511
int main() {
612
std::array<int, 3> a{{0, 1, 2}};
13+
714
assert(a.size() == 3);
15+
816
// No implicit bounds checks.
917
//std::cout << a[4] << std::endl;
18+
19+
// But does have some goodies, since it knows the array size,
20+
// e.g. operator== comparison.
21+
assert((std::array<int, 3>{1, 2, 3} == std::array<int, 3>{1, 2, 3}));
22+
23+
// Nah, can't deduce size from initializer:
24+
// https://stackoverflow.com/questions/6114067/how-to-emulate-c-array-initialization-int-arr-e1-e2-e3-behaviou
25+
// std::array<int>{1, 2, 3}
26+
27+
// But does not have any constructor goodies, e.g. fill constructor:
28+
//std::array<int, 3>(24);
29+
// Maybe this is to make it POD?
30+
static_assert(std::is_pod<std::array<int, 1>>());
1031
}

‎cpp/iterator.cpp‎

Lines changed: 5 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -55,17 +55,15 @@ int main() {
5555
// After C++11; the range based syntax is the best way to use them.
5656
{
5757
/*
58-
# forward iteration
58+
# begin
5959
60-
Can be done on all containers.
60+
Returns an iterator to the first element.
6161
62-
# begin
62+
# end
6363
64-
Returns an iterator to the first element.
64+
Returns an iterator to the first element *after* the last.
6565
66-
# end
67-
68-
Returns an iterator to the first element *after* the last.
66+
https://stackoverflow.com/questions/7593086/why-use-non-member-begin-and-end-functions-in-c11
6967
*/
7068
{
7169
std::vector<int> v{1, 2, 0};

‎cpp/pod.cpp‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@
99
*/
1010

1111
#include <type_traits>
12+
#include <array>
1213
#include <vector>
1314

1415
int main() {
@@ -227,6 +228,9 @@ int main() {
227228
{
228229
static_assert(!std::is_pod<std::vector<int>>());
229230
static_assert(!std::is_trivially_copyable<std::vector<int>>());
231+
// Some might be though:
232+
// https://stackoverflow.com/questions/3674247/is-stdarrayt-s-guaranteed-to-be-pod-if-t-is-pod
233+
static_assert(std::is_pod<std::array<int, 1>>());
230234
}
231235

232236
/* Array of POD is POD. */

‎cpp/unique_ptr.cpp‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -140,7 +140,7 @@ int main() {
140140

141141
// # reset
142142
{
143-
/* With no argumetns, explicit destruction of pointer. Equivalent to `delete`.
143+
/* With no arguments, explicitly destroy the pointer. Equivalent to `delete`.
144144
*
145145
* http://stackoverflow.com/questions/25609457/unique-ptr-explicit-delete
146146
*/
@@ -152,13 +152,15 @@ int main() {
152152
}
153153

154154
// Reset with an argument
155-
// does what you would expect: release and replace.
155+
// does what you would expect: release and replace,
156+
// just like assignment.
156157
{
157158
std::unique_ptr<Base> p(new Base(1));
158159
assert(p->i == 1);
159160
assert(Base::count == 1);
160161

161162
/* Nope. TODO why?
163+
*
162164
* - https://stackoverflow.com/questions/48104034/why-cant-i-assign-to-unique-ptr-of-type-uint-8
163165
* - https://stackoverflow.com/questions/34882140/why-cant-a-pointer-be-automatically-converted-into-a-unique-ptr-when-returning
164166
*/

‎cpp/vector.cpp‎

Lines changed: 49 additions & 63 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,7 @@
1-
/*
2-
# vector
3-
4-
Array backed conatiner that grows / shrinks as necessary.
5-
6-
$O(1)$ random access.
7-
8-
$O(n)$ element removal from interior
9-
10-
$O(1)$ element append to end (amortized, $O(n)$ worst case)
11-
12-
All methods that work for several SLT containers shall only be cheated here once.
13-
*/
1+
/* # vector
2+
*
3+
* Dynamic array: https://en.wikipedia.org/wiki/Dynamic_array
4+
*/
145

156
#include "common.hpp"
167

@@ -31,11 +22,10 @@ int main() {
3122
assert(v.size() == 3);
3223
}
3324

34-
/*
35-
Fill constructor.
36-
37-
Make a `std::vector` with n copies of a single value.
38-
*/
25+
/* Fill constructor.
26+
*
27+
* Make a `std::vector` with n copies of a single value.
28+
*/
3929
{
4030
// Copies of given object.
4131
{
@@ -71,22 +61,21 @@ int main() {
7161
assert(v != v1);
7262
}
7363

74-
/*
75-
# Contigous storage
76-
77-
# Data
78-
79-
Storage is required to be contiguous by TR1:
80-
http://stackoverflow.com/questions/849168/are-stdvector-elements-guaranteed-to-be-contiguous
81-
82-
C++11 introduces the `data()` method which returns a pointer to the first element.
83-
It works even if the vector is empty.
84-
http://stackoverflow.com/questions/6485496/how-to-get-stdvector-pointer-to-the-raw-data
85-
86-
Before C++11, `&v[0]` works for non-empty vectors.
87-
88-
`vector<bool>` as usual is an exception.
89-
*/
64+
/* # Contiguous storage
65+
*
66+
* # Data
67+
*
68+
* Storage is required to be contiguous by TR1:
69+
* http://stackoverflow.com/questions/849168/are-stdvector-elements-guaranteed-to-be-contiguous
70+
*
71+
* C++11 introduces the `data()` method which returns a pointer to the first element.
72+
* It works even if the vector is empty.
73+
* http://stackoverflow.com/questions/6485496/how-to-get-stdvector-pointer-to-the-raw-data
74+
*
75+
* Before C++11, `&v[0]` works for non-empty vectors.
76+
*
77+
* `vector<bool>` as usual is an exception.
78+
*/
9079
{
9180
std::vector<int> v{0, 1, 2};
9281
assert(&v[0] == v.data());
@@ -96,31 +85,29 @@ int main() {
9685

9786
// size methods
9887
{
99-
/*
100-
# size
101-
102-
# length of vector
103-
104-
# size_type
105-
106-
Number of elements in std::vector.
107-
108-
This has type std::vector<X>::size_type
109-
*/
88+
/* # size
89+
*
90+
* # length of vector
91+
*
92+
* # size_type
93+
*
94+
* Number of elements in std::vector.
95+
*
96+
* This has type std::vector<X>::size_type
97+
*/
11098
{
11199
std::vector<int> v;
112100
assert(v.size() == 0);
113101
v.push_back(0);
114102
assert(v.size() == 1);
115103
}
116104

117-
/*
118-
# resize
119-
120-
If larger than current size, append given element at end.
121-
122-
If smaller than current size, remove elements from end.
123-
*/
105+
/* # resize
106+
*
107+
* If larger than current size, append given element at end.
108+
*
109+
* If smaller than current size, remove elements from end.
110+
*/
124111
{
125112
// Reduce size
126113
{
@@ -150,17 +137,16 @@ int main() {
150137

151138
// Capacity methods.
152139
{
153-
/*
154-
# capacity
155-
156-
Get currently allocated size.
157-
158-
Different from size, which is the number of elements in the std::vector!
159-
160-
At least as large as size.
161-
162-
Likely to be a power of 2 on most implementations.
163-
*/
140+
/* # capacity
141+
*
142+
* Get currently allocated size.
143+
*
144+
* Different from size, which is the number of elements in the std::vector!
145+
*
146+
* At least as large as size.
147+
*
148+
* Likely to be a power of 2 on most implementations.
149+
*/
164150
{
165151
std::vector<int> v;
166152
v.push_back(0);

0 commit comments

Comments
 (0)