C++

Forum

 
insertNextTo function, templated, and iterators

Arslan7041 (753)
I was given a piece of code that declares a singly list, doubly list and a vector. It fills these containers with random numbers, sorts them, then calls a function InsertNextTo. I have to implement this InsertNextTo fuction, description of which is below.

In main.cpp, implement the function insertNextTo, which takes a Container and an element, and adds the element to the container such that if it already appears in the container, it will be added next to its copy; otherwise it will be added at the end.

For example, if vector v has the elements [18, 3, 19, 6, 5, 10, 20, 17], after calling insertNextTo(v,6) it will look like this: [18, 3, 19, 6, 6, 5, 10, 20, 17].

After calling insertNextTo(v, 8), it will look like this: [18, 3, 19, 6, 6, 5, 10, 20, 17, 8].

The code is below, the relevant fucntion all the way at the end. I've written my question as a comment in the function. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
#include <iostream>
#include <time.h>
#include <vector>

#include "llist.h" // singly linked list class
#include "dllist.h" // doubly linked list class
#include "timing.h"

template <class Iter>
void selectionSort(Iter, Iter);				// implement
template <class Container, class T>
void insertNextTo(Container &, const T&);		// implement


struct time {
	uint64 start;
	std::string name;
	time(const std::string& str="") : start(GetTimeMs64()), name(str) {}
	void getTimeElapsed() {
		std::cout << name << "... " << GetTimeMs64() - start << std::endl;
	}
	void startAgain(const std::string& str="") {
		start = GetTimeMs64();
		name = str;
	}
};

int main(int argc, char** argv) {
	srand (time(NULL));

	int sz;
	std::cout << "Enter data size: ";
	std::cin >> sz;

	int arr1[sz];
	int arr2[sz];
	for (int i = 0; i < sz; i++) {
		arr1[i] = rand() % 100;
		arr2[i] = rand() % 100;
	}

	struct time t("filling list");
	List<int> lst;
	for (int i = 0; i < sz; i++) {	lst.push_front(arr1[i]); }
	t.getTimeElapsed();

	t.startAgain("filling dlist");
	DList<int> dlst;
	for (int i = 0; i < sz; i++) {	dlst.push_front(arr1[i]); }
	t.getTimeElapsed();

	t.startAgain("filling vector");
	std::vector<int> v;
	for (int i = 0; i < sz; i++) { v.push_back(arr1[i]); }
	t.getTimeElapsed();

	t.startAgain("sorting list");
	selectionSort(lst.begin(), lst.end());
	t.getTimeElapsed();

	t.startAgain("sorting dlist");
	selectionSort(dlst.begin(), dlst.end());
	t.getTimeElapsed();

	t.startAgain("sorting vector");
	selectionSort(v.begin(), v.end());
	t.getTimeElapsed();

	t.startAgain("adding more to list");
	for(int i = 0; i < sz; i++) { insertNextTo(lst, arr2[i]); }
	t.getTimeElapsed();

	t.startAgain("adding more to dlist");
	for(int i = 0; i < sz; i++) { insertNextTo(dlst, arr2[i]); }
	t.getTimeElapsed();

	t.startAgain("adding more to vector");
	for(int i = 0; i < sz; i++) { insertNextTo(v, arr2[i]); }
	t.getTimeElapsed();
}

template <class Iter>
void selectionSort(Iter begin, Iter end)
{
    Iter it, jt, minIt;

    for(it = begin; it != end; ++it)
    {
        minIt = it;
        for(jt = ++it; jt != end; ++jt)
        {
            if(*jt < *minIt)
                minIt = jt;
        }
        std::swap(*it, *minIt);
    }
}

template <class Container, class T>
void insertNextTo(Container &C, const T& val)
{

    Container iter; // this is where im getting an error. 
    // what should the type of my iterator be? 
     // I am not allowed to include the <iterator> header file. 
    
    for(iter = C.begin(); iter != C.end(); ++iter)
    {
        if(*iter == val)
        {
            C.insert(++iter, val);
            return;
        }
    }

    C.insert(iter, val);
}
Last edited on
coder777 (8444)
what should the type of my iterator be?
This depends on how the iterator for your container is actually defined.

For a std container it would look like this:

Container::iterator iter;
Arslan7041 (753)
Ah, that works. But now my selectionSort on dlist fails. Program seems to crash at this point.

