Ordered Bag

An OrderedBag is a DataStructure which combines, in many ways, the properties of both sets and lists. It operates as follows:

• An OrderedBag contains any non-negative number of <key, value> pairs. The keys should be immutable, we don't care about the values. "Null" keys are of course permissible.

• Unlike a set (and like a bag, or MultiSet), any number of elements in the OrderedBag may have the same key.

• No ordering is imposed upon elements with different keys.

• A TotalOrder is imposed upon elements with the same key. This differs from the traditional definition of a MultiSet, in which no order is imposed upon elements with the same key.

All sets are also valid OrderedBags. All lists are also ordered bags, assuming the same key (or a null key) is assigned to each element of the list.

This seems like a combination of map and bag and list. It is confusing.

• In what way is a set an OrderedBag? You seem to be defining technical terms in ways that are different from and incompatible with technical usage in other fields. This is only to be done with caution.

• What is the difference between this definition and a bag of lists?

• Why are you dumping all these technical definitions here? What value do they add to discussions about patterns, people and software?

---

My personal opinion - to me an "ordered bag" is simply a essentially a list, and it is confusing to describe it as otherwise. A set is a collection where every element must be distinct. A bag is a collection which permits indistinct elements, i.e. an identical element E may occur with say 3 occurrences. Both of these are unordered (unless specified otherwise). Now an ordered bag has (1) non-uniqueness of elements (2) an ordering of elements? How is this different from a list? Thus I say that a list and an ordered bag are the same thing. The definition given above, does not make much sense to me. -- ZacharyMartin

---

What practical use is there in having an order for identical keys but not different keys? If we have a surrogate key for identical keys, we might as well use the same mechanism for all keys rather than create condition-based look-up logic. If there is any detectable order to the keys, which is usually the case, then it's essentially a list anyhow because unique keys are have an inherit order (themselves collated) and the "ordered" duplicate keys also create a detectable order by definition.

---

See

• HowDataIsOrganized

---

It seems that this was an offshoot from something called BagDiscussion in 2005, so whoever invented this page is probably not around here now to read this. That does not invalidate any present comments, but means there may not be a response. -- JohnFletcher

---

CategoryDataStructure