Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #3053

Re: data structure that preserving insertion order

Followups directed to: comp.lang.c

Show all headers | View raw

Owner wrote:

> On Fri, 29 Apr 2011 18:15:46 +0100, Ben Bacarisse wrote:
> 
>> Owner <Owner@Owner-PC.com> writes:
>> 
>>> On Fri, 29 Apr 2011 16:23:15 +0100, Ben Bacarisse wrote:
>>>
>>>> Owner <Owner@Owner-PC.com> writes:
>>>> <snip>
>>>>> Yes exactly, preserving order like that but with large data
>>>>> like unicode mapping.  data structure preserving the inorder
>>>>> of character( character has its own value according
>>>>> character set but when inserted the character in some
>>>>> sort of data structure, it preserves inorder ) with able
>>>>> to search the character efficiently.
>>>> 
>>>> I'm still not sure what you want.  In particular what is "Unicode
>>>> mapping"?  Presumably it maps Unicode code points to ... what?
>>>> 
>>>> Anyway, any data structure that supports the mapping you want can be
>>>> made to record the insertion order, simply by maintaining a list at the
>>>> same time.  This so simple that I image it is not what you want but I
>>>> can't tell.  Why not say what the actual problem is that needs to be
>>>> solved?
>>>
>>> Trying to build tr unix tool that supports unicode.
>>> ascii is 128 characters so a array can hold characters.
>>> unicode is a little over 10,000 characters.
>>> thought a binary tree could be right structure.  but then
>>> I need preserve order which character goes in first.
>> 
>> Why?  I'd use something like a hash table.  I don't see any need to
>> remember the insertion order.  What's your reasoning?
> 
> If you command something like "tr hashtable empttable"
> 
> replacing same length word hashtable with empttable.
> 
> I thought inorder needs to be preserved to replace the word,
> 
> no?

But would 

  tr abcd efgh

not just transliterate as follows:

  a --> e
  b --> f
  c --> g
  d --> h

_every_ a becomes an e, _every_ b becomes an f, ... . I.e., 

  asdbdea  --> eshfhee

For that, you don't need to know the order:  

  tr abcd efgh

behaves exactly like

  tr badc fehg

At least, that is how tr behaves on my Unix box. Moreover, that is what the 
info page tells me.


Best,

Kai-Uwe Bux

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

data structure that preserving insertion order Owner <Owner@Owner-PC.com> - 2011-04-28 22:10 -0400
  Re: data structure that preserving insertion order Peter Nilsson <airia@acay.com.au> - 2011-04-28 23:02 -0700
    Re: data structure that preserving insertion order Owner <Owner@Owner-PC.com> - 2011-04-29 08:06 -0400
  Re: data structure that preserving insertion order Paul N <gw7rib@aol.com> - 2011-04-29 05:18 -0700
    Re: data structure that preserving insertion order Owner <Owner@Owner-PC.com> - 2011-04-29 08:42 -0400
      Re: data structure that preserving insertion order Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-29 16:23 +0100
        Re: data structure that preserving insertion order Owner <Owner@Owner-PC.com> - 2011-04-29 12:16 -0400
          Re: data structure that preserving insertion order Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-29 18:15 +0100
            Re: data structure that preserving insertion order Owner <Owner@Owner-PC.com> - 2011-04-29 13:35 -0400
              Re: data structure that preserving insertion order Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-04-29 20:00 +0200
                Re: data structure that preserving insertion order Owner <Owner@Owner-PC.com> - 2011-04-29 14:15 -0400
              Re: data structure that preserving insertion order James Kuyper <jameskuyper@verizon.net> - 2011-04-29 19:17 -0400
          Re: data structure that preserving insertion order "Scott Fluhrer" <sfluhrer@ix.netcom.com> - 2011-04-29 13:08 -0400
          Re: data structure that preserving insertion order William Ahern <william@wilbur.25thandClement.com> - 2011-04-29 10:53 -0700
            Re: data structure that preserving insertion order Owner <Owner@Owner-PC.com> - 2011-04-29 14:17 -0400
              Re: data structure that preserving insertion order James Kuyper <jameskuyper@verizon.net> - 2011-04-29 19:24 -0400
              Re: data structure that preserving insertion order Gene <gene.ressler@gmail.com> - 2011-04-29 16:25 -0700

csiph-web