Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #47017 > unrolled thread
| Started by | xerofoify <xerofoify@gmail.com> |
|---|---|
| First post | 2016-12-02 10:14 -0800 |
| Last post | 2016-12-03 08:05 +0100 |
| Articles | 8 on this page of 128 — 21 participants |
Back to article view | Back to comp.lang.c++
Qucksort for Linked List xerofoify <xerofoify@gmail.com> - 2016-12-02 10:14 -0800
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-02 19:17 +0000
Re: Qucksort for Linked List Melzzzzz <mel@zzzzz.com> - 2016-12-02 22:09 +0100
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-02 21:26 +0000
Re: Qucksort for Linked List Melzzzzz <mel@zzzzz.com> - 2016-12-02 22:37 +0100
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-02 21:41 +0000
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-12 13:16 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-12 18:32 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-12 18:34 +0000
Re: Qucksort for Linked List asetofsymbols@gmail.com - 2016-12-12 10:44 -0800
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-12 21:30 +0000
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-13 07:26 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-13 17:51 +0000
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-13 14:52 -0800
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-14 10:26 +0000
Re: Qucksort for Linked List "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-14 13:05 +0100
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-14 14:06 +0000
Re: Qucksort for Linked List "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-14 16:59 +0100
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-14 20:19 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-14 21:23 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-14 21:42 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-14 22:43 +0000
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-16 11:02 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-16 23:00 +0000
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-16 23:00 -0800
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-17 20:17 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-18 21:15 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-18 21:49 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-18 21:51 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-18 21:52 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-18 21:56 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-18 22:04 +0000
Re: Qucksort for Linked List Paavo Helde <myfirstname@osa.pri.ee> - 2016-12-19 00:22 +0200
Re: Qucksort for Linked List "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-19 00:18 +0100
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-19 08:58 +0100
Re: Qucksort for Linked List gwowen <gwowen@gmail.com> - 2016-12-19 06:17 -0800
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-19 20:14 +0000
Re: Qucksort for Linked List woodbrian77@gmail.com - 2016-12-23 10:55 -0800
Re: Qucksort for Linked List Daniel <danielaparker@gmail.com> - 2016-12-23 12:08 -0800
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-27 10:39 +0100
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-27 17:48 +0000
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-27 17:53 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-27 18:52 +0000
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-27 19:06 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-27 19:17 +0000
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-27 21:05 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-27 21:15 +0000
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-27 21:21 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-27 21:29 +0000
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-27 21:33 +0000
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-28 10:03 +0100
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-28 15:34 +0000
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-29 09:38 +0100
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-28 16:40 +0000
Re: Qucksort for Linked List Daniel <danielaparker@gmail.com> - 2016-12-28 08:55 -0800
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-28 17:02 +0000
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-28 17:12 +0000
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-28 17:21 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-29 11:05 -0600
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-29 17:43 +0000
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-30 09:48 +0100
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-30 11:37 +0000
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-30 13:23 +0100
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-29 11:00 +0100
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-29 09:43 +0100
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-18 22:56 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-18 22:52 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-18 23:07 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-19 05:48 +0000
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-19 08:09 +0000
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-19 08:06 +0000
Re: Qucksort for Linked List leigh.v.johnston@googlemail.com - 2016-12-19 04:46 -0800
Re: Qucksort for Linked List bartekltg <bartekltg@gmail.com> - 2016-12-19 15:04 +0100
Re: Qucksort for Linked List gwowen <gwowen@gmail.com> - 2016-12-19 06:40 -0800
Re: Qucksort for Linked List bartekltg <bartekltg@gmail.com> - 2016-12-19 18:48 +0100
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-19 18:53 +0000
Re: Qucksort for Linked List bartekltg <bartekltg@gmail.com> - 2016-12-19 21:26 +0100
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-19 20:32 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-19 19:09 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-19 19:14 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-19 19:31 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-19 19:45 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-19 20:19 +0000
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-20 07:18 +0000
Re: Qucksort for Linked List leigh.v.johnston@googlemail.com - 2016-12-20 04:31 -0800
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-21 07:08 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-21 19:39 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-21 20:54 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-21 19:28 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-21 19:43 +0000
Re: Qucksort for Linked List Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-12-21 20:34 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-21 20:53 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-21 20:58 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-21 23:34 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-22 00:19 +0000
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2017-01-04 07:04 +0000
Re: Qucksort for Linked List Daniel <danielaparker@gmail.com> - 2017-01-04 07:18 -0800
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2017-01-04 18:39 +0000
Re: Qucksort for Linked List Daniel <danielaparker@gmail.com> - 2017-01-05 07:29 -0800
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2017-01-05 21:21 +0000
Re: Qucksort for Linked List Ian Collins <ian-news@hotmail.com> - 2017-01-06 10:35 +1300
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-22 21:43 -0800
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-22 22:09 -0800
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-23 17:00 +0000
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-23 12:03 -0800
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-23 20:25 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-23 20:56 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-23 22:02 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-23 22:14 +0000
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-29 13:56 -0800
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-29 23:26 +0000
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-29 20:25 -0800
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2017-01-04 07:07 +0000
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2017-01-26 22:40 -0800
Re: Qucksort for Linked List xerofoify <xerofoify@gmail.com> - 2016-12-02 13:47 -0800
Re: Qucksort for Linked List ruben safir <ruben@mrbrklyn.com> - 2016-12-02 17:38 -0500
Re: Qucksort for Linked List xerofoify <xerofoify@gmail.com> - 2016-12-02 14:53 -0800
Re: Qucksort for Linked List Jerry Stuckle <jstucklex@attglobal.net> - 2016-12-02 19:50 -0500
Re: Qucksort for Linked List ruben safir <ruben@mrbrklyn.com> - 2016-12-02 21:17 -0500
Re: Qucksort for Linked List xerofoify <xerofoify@gmail.com> - 2016-12-02 20:44 -0800
Re: Qucksort for Linked List xerofoify <xerofoify@gmail.com> - 2016-12-02 20:52 -0800
Re: Qucksort for Linked List Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-12-03 11:07 +0000
Re: Qucksort for Linked List ruben safir <ruben@mrbrklyn.com> - 2016-12-03 13:38 -0500
Re: Qucksort for Linked List Öö Tiib <ootiib@hot.ee> - 2016-12-03 01:46 -0800
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-12 13:18 +0000
Re: Qucksort for Linked List "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-03 01:16 +0100
Re: Qucksort for Linked List bartekltg <bartekltg@gmail.com> - 2016-12-03 08:25 +0100
Re: Qucksort for Linked List bartekltg <bartekltg@gmail.com> - 2016-12-03 08:05 +0100
Page 7 of 7 — ← Prev page 1 2 3 4 5 6 [7]
| From | xerofoify <xerofoify@gmail.com> |
|---|---|
| Date | 2016-12-02 20:52 -0800 |
| Message-ID | <9e354e3a-6f50-4434-b1ab-0c75fcf14f80@googlegroups.com> |
| In reply to | #47061 |
This is my complete code.
#pragma once
#include <utility>
#include<iostream>
template<typename T>
class DList {
private:
/*This is the Node object used for each list element
data members
@data - represents the data held inside the Node and of type T or the List's data type
@prev - previous element in the list
@next - next element in the list
*/
struct Node {
T data_;
Node* next_;
Node* prev_;
/*constructor
takes the following values as parameters
@ T data - type of data and value of data to be stored for this Node's data,
safe empty state by default
@Node* next - next Node in list
sets to NULL pointer by default
@Node* prev - pre Node in list
sets to NULL pointer by default
*/
Node(const T& data = T{}, Node* next = nullptr, Node* prev = nullptr) {
data_ = data;
next_ = next;
prev_ = prev;
}
};
/* head_ is the first node in the list and tail_ is the last node */
Node* head_;
Node* tail_;
/*Number of elements in the list*/
int size_;
public:
/*Iterator that is const in nature, i.e. cannot modifty the iterator after creation*/
class const_iterator {
protected:
Node* curr;
private:
friend class DList;
/*Constructor that sets Node to Node passed*/
const_iterator(Node* pass) {
curr = pass;
}
public:
/* A Constructor that sets internal Node to nullptr*/
const_iterator() {
curr = nullptr;
}
/*This function checks that the passed iterator is equal to the current
one including pointing to the same Node in the list*/
bool operator==(const_iterator rhs) {
return curr == rhs.curr;
}
/*This function is the opposite of the one above in that it
checks if the iterator passed is not equal in both being the
same object and pointing to the same Node in the list*/
bool operator!=(const_iterator rhs) {
return curr != rhs.curr;
}
/*This makes the interal Node point to the next Node in
the list before returning the current object as a point*/
const_iterator operator++() {
curr = curr->next_;
return *this;
}
/*This does the same as above but returns the previos
Node in the list as a iterator rather then *this*/
const_iterator operator++(int) {
const_iterator next = *this;
curr = curr->next_;
return next;
}
/*This moves the internal Node to the previous
object before returning the current object's
pointer*/
const_iterator operator--() {
curr = curr->prev_;
return *this;
}
/*Same as above but return a new iterator
that points to the previous Node rather
than *this*/
const_iterator operator--(int) {
const_iterator prev = *this;
curr = curr->prev_;
return prev;
}
/*Return the data held by this Node*/
const T& operator*() const {
return curr->data_;
}
};
/*This is the same as above except not const in nature i.e. can modifiy*/
class iterator :public const_iterator {
friend class DList;
/*Constructor that takes a parameter sets the Node to the Node passed*/
iterator(Node* pass) {
this->curr = pass;
}
/*Returns Node for Quicksort*/
Node* getNode() {
return this->curr;
}
public:
/*Constructor for this class
One that takes no parameters sets interal node used by interator to nullptr
*/
iterator() {
this->curr = nullptr;
}
/*Return the data held by this Node*/
T& operator*() {
return this->curr->data_;
}
/*This makes the interal Node point to the next Node in
the list before returning the current object as a point*/
iterator operator++() {
this->curr = this->curr->next_;
return *this;
}
/*This does the same as above but returns the previos
Node in the list as a iterator rather then *this*/
iterator operator++(int) {
iterator next = *this;
this->curr = this->curr->next_;
return next;
}
/*This moves the internal Node to the previous
object before returning the current object's
Same as above but return a new iterator */
iterator operator--() {
this->curr = this->curr->prev_;
return *this;
}
/*This moves the internal Node to the previous
object before returning the current object's
Same as above but return a new iterator
that points to the previous Node rather
than *this*/
iterator operator--(int) {
iterator prev = *this;
this->curr = this->curr->prev_;
return prev;
}
};
private:
//Swap function for nodes
void swap ( Node* a, Node* b ) {
Node *t = a;
a = b;
b = t;
}
//Partion function for nodes
Node* partition(Node *l, Node *h)
{
T x = h->data_;
Node *i = l->prev_;
Node* j = new Node();
for (j; j != h; j = j->next_) {
if (j->data_ <= x) {
i = (i == nullptr)? l : i->next_;
swap(i, j);
}
}
i = (i == nullptr)? l : i->next_;
swap(i, h);
return i;
}
/*this does qsort recursively on the elements from the Node at the first iterator passed up to
and including the Node at iterator two*/
void qSortrecursive(iterator first, iterator second) {
Node* h = first.getNode();
Node* l = second.getNode();
if (h != NULL && l != h && l != h->next_)
{
struct Node *p = partition(l, h);
qSortrecursive(l, p->prev_);
qSortrecursive(p->next_, h);
}
}
/*This does qsort as above but Iterative and not recursively*/
void qSortIterative(iterator first, iterator second) {
Node* h = first.getNode();
Node* l = second.getNode();
if (h != NULL && l != h && l != h->next_) {
struct Node *p = partition(l, h);
qSortIterative(l, p->prev_);
qSortIterative(p->next_, h);
}
}
public:
/*Constructor sets list to empty state
i.e. head_ and tail_ are nullptr and
size is 0, no Nodes*/
DList() {
head_ = new Node();
tail_ = new Node();
head_->next_ = tail_;
tail_->prev_ = head_;
size_ = 0;
}
/*Creates and returns a iterator to the beginning of the list*/
iterator begin() {
iterator begin(head_->next_);
return begin;
}
/*Returns a iterator to one after the end of the list after
creating a iterator that does so*/
iterator end() {
iterator end(tail_);
return end;
}
/*This is the same as iterator begin but creates a const_iterator
rather then a iterator*/
const_iterator begin() const {
const_iterator begin(head_->next_);
return begin;
}
/*This creates a const iterator to the Node after the end of the list*/
const_iterator end() const {
const_iterator end(tail_);
return end;
}
/* Pushs a new Node into the list's first element with a value
passed to it as the Node's data member*/
void push_front(const T& data) {
Node* first = head_->next_; //it is ok if this
//is back sentinel
Node* temp = new Node(data, first, head_);
head_->next_ = temp;
first->prev_ = temp;
size_++;
}
/* Pushs a new Node into the list's last element with a value
passed to it as the Node's data member*/
void push_back(const T& data) {
Node* last = tail_->prev_;
Node* temp = new Node(data, tail_, last);
tail_->prev_ = temp;
last->next_ = temp;
size_++;
}
/* Removes the Node at the beginning of the list*/
void pop_front() {
Node* first = head_->next_;
if (first != tail_) {
Node* secondFirst = first->next_;
head_->next_ = secondFirst;
secondFirst->prev_ = head_;
delete first;
size_--;
}
}
/*Removes the Node at the end of the list*/
void pop_back() {
Node* last = tail_->prev_;
if (last != head_) {
Node* secondLast = last->prev_;
tail_->prev_ = secondLast;
secondLast->next_ = tail_;
delete last;
size_--;
}
}
/*Insert Node at the point of the iterator passed with
the data passed becoming the inseted Node's data member*/
iterator insert(iterator loc, const T& data) {
Node* curr = loc.curr;
std::cout << loc.curr;
Node* prev = curr->prev_;
Node* New = new Node(data, curr, prev);
prev->next_ = New;
curr->prev_ = New;
size_++;
loc--;
return loc;
}
/*Removes the element at the position passsed in the iterator argument*/
void erase(iterator it) {
Node* loc = it.curr;
Node* next = loc->next_;
Node* prev = loc->prev_;
prev->next_ = next;
next->prev_ = prev;
size_--;
delete loc;
}
/*Removes all elements from the first to the last*/
void erase(iterator first, iterator last) {
iterator it = first;
while(++it != last) {
erase(it);
it = first;
}
erase(first);
}
/*Searchs for a Node with the data passed as a arugment if found
return a iterator founding to it otherwise return iterator pointing
to one element beyond end of list*/
iterator search(T& data) {
iterator it = begin();
while (it != end()) {
if (it.curr->data_ == data) {
return it;
}
it++;
}
return end();
}
/*Searchs for a Node with the data passed as a arguument if found
return a const iterator founding to it otherwise return iterator pointing
to one element beyond end of list*/
const_iterator search(const T& data) const {
const_iterator it = begin();
while (it != end()) {
if (it.data_->data_ == data) {
return it;
}
it++;
}
return end();
}
/*Quicksort wrapper for iterative verision*/
void sortIterative() {
iterator last = end()--;
qSortIterative(begin(),last);
}
void qSort(){
iterator last = end()--;
qSortrecursive(begin(),last);
}
/*Returns true if list has size set to zero or no Nodes otherwise false*/
bool empty() const {
if (size_ == 0) {
return true;
}
else {
return false;
}
}
/*Returns size of list*/
int size() const {
return size_;
}
/*Destructor, destorys and cleans up each Node's member when the
list is destoryed*/
~DList() {
if (empty()) {
return;
}
iterator itBegin = begin();
iterator itEnd = end();
erase(itBegin,itEnd);
}
/*Copy Constructor, creates a new List that is a copy of the src list
passed as a argument*/
DList(const DList& src) {
head_ = new Node();
tail_ = new Node();
head_->next_ = tail_;
tail_->prev_ = head_;
size_ = src.size_;
if (src.empty() == false) {
iterator i = end();
const_iterator c = src.end();
c--;
while(c != src.begin()){
i = insert(i,*c);
c--;
}
push_front(*c);
}
}
/*Copy Assigment operator, assigns a new List that is a copy of the src list
passed as a argument*/
DList& operator=(const DList& src) {
head_ = new Node();
tail_ = new Node();
head_->next_ = tail_;
tail_->prev_ = head_;
size_ = src.size_;
if (src.empty() == false && src.head_ != head_) {
iterator i = end();
const_iterator c = src.end();
c--;
while(c != src.begin()){
i = insert(i,*c);
c--;
}
push_front(*c);
}
return *this;
}
/*Move constructor - sets list to list passed in agrument src but steals or
moves it other rather then copies the values of the Nodes and themselves*/
DList(DList&& src) {
if (src.head_ == tail_) {
head_ = tail_ = nullptr;
size_ = 0;
}
else {
head_ = std::move(src.head_);
tail_ = std::move(src.tail_);
size_ = std::move(src.size_);
src.head_ = nullptr;
src.tail_ = nullptr;
size_ = src.size_;
}
}
/*Move Assignment operator - sets list to list passed in agrument src but steals or
moves it other rather then copies the values of the Nodes and themselves*/
DList& operator=(DList&& src) {
head_ = std::move(src.head_);
tail_ = std::move(src.tail_);
size_ = std::move(src.size_);
src.head_ = nullptr;
src.tail_ = nullptr;
size_ = src.size_;
return *this;
}
};
The reason I am asking is there appears to be no good examples for quicksort *with Node* swap not data swap which is what I want. So can someone point me to an example that does it by swapping the nodes and not the data.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2016-12-03 11:07 +0000 |
| Message-ID | <87fum5jmnp.fsf@bsb.me.uk> |
| In reply to | #47062 |
xerofoify <xerofoify@gmail.com> writes:
There seems to be more code than I'd expect and I don't have time to go
though it but here are two remarks that jump out at me...
<snip>
> //Swap function for nodes
> void swap ( Node* a, Node* b ) {
> Node *t = a;
> a = b;
> b = t;
> }
This function does nothing. It alters only local objects so has no
effect on the lists you are trying to alter.
> The reason I am asking is there appears to be no good examples for
> quicksort *with Node* swap not data swap which is what I want. So can
> someone point me to an example that does it by swapping the nodes and
> not the data.
It's not a natural list algorithm, so examples will be rare. It takes
care not to make it very inefficient on linked lists, but you can
probably find some tips about that in the literature about function
programming. Can I ask why you are using it?
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | ruben safir <ruben@mrbrklyn.com> |
|---|---|
| Date | 2016-12-03 13:38 -0500 |
| Message-ID | <o1v3fd$g3q$1@reader1.panix.com> |
| In reply to | #47061 |
On 12/02/2016 11:44 PM, xerofoify wrote:
> for (Node *j = l; j != h; j = j->next_) {
> 163 if (j->data_ <= x) {
> I am confused about why this two lines are segfaulting for me through.
the same reason why they always segfault is that your trying to assign
or look into a non-allocated space.
[toc] | [prev] | [next] | [standalone]
| From | Öö Tiib <ootiib@hot.ee> |
|---|---|
| Date | 2016-12-03 01:46 -0800 |
| Message-ID | <1b0db664-6066-47a5-adaf-5d38029720f8@googlegroups.com> |
| In reply to | #47035 |
On Friday, 2 December 2016 23:47:15 UTC+2, xerofoify wrote: > On Friday, December 2, 2016 at 1:14:46 PM UTC-5, xerofoify wrote: > > I am trying to write a linked list quicksort that works by only swapping the Nodes and was wondering why the below code does not work as I can't see why: > > I am wondering how to write quicksort by swapping the Nodes themselves > not the data. So was wondering how to do that and make the above > quicksort work. That does not make sense logically. A node of linked list contains data and pointers (IOW addresses) of next and/or previous node. So we can sort linked list by swapping data or we can sort it by rearranging the pointers. However if we swap both pointers and data of two nodes in list then we just break integrity of the list instead of sorting it.
[toc] | [prev] | [next] | [standalone]
| From | Juha Nieminen <nospam@thanks.invalid> |
|---|---|
| Date | 2016-12-12 13:18 +0000 |
| Message-ID | <o2m837$2s1e$2@adenine.netfront.net> |
| In reply to | #47068 |
Öö Tiib <ootiib@hot.ee> wrote: > On Friday, 2 December 2016 23:47:15 UTC+2, xerofoify wrote: >> On Friday, December 2, 2016 at 1:14:46 PM UTC-5, xerofoify wrote: >> > I am trying to write a linked list quicksort that works by only swapping the Nodes and was wondering why the below code does not work as I can't see why: >> >> I am wondering how to write quicksort by swapping the Nodes themselves >> not the data. So was wondering how to do that and make the above >> quicksort work. > > That does not make sense logically. > A node of linked list contains data and pointers (IOW addresses) of > next and/or previous node. > So we can sort linked list by swapping data or we can sort it > by rearranging the pointers. > However if we swap both pointers and data of two nodes in list then > we just break integrity of the list instead of sorting it. He is talking about changing the prev/next pointers of the nodes to make them change place in the list (in contrast to swapping the values of the nodes.)
[toc] | [prev] | [next] | [standalone]
| From | "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> |
|---|---|
| Date | 2016-12-03 01:16 +0100 |
| Message-ID | <o1t2vs$3er$1@dont-email.me> |
| In reply to | #47017 |
On 02.12.2016 19:14, xerofoify wrote:
> I am trying to write a linked list quicksort that works by only swapping the Nodes and was wondering why the below code does not work as I can't see why:
> //Swap function for nodes
> 154 void swap ( Node* a, Node* b )
> 155 { Node t = *a; *a = *b; *b = t; }
> 156 //Partion function for nodes
> 157 Node* partition(Node *l, Node *h)
> 158 {
> 159 T x = h->data_;
> 160
> 161 Node *i = l->prev_;
> 162 for (Node *j = l; j != h; j = j->next_) {
> 163 if (j->data_ <= x) {
> 164 i = (i == nullptr)? l : i->next_;
> 165 swap(i, j);
> 166 }
> 167 }
> 168 i = (i == nullptr)? l : i->next_;
> 169 swap(i, h);
> 170 return i;
> 171 }
> 172 /*this does qsort recursively on the elements from the Node at the first iterator passed up to
> 173 and including the Node at iterator two*/
> 174 void qSortrecursive(iterator first, iterator second) {
> 175 Node* h = first.getNode();
> 176 Node* l = second.getNode();
> 177 if (h != NULL && l != h && l != h->next_)
> 178 {
> 179 struct Node *p = partition(l, h);
> 180 qSortrecursive(l, p->prev_);
> 181 qSortrecursive(p->next_, h);
> 182 }
> 183 }
You can either swap the data in the nodes, or you can swap nodes by
unlinking them and reinserting.
To unlink a node that you have a pointer to, without copying data, and
without searching from the start of the list, you need a doubly linked list.
That said, quicksort is not really suited for linked lists. It's quick
(on average) because one can determine the two halves of an array in
constant time. With a linked list this is a linear time operation.
With a linked list you can instead use a merge sort.
Essentially this is the reason why you cannot do
std::list<T> items;
std::sort( items.begin(), items.end() ); //! Nah.
but must do e.g.
items.sort();
Well I've never understood why `std::sort` isn't just overloaded for
`std::list`, forwarding to the `sort` member function, that is, I've
never understood why `std::sort` /requires/ random access iterators, why
it can't just do the practical thing for the container at hand.
But, there is an issue.
Cheers & hth.,
- Alf
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartekltg@gmail.com> |
|---|---|
| Date | 2016-12-03 08:25 +0100 |
| Message-ID | <o1ts1t$286$1@node2.news.atman.pl> |
| In reply to | #47049 |
On 03.12.2016 01:16, Alf P. Steinbach wrote: > > I've > never understood why `std::sort` /requires/ random access iterators, why > it can't just do the practical thing for the container at hand. ...So I can made a container with random access iterator and do not have to rewrite whole <algorithm> header. Or I write my own iterator. > Well I've never understood why `std::sort` isn't just overloaded for > `std::list`, forwarding to the `sort` member function, that is, This is other, valid, question. Why std::sort do not check if the container do not have method sort, and use default only if needed. One reason I can thing of is that iterators do not have information about the container. Do it have information about the type of the container, I don't remember, but I do not see why it can't. But probably I'm wrong ;) bartekltg
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartekltg@gmail.com> |
|---|---|
| Date | 2016-12-03 08:05 +0100 |
| Message-ID | <o1tqs6$15v$1@node2.news.atman.pl> |
| In reply to | #47017 |
On 02.12.2016 19:14, xerofoify wrote:
> I am trying to write a linked list quicksort that works by only swapping the Nodes and was wondering why the below code does not work as I can't see why:
> //Swap function for nodes
> 154 void swap ( Node* a, Node* b )
> 155 { Node t = *a; *a = *b; *b = t; }
You are not swapping nodes, nor you swaping values! ;-)
For example, we have 5 nodes:
{value, pointer next, pointer prev}
0 { 111, 1, null }
1 { 222, 2 , 0 }
2 { 333, 3 , 1 }
3 { 444, 4 , 2 }
4 { 555, null , 3 }
It looks like that:
111 - 222 - 333 - 444 - 555
And now you swap node number 1 and 3.
You swap everything inside dereferenced node.
0 { 111, 1, null }
1 { 444, 4 , 2 }
2 { 333, 3 , 1 }
3 { 222, 2 , 0 }
4 { 555, null , 3 }
And now draw the linked list...
111 - 222 - 333 - 444 - 555
Hmm, I'm quite sure this is the same list;) Just put in memory
in different way.
If you want to swap two element, a and b, in a linked list,
you have to go to neighbours of a and b and (up to four objects!)
and change its "next" and "prev" pointers.
Of course you have to update pointers in a and b too.
Be carefull, a and b can be neighbour, a or b (or both)
can be on the edge of the list, and you have to keep track of the head.
The first problem is just a one "if" statement.
The second one can be taken care of with sentinel nodes,
on the head and on the tail. Or more "ifs" ;-)
And, as others, I have to say it is veri ineffective way of sorting
list.
If you have to/want to do it with qsort, do not swap objects.
Traverse through the sub-list and move nodes with data>x on
one list, and the other ones to the second list. Then link
both new list and link it to the rest (nodes outside your sublist,
l->prev and h->next (*), there you see that sentinel nodes are usefull).
*) I assumed l is the first element, and h is the last (but still a
valid object you want to sort, not like in STL, where 'last' is not
included)
This new qsort will be much faster, but still worse than mergesort.
The number of operation in one level is similar.
It has the same number of 'levels' if the partition is each time
ideal, in the other case - qsort has more.
bartekltg
[toc] | [prev] | [standalone]
Page 7 of 7 — ← Prev page 1 2 3 4 5 6 [7]
Back to top | Article view | comp.lang.c++
csiph-web