On Mon, Jun 15, 2009 at 16:02, Kristof Zelechovski <[email protected]>wrote:
> Uniqueness of tokens can be determined in O(n) only* if the tokens are > ordered in the source (any order would do) but there is no such requirement, > and it cannot be required for compatibility with the content in the wild and > because the standard supports inserting new tokens. > That is is not true. Just use a set/map to keep track of previously seen elements. It is a trivial thing to do. > It is possible to ignore this issue and proceed as if the tokens were > ordered. The result would be that remove would fail, or it would run in > quadratic time. > > HTH, > > Chris > > > > * If all possible tokens are predefined and their number is finite and the > source is valid, uniqueness can be determined in constant time. This > scenario, however, is better served by a bit field than by a token list. > > > -- erik
