Questions tagged [data-structures]

For questions about the implementation or design of data structures as specifically relevant to programming language design or implementation. Generic data structure questions are off-topic.

Filter by
Sorted by
Tagged with
9 votes
0 answers
197 views

How can a compiler optimise persistent data structures to use mutable data structures "under the hood"?

Consider for a motivating example a copy-on-write array, which implements a persistent (i.e. immutable) array data type. As an optimisation at runtime, a reference counter can be used to avoid the ...
kaya3's user avatar
  • 17.3k
15 votes
3 answers
765 views

Towards a better default listlike datastructure for functional languages

In most functional languages I know of, linked lists are the default datastructure of choice for many operations. The benefits are clear - they're clearly encoded with ADTs, and can be utilised easily ...
blueberry's user avatar
  • 2,315
8 votes
7 answers
930 views

Distinguishing classes from structures

Some languages have a concept of classes separately than structs. In C++ the only difference is whether the members are public or private by default. This seems redundant. Why have a separate ...
user16217248's user avatar
  • 7,535
6 votes
2 answers
909 views

What are the downsides of having no syntactic sugar for data collections?

For example, Python has lists, sets and dictionaries as language-level primitives that can be constructed using syntactic sugar [1,2,3], {'a': 1, 'b': 2} while Java ...
kouta-kun's user avatar
  • 1,349
-2 votes
1 answer
177 views

Why are type theorhetic data structures rarer (than sets) if they are fundamental? [closed]

Set theorhetical structures and operations are quite fundamental and typically are either part of a languages standard library or built into it. Given that types are fundamental to programming why do ...
Bruce Adams's user avatar
  • 2,793
8 votes
9 answers
620 views

Would a structure ever require padding beyond what is required to align the members?

In C a structure can have an arbitrary amount of padding. In theory this implementation conforms to the C standard: ...
user16217248's user avatar
  • 7,535
5 votes
7 answers
359 views

What are the implications of a 'packed' keyword/feature?

I am bothered by the fact that, in C, struct types can be arbitrarily large. We have no control over their memory layout except for the fact that the first member ...
user16217248's user avatar
  • 7,535
1 vote
2 answers
163 views

What are the pros and cons of having a unique type for generators?

For languages that allow generators (iterables where elements are determined by a function), what are the pros and cons of having a unique type for generators? For example, languages like python have ...
lyxal's user avatar
  • 1,775
7 votes
1 answer
91 views

Should functions like filter and map be members of a class or top-level functions?

In python, the filter and map functions (among others) are top-level (i.e. global) functions which take an iterable as an ...
Ginger's user avatar
  • 2,579
24 votes
5 answers
682 views

Can "no cyclic data structures" be enforced at compile time?

When using reference counting for garbage collection, memory leaks can occur when cyclic structures are created (an object which contains a pointer to itself, or a pointer to an object with a pointer ...
Rydwolf Programs's user avatar