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

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

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

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

On 5/12/22 6:51 PM, olcott 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('_');
> }
>
>
>

Looks at what indexing with an index value of 0 does.

Operator [] want to test index >= 0, not > 0

On 5/12/2022 6:23 PM, Richard Damon wrote:
> On 5/12/22 6:51 PM, olcott 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('_');
>> }
>>
>>
>>
>
> Looks at what indexing with an index value of 0 does.
>
> Operator [] want to test index >= 0, not > 0

Good catch. I just wrote that function as a simplification.

--
Copyright 2022 Pete Olcott

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

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

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

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

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

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

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

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

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.

Click here to read the complete article

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

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
>

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); }

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()?