Groups > comp.lang.c++ > #84045 > unrolled thread

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

Started by	olcott <NoOne@NoWhere.com>
First post	2022-05-12 17:51 -0500
Last post	2022-05-13 12:05 -0500
Articles	20 on this page of 30 — 8 participants

Back to article view | Back to comp.lang.c++

  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 Öö Tiib <ootiib@hot.ee> - 2022-05-12 21:05 -0700
                        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:47 -0500
                              Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 17:22 +0100
                              Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Paavo Helde <eesnimi@osa.pri.ee> - 2022-05-13 19:31 +0300
                          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

Page 1 of 2 [1] 2 Next page →

#84045 — Implementing a two-way Turing Machine tape as an improvement to std::deque

From	olcott <NoOne@NoWhere.com>
Date	2022-05-12 17:51 -0500
Subject	Implementing a two-way Turing Machine tape as an improvement to std::deque
Message-ID	<cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>

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('_');
}



-- 
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
  Genius hits a target no one else can see."
  Arthur Schopenhauer

[toc] | [next] | [standalone]

#84046

From	Mr Flibble <flibble@reddwarf.jmc>
Date	2022-05-12 23:56 +0100
Message-ID	<20220512235610.00004914@reddwarf.jmc>
In reply to	#84045

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

[toc] | [prev] | [next] | [standalone]

#84047

From	olcott <NoOne@NoWhere.com>
Date	2022-05-12 18:09 -0500
Message-ID	<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
In reply to	#84046

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.

-- 
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
  Genius hits a target no one else can see."
  Arthur Schopenhauer

[toc] | [prev] | [next] | [standalone]

#84048

From	Mr Flibble <flibble@reddwarf.jmc>
Date	2022-05-13 00:22 +0100
Message-ID	<20220513002218.00003fa0@reddwarf.jmc>
In reply to	#84047

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

[toc] | [prev] | [next] | [standalone]

#84051

From	olcott <NoOne@NoWhere.com>
Date	2022-05-12 18:38 -0500
Message-ID	<-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
In reply to	#84048

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.

-- 
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
  Genius hits a target no one else can see."
  Arthur Schopenhauer

[toc] | [prev] | [next] | [standalone]

#84052

From	Mr Flibble <flibble@reddwarf.jmc>
Date	2022-05-13 00:40 +0100
Message-ID	<20220513004049.00000d64@reddwarf.jmc>
In reply to	#84051

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

[toc] | [prev] | [next] | [standalone]

#84053

From	olcott <NoOne@NoWhere.com>
Date	2022-05-12 18:49 -0500
Message-ID	<HYudneQqVdKFAOD_nZ2dnUU7_83NnZ2d@giganews.com>
In reply to	#84052

On 5/12/2022 6:40 PM, Mr Flibble wrote:
> 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

Mine words the same way and has the added benefit of contiguous storage.

>   * 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.

I don't think that this applies to the way that I implemented it.
pop_front pops from the end of Left. pop_back pops from the end of 
Right. This is the key aspect that I used from David's two-stack approach.

-- 
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
  Genius hits a target no one else can see."
  Arthur Schopenhauer

[toc] | [prev] | [next] | [standalone]

#84054

From	Mr Flibble <flibble@reddwarf.jmc>
Date	2022-05-13 00:53 +0100
Message-ID	<20220513005340.00001694@reddwarf.jmc>
In reply to	#84053

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

> On 5/12/2022 6:40 PM, Mr Flibble wrote:
> > 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
> 
> Mine words the same way and has the added benefit of contiguous
> storage.
> 
> >   * 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.
> 
> I don't think that this applies to the way that I implemented it.
> pop_front pops from the end of Left. pop_back pops from the end of 
> Right. This is the key aspect that I used from David's two-stack
> approach.
 
Then it is totally different to what std::deque offers: std::deque
allows ALL elements to be either popped from the front or back.  Try
reading AND UNDERSTANDING what I wrote again.

/Flibble

[toc] | [prev] | [next] | [standalone]

#84056

From	olcott <NoOne@NoWhere.com>
Date	2022-05-12 19:12 -0500
Message-ID	<Bo-dnemL1eT6P-D_nZ2dnUU7_81g4p2d@giganews.com>
In reply to	#84054

