std-union


Synopsis

(std-union <lst1> <lst2>) ; unstable union of multisets

(std-ordered-union <lst1> <lst2>) ; stable union

Description

STD-UNION returns the union of the two unordered multisets lst1 and lst2. A set is a list without defined order of elements, a multiset is a set with duplicate elements allowed.

The returned list has no defined order, it might even destroy the order of both lists.

Simplified unstable version, but faster than std-ordered-union.

STD-ORDERED-UNION - the stable version - keeps the order of both lists but it is lightly slower than STD-UNION. Use this to keep the order of both lists intact, to add all elements of the second list to the first, which are not already in the first list. #- SMALL

Problem with Duplicates

Duplicates in the second argument are ignored, in the first argument not.

(std-union '(1 2 2 3) '(1 2 3 3)) =>	(1 2 2 3)

So std-union is in fact a boolean union for a multiset and a set.

Note

Big lists as first argument are much faster than as second argument:

(setq big (std-int-list 1000) small (std-int-list 10))
(std-time '(std-union small big))
  (STD-UNION SMALL BIG) 	: 1222 ms

(std-time '(std-union big small))
  (STD-UNION BIG SMALL) 	: 0 ms

Example

(std-union '(0 1 2) '(2 3 4)) => unorderd set of (0 1 2 3 4)
actually (4 3 0 1 2)

(std-ordered-union '(0 1 2) '(2 3 4)) =>	(0 1 2 3 4)
(std-sort (std-union '(0 1 2) '(2 3 4)) '<) => 	(0 1 2 3 4)
(std-ordered-union '(1 2 3 4) '(1 2 3 3)) =>	(1 2 3 4)
(std-ordered-union '(1 2 2 3) '(1 2 3 3)) =>	(1 2 2 3)

Arguments

lst1, lst2: proper lists.

Return Value

The union set. A list without defined order of elements which contains all elements of both lists.

Side Effects

None.

Module

(std-require 'STDLIST)

Defined in STDLIST