Re: Implementing a two-way Turing Machine tape as an improvement to std::deque

From	Mr Flibble <flibble@reddwarf.jmc>
Newsgroups	comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Subject	Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
Message-ID	<20220513004049.00000d64@reddwarf.jmc> (permalink)
References	<cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com> <20220512235610.00004914@reddwarf.jmc> <Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com> <20220513002218.00003fa0@reddwarf.jmc> <-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
Organization	Jupiter Mining Corp
Date	2022-05-13 00:40 +0100

Cross-posted to 4 groups.

Show all headers | View raw

On Thu, 12 May 2022 18:38:49 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/12/2022 6:22 PM, Mr Flibble wrote:
> > On Thu, 12 May 2022 18:09:39 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >   
> >> On 5/12/2022 5:56 PM, Mr Flibble wrote:  
> >>> On Thu, 12 May 2022 17:51:25 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>      
> >>>> C/C++ people please critique this as the basis for an improvement
> >>>> to std::deque. It seems to have the key functionality of
> >>>> std::deque and does it much more simply while saving time and
> >>>> space. https://www.cplusplus.com/reference/deque/deque/
> >>>>
> >>>> #define tape_element unsigned char
> >>>>
> >>>> class Tape_Type
> >>>> {
> >>>> private:
> >>>>      int Tape_Head = 0;               // Can be negative
> >>>>      std::vector<tape_element> Left;  // Stores left expansion
> >>>>      std::vector<tape_element> Right; // Stores right expansion
> >>>>      tape_element & operator[](int index);
> >>>>
> >>>> public:
> >>>>      void move_left();      // Tape_Head--; Left.push_back(0); as
> >>>> needed void move_right();     // Tape_Head++; Left.push_back(0);
> >>>> as needed void Write(tape_element Y){ this->operator[](Tape_Head)
> >>>> = Y; }; tape_element Read()       { return
> >>>> this->operator[](Tape_Head); }; Tape_Type(){
> >>>> Right.push_back('_'); } // constructor void Output();
> >>>> };
> >>>>
> >>>> tape_element& Tape_Type::operator[](int index)
> >>>> {
> >>>>      if (index > 0)
> >>>>        return Right[index];
> >>>>      int Left_Index = ((index * -1) -1);
> >>>>      return Left[Left_Index];
> >>>> }
> >>>>
> >>>> void Tape_Type::Output()
> >>>> {
> >>>>      printf("Tape_Type::Output()\n");
> >>>>
> >>>>      if (Left.size())
> >>>>      {
> >>>>        int Last_One = Left.size() - 1;
> >>>>        for (int N = Last_One; N >= 0; N--)
> >>>>        {
> >>>>          int TH = (N + 1) * -1; // determine Tape_Head from N
> >>>>          printf("[%04d]:%c   Left[%02d]\n", TH, Left[N], N);
> >>>>        }
> >>>>      }
> >>>>      if (Right.size())
> >>>>        for (int N = 0; N < Right.size(); N++)
> >>>>          printf("[%04d]:%c  Right[%02d]\n", N, Right[N], N);
> >>>> }
> >>>>
> >>>> void Tape_Type::move_left()
> >>>> {
> >>>>      Tape_Head--;
> >>>>      int Left_Index = ((Tape_Head * -1) -1);
> >>>>      if (Left_Index == Left.size())
> >>>>        Left.push_back('_');
> >>>> }
> >>>>
> >>>> void Tape_Type::move_right()
> >>>> {
> >>>>      Tape_Head++;
> >>>>      if (Tape_Head == Right.size())
> >>>>        Right.push_back('_');
> >>>> }  
> >>>
> >>> It might be a more appropriate solution than std::deque for your
> >>> specific use-case however it is NOT an improvement to std::deque
> >>> for the general case -- see my reply in the other thread for why.
> >>>
> >>> /Flibble
> >>>      
> >>
> >> I didn't see any reason why it would not make a better std::deque.
> >>  
> >   
> > Because it doesn't meet the complexity and referential integrity
> > requirements of std::deque.
> > 
> > /Flibble
> >   
> 
> It is faster then std::deque.
> I couldn't find what you mean by referential integrity it has too
> many different meanings. invalidating iterators seemed to be what you
> mean otherwise I have no idea.
 
I see you are choosing to ignore my reply in the other thread. OK, I
will repost why you are wrong here:

 * referential integrity and iterator invalidation are different
   things: when you add or remove elements to either end of a
   std::deque iterators are indeed invalidated however references to
   existing elements remain valid
 * If you do 1000 push_fronts followed by 1000 push_backs followed by
   1000 pop_fronts all is good however your next pop_front will have
   linear complexity, O(n), as it will necessitate removal of the first
   element of the right std::vector.

/Flibble

Thread

Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 17:51 -0500
  Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-12 23:56 +0100
    Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 18:09 -0500
      Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 00:22 +0100
        Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 18:38 -0500
          Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 00:40 +0100
            Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 18:49 -0500
              Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 00:53 +0100
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 19:12 -0500
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 01:58 +0100
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 20:34 -0500
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 08:02 +0100
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque tth <tth@none.invalid> - 2022-05-13 09:10 +0200
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 10:58 -0500
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 17:02 +0100
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-05-13 12:44 -0700
  Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Richard Damon <Richard@Damon-Family.org> - 2022-05-12 19:23 -0400
    Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 18:32 -0500
  Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 01:06 +0100
    Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 19:55 -0500
      Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 02:01 +0100
        Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 20:36 -0500
          Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 08:04 +0100
            Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 11:00 -0500
              Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 17:04 +0100
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 12:05 -0500
      Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 02:38 +0100
        Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 21:37 -0500
          Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Python <python@example.invalid> - 2022-05-13 04:39 +0200
          Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 12:01 +0100
            Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 10:41 -0500
              Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Richard Damon <Richard@Damon-Family.org> - 2022-05-13 11:56 -0400
              Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 17:35 +0100
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 12:12 -0500
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 20:04 +0100
                Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 14:19 -0500

csiph-web