On 5/12/2022 6:53 PM, Mr Flibble wrote:
> On Thu, 12 May 2022 18:49:43 -0500
> olcott <NoOne@NoWhere.com> wrote:
> 
>> On 5/12/2022 6:40 PM, Mr Flibble wrote:
>>> 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
>>
>> Mine words the same way and has the added benefit of contiguous
>> storage.
>>
>>>    * 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.
>>
>> I don't think that this applies to the way that I implemented it.
>> pop_front pops from the end of Left. pop_back pops from the end of
>> Right. This is the key aspect that I used from David's two-stack
>> approach.
>   
> Then it is totally different to what std::deque offers: std::deque
> allows ALL elements to be either popped from the front or back.  Try
> reading AND UNDERSTANDING what I wrote again.
> 
> /Flibble
> 

I could allow all elements to be popped from the front or the back too.
Mine is much faster when you need far less than all elements.

-- 
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
  Genius hits a target no one else can see."
  Arthur Schopenhauer

[toc] | [prev] | [next] | [standalone]

#84058

From	Mr Flibble <flibble@reddwarf.jmc>
Date	2022-05-13 01:58 +0100
Message-ID	<20220513015816.00006f57@reddwarf.jmc>
In reply to	#84056

On Thu, 12 May 2022 19:12:22 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/12/2022 6:53 PM, Mr Flibble wrote:
> > On Thu, 12 May 2022 18:49:43 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >   
> >> On 5/12/2022 6:40 PM, Mr Flibble wrote:  
> >>> 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  
> >>
> >> Mine words the same way and has the added benefit of contiguous
> >> storage.
> >>  
> >>>    * 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.  
> >>
> >> I don't think that this applies to the way that I implemented it.
> >> pop_front pops from the end of Left. pop_back pops from the end of
> >> Right. This is the key aspect that I used from David's two-stack
> >> approach.  
> >   
> > Then it is totally different to what std::deque offers: std::deque
> > allows ALL elements to be either popped from the front or back.  Try
> > reading AND UNDERSTANDING what I wrote again.
> > 
> > /Flibble
> >   
> 
> I could allow all elements to be popped from the front or the back
> too. Mine is much faster when you need far less than all elements.
 