Here is the entire DList class with the iterator class implementation as well:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
#ifndef DLLIST_H
#define DLLIST_H

#include <iterator>
template <class T>
class DList
{
	struct Node
	{
		Node(const T& x,Node* y = 0, Node* p = 0):m_data(x), m_next(y), m_prev(p){}
		T m_data;
		Node* m_next;
		Node* m_prev;
	};

	Node* m_head;
	Node* m_back;
public:

	class iterator
	{
		Node* m_rep;
	public:
		friend class DList;

		inline iterator(Node* x=0):m_rep(x){}
		inline iterator(const iterator& x):m_rep(x.m_rep) {}
		inline iterator& operator=(const iterator& x)
		{
			m_rep=x.m_rep; return *this;
		}
		inline iterator& operator++()
		{
			m_rep = m_rep->m_next; return *this;
		}
		inline iterator operator++(int)
		{
			iterator tmp(*this); m_rep = m_rep->m_next; return tmp;
		}
		inline T& operator*() const { return m_rep->m_data; }
		inline Node* operator->() const { return m_rep; }
		inline bool operator==(const iterator& x) const
		{
			return m_rep == x.m_rep;
		}
		inline bool operator!=(const iterator& x) const
		{
			return m_rep != x.m_rep;
		}

	};


	DList() : m_head(0), m_back(0) {}
	~DList() { clear(); }
	void clear() { while (!empty()) pop_front(); }

	inline void push_front(const T&x)
	{
		Node* tmp = new Node(x);
        if(m_head == 0)
        {
            m_head = tmp;
            m_back = tmp;
        }

        else
        {
            tmp->m_next = m_head;
            m_head = tmp;
            tmp->m_next->m_prev = tmp;
        }

	}

	inline void pop_front()
	{
		if (m_head)
		{
			Node* newhead = m_head->m_next;

			newhead->m_prev = m_head->m_prev;
			delete m_head;
			m_head = newhead;
		}
	}
	inline bool empty() { return m_head; }

	inline T& front() { return *begin(); }
	inline const T& front() const { return *begin(); }

	inline iterator begin() { return iterator(m_head); }
	inline iterator end() { return iterator(m_back); }

	// insert y before x. Intended to parallel vector operation
	void insert (iterator& x, const T& y) {
		Node *tmp = new Node(y, x.m_rep);		// new node's next will be x's node
		if (x==m_head)
		{
		    push_front(y);
		}

		else {
			Node *p = m_head;
			while (p && p->m_next != x.m_rep) p = p->m_next;
			if (!p) throw std::exception();
			tmp->m_next = p->m_next;
			p->m_next = tmp;
			tmp->m_prev = p;
			tmp->m_next->m_prev = tmp;
		}
	}

	// push back. Intended to parallel vector operation
	void push_back (const T& y) {
		Node *nd = new Node(y, NULL);
		if (!m_head)
        {
            m_head = nd;
            m_back = nd;
        }
		else {
			Node *p = m_head;
			while (p->m_next != 0) p = p->m_next;
			m_back = nd;
			p->m_next = nd;
			p->m_next->m_prev = p;

		}
	}

};

#endif


After printing "sorting list" and then the time, program crashes, so Im assuming the problem is somewhere when sort is called on dlist. I looked over my selectionSort function but dont see any problem.

Below is my selectionSort function:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
template <class Iter>
void selectionSort(Iter begin, Iter end)
{
    Iter it, jt, minIt;

    for(it = begin; it != end; ++it)
    {
        minIt = it; 
        for(jt = ++it; jt != end; ++jt)
        {
            if(*jt < *minIt)
                minIt = jt;
        }
        std::swap(*it, *minIt);
    }
}


Any idea why my program is crashing?
Last edited on
Arslan7041 (753)
Nevermind, got it to work. Made the following adjustment:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
template <class Iter>
void selectionSort(Iter begin, Iter end)
{
    Iter it, jt, minIt;

    for(it = begin; it != end; ++it)
    {
        minIt = it; 
        jt = it;    // how does making this
        ++jt;      // change suddenly make it work?
        for(; jt != end; ++jt)
        {
            if(*jt < *minIt)
                minIt = jt;
        }
        std::swap(*it, *minIt);
    }
}
Topic archived. No new replies allowed.