1
Array := {"title": "Book Title", "author": "John Doe"}

Some people use the following terminology:

  • title and author are keys.

  • Book Title and John Doe are values.

  • "title": "Book Title" and "author": "John Doe" are elements (= key-value pairs).

But some people - this one:

  • Book Title and John Doe are elements (= values). (These words are used as a synonyms.)
  • "title": "Book Title" and "author": "John Doe" are key-element pairs (= key-value pairs).

Which terminology is correct? Does it exist at all?

  • Your example isn't an array. Hence, your confusion. – BobDalgleish Nov 19 '19 at 22:53
3

The term element mean a distinct object that is member of a set. This terminology originates from the mathematical set theory. It is used in computer science algorithms with the same meaning, for any kind of collections.

Arrays, be it classical indexed arrays, or more elaborate associative arrays are a data structure that represents the relation between a key (or index, in the case of indexed arrays) and a value.

The element is not the really value. The value alone is not sufficient: they have no identity, and two same values cannot be distinguished. Example:

string colour[] = { "red", "blue", "red" }     // language with classical arrays
Array := {"title": "Doe", "author": "Doe"}     // language with associative arrays

If the values would really be the elements, how would you understand "swaping two elements", for example the "red" and the "blue" ? What's missing here to say which "red" you want to swap ? The key (or index) !

Now, it is not possible to give an accurate definition without considering mutablility:

  • If the elements are immutable, the combination key-value (or index-value) is a better candidate for being an element than the value alone. 0-red, 1-blue, 2-red are distinct elements.

  • If the elements are mutable, the combination key-value no longer defines correctly the element. In this semantic, if I change colour[1] from "red" to "green", it's still the same element, but with a new value. Here, the element is the unique object associated with the key/index.

  • Hello, Christophe. Thanks a lot. There is "colour1" in the bottom part of the answer, where "1" links to Wikipedia. Not sure is a typo or not. (I mean "1" and its link.) – john c. j. Nov 15 '19 at 20:01
  • @johnc.j. Hello John ! Thanks for pointing this out. It was the markdown formatting engine that interpreted the index between bracket as a reference to a link. I’ve corrected. – Christophe Nov 15 '19 at 20:42
  • I made a simple example to ensure I understand your answer correctly. Is it correct? pastebin.com/raw/D1hYQLAf – john c. j. Nov 27 '19 at 15:17
  • 1
    @johnc.j. yes for the first. For the second almost yes, since we do not have a way to show that we mean the object containing aaaa rather than the value aaaa. – Christophe Nov 27 '19 at 15:43
  • It seems you mean aaa, 3, not 4? – john c. j. Nov 27 '19 at 16:10
4
Array := {"title": "Book Title", "author": "John Doe"}

Most languages don't refer to that structure as an array (the only major exception I know of is PHP). It's more commonly called a dictionary or a map; those structures have keys and values. A proper array is 'just' a list of elements/values (either term is correct); an example would be ["John", "Jane", "Bob"].

You could interpret a dictionary/map as an array of key-value pairs, but that's usually the wrong way to think of it. An array imposes a certain ordering (in my previous example, "John" precedes "Jane" and "Jane" precedes "Bob") and each element has an index (the index of "John" is 0, the index of "Jane" is 1). The ordering of key-value pairs in dictionaries is usually indeterminate.

  • Interesting! What about this definition of arrays and associative arrays ? And is an array really a list ? Lists have iterators, but no indexes. – Christophe Nov 15 '19 at 19:50
  • It's true that dictionaries are not strictly ordered, but most languages offer you to enumerate the entries (in whatever order the runtime decides to give it to you). Similarly, you can use arrays without an expectation of a particular ordering (e.g. when you're only interested in "contains" logic). If you don't care about the order of a given collection, which is not that uncommon, it's not wrong to think of a dictionary as an array. – Flater Nov 16 '19 at 10:52
  • @Christophe: The functional purpose of arrays and lists is similar, even if the specific implementation might not be. Speaking from a .Net perspective, arrays and lists have become trivially interchangeable. The types are still different but any collection can be cast from one to the other with little to no effort (ToList/ToArray), or polymorphically both can be used as a IEnumerable<T>. For .Net developers, the question of using an array or a list has become moot, hence why devs tend not to actively distinguish between them anymore. I suspect other languages may have evolved similarly. – Flater Nov 16 '19 at 10:55
  • @Flater interesting. But this is specific to one single implementation. Speaking from a general algorithmic point of view, an element in a list only knows the next element; sequential access is required. An element in a double linked list knows the previous and the next element; sequential access is still required but at least you do'nt need to restart. An element in an array knows no other elements, but the array gives direct access to any element. This is a very different access. To get a comparable level of performance with a list, you'd need to implement a skip list. structure – Christophe Nov 16 '19 at 11:04
  • @Flater furthermore, in a couple of languages, the array has a maximum size, whereas the list allows an unlimited growth. THe languages where rray can grow dynamically require to move from time to time the content of the array, which may or may not be a performance issue depending on the use case. Behind each of these structures, there are different time and space complexity: this is why I wanted to draw the attention that some care with the wording could be useful ;-) – Christophe Nov 16 '19 at 11:07
0

I’m skipping the “key-value” part because other answers talk about it. It just emphasizes that “array” gets used a lot of different ways.

Classically, an array represents a contiguous block of memory. The name of the array dereferences to the start of the block and “the name” of each element is an offset in the memory block. In other words, historically the array is a low level data structure and a thin abstraction over sequential memory addresses.

In this context, an element of the array can mean passing by reference. An array value suggests passing by value. Changing an array element changes the array. Changing an array value might mean only changing a local value without modifying the array data structure.

Again, this is only one context and what someone actually means depends on what they actually mean. But it helps to know what they might mean before discovering that an array is still holding stale values.

  • Objective-C mutable arrays don’t have elements stored contiguous you, allowing insert/delete the k-th element either from the start or from the end in O(k). – gnasher729 Nov 16 '19 at 17:03
  • @gnasher729 I’m not surprised. – ben rudgers Nov 17 '19 at 2:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.