Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #84081
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Newsgroups | comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++ |
| Subject | Re: Implementing a two-way Turing Machine tape as an improvement to std::deque |
| Message-ID | <20220513170239.0000273b@reddwarf.jmc> (permalink) |
| References | (8 earlier) <Bo-dnemL1eT6P-D_nZ2dnUU7_81g4p2d@giganews.com> <20220513015816.00006f57@reddwarf.jmc> <D7WdnSjo4swvKOD_nZ2dnUU7_81g4p2d@giganews.com> <20220513080247.000077d7@reddwarf.jmc> <zdmdnV7tirvcHeP_nZ2dnUU7_8xQAAAA@giganews.com> |
| Organization | Jupiter Mining Corp |
| Date | 2022-05-13 17:02 +0100 |
Cross-posted to 4 groups.
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
Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 17:51 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-12 23:56 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 18:09 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 00:22 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 18:38 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 00:40 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 18:49 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 00:53 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 19:12 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 01:58 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 20:34 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Öö 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
csiph-web