Goal: No incidental data structures
Classic: A data structure is a format for organizing and storing data.
A structure on a set consists of additional entities that, in some manner, relate to the set, endowing the collection with meaning or significance.
A type is a pattern for storing and modifying objects
A type is a structure that relates a set of objects to a set of values
A representational relationship creates a trivial data structure consisting of a single value
Values are related to other values, i.e. $3 \neq 4$
A data structure is a structure utilizing value, representational, and physical relationships to encode semantic relationships on a collection of objects
{3, 4, 5}
3
is before 4
and 3
is less-than 4
struct list { int _data, list* _next };
the value of _next
encodes an ordered relationshiphash(a) == hash(b)
$\implies$ a == b
[ Everything from here down is notes... ]
namespace bcc {
template <class T, class O>
void iota(T f, T l, O out) {
while (f != l) {
out(f);
++f;
}
}
} // namespace bcc
%%timeit
{
std::list<int> _list;
bcc::iota(0, 1'000'000, [&](int n){ _list.push_back(n); });
}
%%timeit
{
std::vector<int> _vector;
bcc::iota(0, 1'000'000, [&](int n){ _vector.push_back(n); });
}
std::list<int> _list;
bcc::iota(0, 1'000'000, [&](int n){ _list.push_back(n); });
%timeit std::find(begin(_list), end(_list), 500'000);
%timeit std::find(begin(_vector), end(_vector), 500'000);
%timeit _list.insert(std::find(begin(_list), end(_list), 500'000), 42);
%timeit _vector.insert(std::find(begin(_vector), end(_vector), 500'000), 42);
%timeit -n 1000 _list.push_front(42);
%timeit -n 1000 _vector.insert(begin(_vector), 42);
push_front()
, std::deque<>
is a better choicestd::list<>
only makes since when you are externally indexing and hence require iterator stability