What you have does not offer what std::deque offers so is not
equivalent to std::deque so can't be considered better than std::deque
for the general case (I don't care about your specific use-case).

/Flibble

[toc] | [prev] | [next] | [standalone]

#84060

From	olcott <NoOne@NoWhere.com>
Date	2022-05-12 20:34 -0500
Message-ID	<D7WdnSjo4swvKOD_nZ2dnUU7_81g4p2d@giganews.com>
In reply to	#84058

On 5/12/2022 7:58 PM, Mr Flibble wrote:
> On Thu, 12 May 2022 19:12:22 -0500
> olcott <NoOne@NoWhere.com> wrote:
> 
>> On 5/12/2022 6:53 PM, Mr Flibble wrote:
>>> On Thu, 12 May 2022 18:49:43 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>    
>>>> On 5/12/2022 6:40 PM, Mr Flibble wrote:
>>>>> 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
>>>>
>>>> Mine words the same way and has the added benefit of contiguous
>>>> storage.
>>>>   
>>>>>     * 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.
>>>>
>>>> I don't think that this applies to the way that I implemented it.
>>>> pop_front pops from the end of Left. pop_back pops from the end of
>>>> Right. This is the key aspect that I used from David's two-stack
>>>> approach.
>>>    
>>> Then it is totally different to what std::deque offers: std::deque
>>> allows ALL elements to be either popped from the front or back.  Try
>>> reading AND UNDERSTANDING what I wrote again.
>>>
>>> /Flibble
>>>    
>>
>> I could allow all elements to be popped from the front or the back
>> too. Mine is much faster when you need far less than all elements.
>   
> What you have does not offer what std::deque offers so is not

All these things can be added and we end up with a simple, faster, 
std:deque that has most the conventional overhead and complexity abolished.

> equivalent to std::deque so can't be considered better than std::deque
> for the general case (I don't care about your specific use-case).
> 
> /Flibble
> 

It just a matter of defining more member functions.

-- 
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
  Genius hits a target no one else can see."
  Arthur Schopenhauer

[toc] | [prev] | [next] | [standalone]

#84064

From	Öö Tiib <ootiib@hot.ee>
Date	2022-05-12 21:05 -0700
Message-ID	<fca2cab7-ceba-4246-8df1-82bb8ec11e2fn@googlegroups.com>
In reply to	#84060

On Friday, 13 May 2022 at 04:35:02 UTC+3, olcott wrote:
> On 5/12/2022 7:58 PM, Mr Flibble wrote: 
> > On Thu, 12 May 2022 19:12:22 -0500 
> > olcott <No...@NoWhere.com> wrote: 
> > 
> >> On 5/12/2022 6:53 PM, Mr Flibble wrote: 
> >>> On Thu, 12 May 2022 18:49:43 -0500 
> >>> olcott <No...@NoWhere.com> wrote: 
> >>> 
> >>>> On 5/12/2022 6:40 PM, Mr Flibble wrote: 
> >>>>> On Thu, 12 May 2022 18:38:49 -0500 
> >>>>> olcott <No...@NoWhere.com> wrote: 
> >>>>> 
> >>>>>> On 5/12/2022 6:22 PM, Mr Flibble wrote: 
> >>>>>>> On Thu, 12 May 2022 18:09:39 -0500 
> >>>>>>> olcott <No...@NoWhere.com> wrote: 
> >>>>>>> 
> >>>>>>>> On 5/12/2022 5:56 PM, Mr Flibble wrote: 
> >>>>>>>>> On Thu, 12 May 2022 17:51:25 -0500 
> >>>>>>>>> olcott <No...@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 
> >>>> 
> >>>> Mine words the same way and has the added benefit of contiguous 
> >>>> storage. 
> >>>> 
> >>>>> * 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. 
> >>>> 
> >>>> I don't think that this applies to the way that I implemented it. 
> >>>> pop_front pops from the end of Left. pop_back pops from the end of 
> >>>> Right. This is the key aspect that I used from David's two-stack 
> >>>> approach. 
> >>> 
> >>> Then it is totally different to what std::deque offers: std::deque 
> >>> allows ALL elements to be either popped from the front or back. Try 
> >>> reading AND UNDERSTANDING what I wrote again. 
> >>> 
> >>> /Flibble 
> >>> 
> >> 
> >> I could allow all elements to be popped from the front or the back 
> >> too. Mine is much faster when you need far less than all elements. 
> > 
> > What you have does not offer what std::deque offers so is not
> 
> All these things can be added and we end up with a simple, faster, 
> std:deque that has most the conventional overhead and complexity abolished.

That is opinion. Opinions are not useful as better std::deque.

> > equivalent to std::deque so can't be considered better than std::deque 
> > for the general case (I don't care about your specific use-case). 
> > 
> > /Flibble 
> >
> It just a matter of defining more member functions.

Writing better std::deque (than particular implementation) is matter
of actually defining those member functions. It can't be done by
arguing in Usenet that defining member functions is possible as
everybody know it is.

[toc] | [prev] | [next] | [standalone]

#84066

From	Mr Flibble <flibble@reddwarf.jmc>
Date	2022-05-13 08:02 +0100
Message-ID	<20220513080247.000077d7@reddwarf.jmc>
In reply to	#84060

On Thu, 12 May 2022 20:34:41 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/12/2022 7:58 PM, Mr Flibble wrote:
> > On Thu, 12 May 2022 19:12:22 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >   
> >> On 5/12/2022 6:53 PM, Mr Flibble wrote:  
> >>> On Thu, 12 May 2022 18:49:43 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>      
> >>>> On 5/12/2022 6:40 PM, Mr Flibble wrote:  
> >>>>> 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  
> >>>>
> >>>> Mine words the same way and has the added benefit of contiguous
> >>>> storage.
> >>>>     
> >>>>>     * 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.  
> >>>>
> >>>> I don't think that this applies to the way that I implemented it.
> >>>> pop_front pops from the end of Left. pop_back pops from the end
> >>>> of Right. This is the key aspect that I used from David's
> >>>> two-stack approach.  
> >>>    
> >>> Then it is totally different to what std::deque offers: std::deque
> >>> allows ALL elements to be either popped from the front or back.
> >>> Try reading AND UNDERSTANDING what I wrote again.
> >>>
> >>> /Flibble
> >>>      
> >>
> >> I could allow all elements to be popped from the front or the back
> >> too. Mine is much faster when you need far less than all elements.
> >>  
> >   
> > What you have does not offer what std::deque offers so is not  
> 
> All these things can be added and we end up with a simple, faster, 
> std:deque that has most the conventional overhead and complexity
> abolished.
> 
> > equivalent to std::deque so can't be considered better than
> > std::deque for the general case (I don't care about your specific
> > use-case).
> > 
> > /Flibble
> >   
> 
> It just a matter of defining more member functions.
 
You cannot implement all of std::deque's member functions meeting
std::deque requirements using your chosen data structure of two
std::vectors.

/Flibble

[toc] | [prev] | [next] | [standalone]

#84068

From	tth <tth@none.invalid>
Date	2022-05-13 09:10 +0200
Message-ID	<t5l090$2f3k$1@news.gegeweb.eu>
In reply to	#84066

On 5/13/22 09:02, Mr Flibble wrote:

> You cannot implement all of std::deque's member functions meeting
> std::deque requirements using your chosen data structure of two
> std::vectors.

    Not with any version of the C language.

-- 
+-------------------------------------------------------------------+
|                      sphinx of black quartz, judge my vow.        |
+-------------------------------------------------------------------+

[toc] | [prev] | [next] | [standalone]

#84078

From	olcott <NoOne@NoWhere.com>
Date	2022-05-13 10:47 -0500
Message-ID	<AKmdnVy_E98P4OP_nZ2dnUU7_8zNnZ2d@giganews.com>
In reply to	#84068

On 5/13/2022 2:10 AM, tth wrote:
> On 5/13/22 09:02, Mr Flibble wrote:
> 
>> You cannot implement all of std::deque's member functions meeting
>> std::deque requirements using your chosen data structure of two
>> std::vectors.
> 
>     Not with any version of the C language.
> 

Many are implemented

class Tape_Type
{
public:
typedef unsigned char tape_element;

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)
   {
     return index >= 0 ? Right[index] : Left[-index - 1];
   }

public:
   tape_element& front( )      { return Left.back();       }
   tape_element& back()        { return Right.back();      }
   void pop_front()                  { Left.pop_back();    }
   void pop_back()                   { Right.pop_back();   }
   void push_front(tape_element& E)  { Left.push_back(E);  }
   void push_back(tape_element& E)   { Right.push_back(E); }
   void reserve(unsigned int N)
                      { Left.reserve(N); Right.reserve(N); }

My deque is indexed by an integer, >=0 grows the RIGHT with 
Right.push_back() as the index increases above 0 and
grows the Left with Left.push_back() as the index decreases below 0.


-- 
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
  Genius hits a target no one else can see."
  Arthur Schopenhauer

[toc] | [prev] | [next] | [standalone]

#84083

From	Ben <ben.usenet@bsb.me.uk>
Date	2022-05-13 17:22 +0100
Message-ID	<87bkw1z9k6.fsf@bsb.me.uk>
In reply to	#84078

olcott <NoOne@NoWhere.com> writes:

> On 5/13/2022 2:10 AM, tth wrote:
>> On 5/13/22 09:02, Mr Flibble wrote:
>> 
>>> You cannot implement all of std::deque's member functions meeting
>>> std::deque requirements using your chosen data structure of two
>>> std::vectors.
>>     Not with any version of the C language.
>
> Many are implemented
>
> class Tape_Type
> {
> public:
> typedef unsigned char tape_element;
>
> 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)
>   {
>     return index >= 0 ? Right[index] : Left[-index - 1];
>   }
>
> public:
>   tape_element& front( )      { return Left.back();       }
>   tape_element& back()        { return Right.back();      }
>   void pop_front()                  { Left.pop_back();    }
>   void pop_back()                   { Right.pop_back();   }
>   void push_front(tape_element& E)  { Left.push_back(E);  }
>   void push_back(tape_element& E)   { Right.push_back(E); }
>   void reserve(unsigned int N)
>                      { Left.reserve(N); Right.reserve(N); }
>
> My deque is indexed by an integer, >=0 grows the RIGHT with
> Right.push_back() as the index increases above 0 and grows the Left
> with Left.push_back() as the index decreases below 0.

This is not a deque.  Test before you post!

-- 
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)

[toc] | [prev] | [next] | [standalone]

#84084

From	Paavo Helde <eesnimi@osa.pri.ee>
Date	2022-05-13 19:31 +0300
Message-ID	<t5m147$m32$1@dont-email.me>
In reply to	#84078

13.05.2022 18:47 olcott kirjutas:
> On 5/13/2022 2:10 AM, tth wrote:
>> On 5/13/22 09:02, Mr Flibble wrote:
>>
>>> You cannot implement all of std::deque's member functions meeting
>>> std::deque requirements using your chosen data structure of two
>>> std::vectors.
>>
>>     Not with any version of the C language.
>>
> 
> Many are implemented
> 
> class Tape_Type
> {
> public:
> typedef unsigned char tape_element;
> 
> 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)
>    {
>      return index >= 0 ? Right[index] : Left[-index - 1];
>    }
> 
> public:
>    tape_element& front( )      { return Left.back();       }
>    tape_element& back()        { return Right.back();      }
>    void pop_front()                  { Left.pop_back();    }
>    void pop_back()                   { Right.pop_back();   }
>    void push_front(tape_element& E)  { Left.push_back(E);  }
>    void push_back(tape_element& E)   { Right.push_back(E); }
>    void reserve(unsigned int N)
>                       { Left.reserve(N); Right.reserve(N); }
> 
> My deque is indexed by an integer, >=0 grows the RIGHT with 
> Right.push_back() as the index increases above 0 and
> grows the Left with Left.push_back() as the index decreases below 0.

My only usage of std::deque is for various FIFO message buffers. This 
means elements are only ever pushed with push_back() and popped with 
pop_front(). Somehow I have a feeling your deque would not be up to the 
task.

[toc] | [prev] | [next] | [standalone]

#84079

From	olcott <NoOne@NoWhere.com>
Date	2022-05-13 10:58 -0500
Message-ID	<zdmdnV7tirvcHeP_nZ2dnUU7_8xQAAAA@giganews.com>
In reply to	#84066

On 5/13/2022 2:02 AM, Mr Flibble wrote:
> On Thu, 12 May 2022 20:34:41 -0500
> olcott <NoOne@NoWhere.com> wrote:
> 
>> On 5/12/2022 7:58 PM, Mr Flibble wrote:
>>> On Thu, 12 May 2022 19:12:22 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>    
>>>> On 5/12/2022 6:53 PM, Mr Flibble wrote:
>>>>> On Thu, 12 May 2022 18:49:43 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>       
>>>>>> On 5/12/2022 6:40 PM, Mr Flibble wrote:
>>>>>>> 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
>>>>>>
>>>>>> Mine words the same way and has the added benefit of contiguous
>>>>>> storage.
>>>>>>      
>>>>>>>      * 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.
>>>>>>
>>>>>> I don't think that this applies to the way that I implemented it.
>>>>>> pop_front pops from the end of Left. pop_back pops from the end
>>>>>> of Right. This is the key aspect that I used from David's
>>>>>> two-stack approach.
>>>>>     
>>>>> Then it is totally different to what std::deque offers: std::deque
>>>>> allows ALL elements to be either popped from the front or back.
>>>>> Try reading AND UNDERSTANDING what I wrote again.
>>>>>
>>>>> /Flibble
>>>>>       
>>>>
>>>> I could allow all elements to be popped from the front or the back
>>>> too. Mine is much faster when you need far less than all elements.
>>>>   
>>>    
>>> What you have does not offer what std::deque offers so is not
>>
>> All these things can be added and we end up with a simple, faster,
>> std:deque that has most the conventional overhead and complexity
>> abolished.
>>
>>> equivalent to std::deque so can't be considered better than
>>> std::deque for the general case (I don't care about your specific
>>> use-case).
>>>
>>> /Flibble
>>>    
>>
>> It just a matter of defining more member functions.
>   
> You cannot implement all of std::deque's member functions meeting
> std::deque requirements using your chosen data structure of two
> std::vectors.
> 
> /Flibble
> 

// Tape_Type implements a two-way Turing machine tape.
// Right contains Tape_Head >= 0 values (right expansion)
// Left  contains Tape_Head  < 0 values (left  expansion)
//
// Grows with Right.push_back() as Tape_Head increases above 0.
// Grows with Left.push_back() as Tape_Head decreases below 0.
//
// Tape_Type has functionality very similar to std::deque
// yet implements this functionality much more simply.
// This saves time and space.
//
class Tape_Type
{
public:
typedef unsigned char tape_element;

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)
   {
     return index >= 0 ? Right[index] : Left[-index - 1];
   }

public:
   tape_element& front( )      { return Left.back();       }
   tape_element& back()        { return Right.back();      }
   void pop_front()                  { Left.pop_back();    }
   void pop_back()                   { Right.pop_back();   }
   void push_front(tape_element& E)  { Left.push_back(E);  }
   void push_back(tape_element& E)   { Right.push_back(E); }
   void reserve(unsigned int N)
                      { Left.reserve(N); Right.reserve(N); }



-- 
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
  Genius hits a target no one else can see."
  Arthur Schopenhauer

[toc] | [prev] | [next] | [standalone]

#84081

From	Mr Flibble <flibble@reddwarf.jmc>
Date	2022-05-13 17:02 +0100
Message-ID	<20220513170239.0000273b@reddwarf.jmc>
In reply to	#84079

On Fri, 13 May 2022 10:58:56 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/13/2022 2:02 AM, Mr Flibble wrote:
> > On Thu, 12 May 2022 20:34:41 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >   
> >> On 5/12/2022 7:58 PM, Mr Flibble wrote:  
> >>> On Thu, 12 May 2022 19:12:22 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>      
> >>>> On 5/12/2022 6:53 PM, Mr Flibble wrote:  
> >>>>> On Thu, 12 May 2022 18:49:43 -0500
> >>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>         
> >>>>>> On 5/12/2022 6:40 PM, Mr Flibble wrote:  
> >>>>>>> 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  
> >>>>>>
> >>>>>> Mine words the same way and has the added benefit of contiguous
> >>>>>> storage.
> >>>>>>        
> >>>>>>>      * 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.  
> >>>>>>
> >>>>>> I don't think that this applies to the way that I implemented
> >>>>>> it. pop_front pops from the end of Left. pop_back pops from
> >>>>>> the end of Right. This is the key aspect that I used from
> >>>>>> David's two-stack approach.  
> >>>>>     
> >>>>> Then it is totally different to what std::deque offers:
> >>>>> std::deque allows ALL elements to be either popped from the
> >>>>> front or back. Try reading AND UNDERSTANDING what I wrote again.
> >>>>>
> >>>>> /Flibble
> >>>>>         
> >>>>
> >>>> I could allow all elements to be popped from the front or the
> >>>> back too. Mine is much faster when you need far less than all
> >>>> elements. 
> >>>    
> >>> What you have does not offer what std::deque offers so is not  
> >>
> >> All these things can be added and we end up with a simple, faster,
> >> std:deque that has most the conventional overhead and complexity
> >> abolished.
> >>  
> >>> equivalent to std::deque so can't be considered better than
> >>> std::deque for the general case (I don't care about your specific
> >>> use-case).
> >>>
> >>> /Flibble
> >>>      
> >>
> >> It just a matter of defining more member functions.  
> >   
> > You cannot implement all of std::deque's member functions meeting
> > std::deque requirements using your chosen data structure of two
> > std::vectors.
> > 
> > /Flibble
> >   
> 
> // Tape_Type implements a two-way Turing machine tape.
> // Right contains Tape_Head >= 0 values (right expansion)
> // Left  contains Tape_Head  < 0 values (left  expansion)
> //
> // Grows with Right.push_back() as Tape_Head increases above 0.
> // Grows with Left.push_back() as Tape_Head decreases below 0.
> //
> // Tape_Type has functionality very similar to std::deque
> // yet implements this functionality much more simply.
> // This saves time and space.
> //
> class Tape_Type
> {
> public:
> typedef unsigned char tape_element;
> 
> 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)
>    {
>      return index >= 0 ? Right[index] : Left[-index - 1];
>    }
> 
> public:
>    tape_element& front( )      { return Left.back();       }
>    tape_element& back()        { return Right.back();      }
>    void pop_front()                  { Left.pop_back();    }
>    void pop_back()                   { Right.pop_back();   }
>    void push_front(tape_element& E)  { Left.push_back(E);  }
>    void push_back(tape_element& E)   { Right.push_back(E); }
>    void reserve(unsigned int N)
>                       { Left.reserve(N); Right.reserve(N); }

And what happens if Left is empty, Right is non-empty and you call
pop_front()?

/Flibble

[toc] | [prev] | [next] | [standalone]

#84087

From	"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date	2022-05-13 12:44 -0700
Message-ID	<t5mce6$ij6$1@dont-email.me>
In reply to	#84081

On 5/13/2022 9:02 AM, Mr Flibble wrote:
> On Fri, 13 May 2022 10:58:56 -0500
> olcott <NoOne@NoWhere.com> wrote:
> 
>> On 5/13/2022 2:02 AM, Mr Flibble wrote:
>>> On Thu, 12 May 2022 20:34:41 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>    
>>>> On 5/12/2022 7:58 PM, Mr Flibble wrote:
>>>>> On Thu, 12 May 2022 19:12:22 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>       
>>>>>> On 5/12/2022 6:53 PM, Mr Flibble wrote:
>>>>>>> On Thu, 12 May 2022 18:49:43 -0500
>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>          
>>>>>>>> On 5/12/2022 6:40 PM, Mr Flibble wrote:
>>>>>>>>> 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
>>>>>>>>
>>>>>>>> Mine words the same way and has the added benefit of contiguous
>>>>>>>> storage.
>>>>>>>>         
>>>>>>>>>       * 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.
>>>>>>>>
>>>>>>>> I don't think that this applies to the way that I implemented
>>>>>>>> it. pop_front pops from the end of Left. pop_back pops from
>>>>>>>> the end of Right. This is the key aspect that I used from
>>>>>>>> David's two-stack approach.
>>>>>>>      
>>>>>>> Then it is totally different to what std::deque offers:
>>>>>>> std::deque allows ALL elements to be either popped from the
>>>>>>> front or back. Try reading AND UNDERSTANDING what I wrote again.
>>>>>>>
>>>>>>> /Flibble
>>>>>>>          
>>>>>>
>>>>>> I could allow all elements to be popped from the front or the
>>>>>> back too. Mine is much faster when you need far less than all
>>>>>> elements.
>>>>>     
>>>>> What you have does not offer what std::deque offers so is not
>>>>
>>>> All these things can be added and we end up with a simple, faster,
>>>> std:deque that has most the conventional overhead and complexity
>>>> abolished.
>>>>   
>>>>> equivalent to std::deque so can't be considered better than
>>>>> std::deque for the general case (I don't care about your specific
>>>>> use-case).
>>>>>
>>>>> /Flibble
>>>>>       
>>>>
>>>> It just a matter of defining more member functions.
>>>    
>>> You cannot implement all of std::deque's member functions meeting
>>> std::deque requirements using your chosen data structure of two
>>> std::vectors.
>>>
>>> /Flibble
>>>    
>>
>> // Tape_Type implements a two-way Turing machine tape.
>> // Right contains Tape_Head >= 0 values (right expansion)
>> // Left  contains Tape_Head  < 0 values (left  expansion)
>> //
>> // Grows with Right.push_back() as Tape_Head increases above 0.
>> // Grows with Left.push_back() as Tape_Head decreases below 0.
>> //
>> // Tape_Type has functionality very similar to std::deque
>> // yet implements this functionality much more simply.
>> // This saves time and space.
>> //
>> class Tape_Type
>> {
>> public:
>> typedef unsigned char tape_element;
>>
>> 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)
>>     {
>>       return index >= 0 ? Right[index] : Left[-index - 1];
>>     }
>>
>> public:
>>     tape_element& front( )      { return Left.back();       }
>>     tape_element& back()        { return Right.back();      }
>>     void pop_front()                  { Left.pop_back();    }
>>     void pop_back()                   { Right.pop_back();   }
>>     void push_front(tape_element& E)  { Left.push_back(E);  }
>>     void push_back(tape_element& E)   { Right.push_back(E); }
>>     void reserve(unsigned int N)
>>                        { Left.reserve(N); Right.reserve(N); }
> 
> And what happens if Left is empty, Right is non-empty and you call
> pop_front()?


Flip a coin; heads left, tails right.

Heads, try to pop from left.
Tails, try to pop from right.

Just joking around here, in a sense... ;^)

Actually, back in the day with my threading work, I have subdivided a 
lock-free stack into regions to amortize things. It was nothing like a 
deque. It was a long time ago, damn near 20 years. The cool part was 
that multiple threads could push/pop items without interfering with one 
another in a lot of use cases that respected locality. It was layered up:

per-thread container
hash bucket container
global container

Iirc, to pop an element from the container:

check per-thread
check hash bucket
check the global

if all checks fail, return nullptr, if not return the popped node.

I think I might still have this code on an old hard drive.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2 [1] 2 Next page →

csiph-web

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

Contents

#84045 — Implementing a two-way Turing Machine tape as an improvement to std::deque

#84046

#84047

#84048

#84051

#84052

#84053

#84054

#84056

#84058

#84060

#84064

#84066

#84068

#84078

#84083

#84084

#84079

#84081

#84087