Unordered Array Lists

[yoked88]

I am looking for some opinions on this. Any help on efficiency and pointers is greatly valued.

#ifndef H_arrayListType  
#define H_arrayListType
#include <iostream>

/* virtual functions are implemented when you have two different objects
that need to access the same function, but with different meanings. This
is an abstract class, no objects can be created of this class.*/

using namespace std;

class arrayListType
{
public:
	bool isEmpty() const;
	bool isFull() const;
	int listSize() const;
	int maxListSize() const;
	void print() const;
	bool isItemAtEqual(int,int) const;
	virtual void insertAt(int,int) = 0;
	virtual void insertEnd(int) = 0;
	void removeAt(int);
	void retrieveAt(int,int&) const;
	virtual void replaceAt(int,int) = 0;
	void clearList();
	virtual int seqSearch(int) const = 0;
	virtual void remove(int) = 0;
	arrayListType(int size = 100);
	arrayListType(const arrayListType& otherList);
	virtual ~arrayListType();
protected:
	int *list;
	int length;
	int maxSize;
};

bool arrayListType::isEmpty() const
{
	return (length == 0);
}

bool arrayListType::isFull() const
{
	return (length == maxSize);
}

int arrayListType::listSize() const
{
	return length;
}

int arrayListType::maxListSize() const
{
	return maxSize;
}

void arrayListType::print() const
{
	for(int i = 0; i < length; i++)
		cout<<list[i]<<" ";
	cout<<endl;
}

bool arrayListType::isItemAtEqual(int location, int item) const
{
	if(location < 0 || location >= length)
	{
		cout<<"The location is out of range."
			<<"This is an error, you shouldn't be here!"<<endl;
		return false;
	}
	else
		return (list[location] == item);
}

void arrayListType::removeAt(int location)
{
	if(location < 0 || location >= length)
		cout<<"The location is out of range."
		    <<"This is an error, you shouldn't be here!"<<endl;
	else
	{
		for(int i = location; i < length - 1; i++)
			list[i] = list[i + 1];
		length--;
	}
}

void arrayListType::retrieveAt(int location, int &retItem) const
{
	if(location < 0 || location >= length)
		cout<<"The location is out of range."
		    <<"This is an error, you shouldn't be here!"<<endl;
	else
		retItem = list[location];
}

void arrayListType::clearList()
{
	length = 0;
}

arrayListType::arrayListType(int size)
{
	if(size <= 0)
	{
		cout<<"The array size must be positive. Creating "
			<<"an array with default size of 100."<<endl;
		maxSize = 100;
	}
	else
		maxSize = size;
	length = 0;
	list = new int[maxSize];
}

arrayListType::~arrayListType()
{
	delete [] list;
}

arrayListType::arrayListType(const arrayListType &otherList)
{
	maxSize = otherList.maxSize;
	length = otherList.length;
	list = new int[maxSize];
	for(int j = 0; j < length; j++)
		list[j] = otherList.list[j];
}
#endif 

#ifndef H_unorderedListType
#define H_unorderedListType
#include <iostream>
#include "arrayListType.h"

using namespace std;

class unorderedListType: public arrayListType
{
public:
	void insertAt(int,int);
	void insertEnd(int);
	void replaceAt(int,int);
	int seqSearch(int) const;
	void remove(int);
	unorderedListType(int size = 100);
};

void unorderedListType::insertAt(int location, int item)
{
	if(location < 0 || location >= maxSize)
		cout<<"The index is out of range."<<endl;
	else if(length >= maxSize)
		cout<<"The list is full."<<endl;
	else
	{
		for(int i = length; i > location; i--)
			list[i] = list[i - 1];
		list[location] = item;
		length++;
	}
}

void unorderedListType::insertEnd(int item)
{
	if(length >= maxSize)
		cout<<"The list is full."<<endl;
	else
	{
		list[length] = item;
		length++;
	}
}

int unorderedListType::seqSearch(int item) const
{
	int loc = 0;
	bool found = false;
	for(loc = 0; loc < length; loc++)
		if(list[loc] == item)
		{
			found = true;
			break;
		}
    if(found)
		return loc;
	else
		return -1;
}

void unorderedListType::remove(int item)
{
	int loc;
	if(length == 0)
		cout<<"The list is empty."<<endl;
	else
	{
		loc = seqSearch(item);
		if(loc != -1)
			removeAt(loc);
		else
			cout<<"The item is not in the list."<<endl;
	}
}

void unorderedListType::replaceAt(int location, int item)
{
	if(location < 0 || location >= length)
		cout<<"The location is out of range."<<endl;
	else
		list[location] = item;
}

unorderedListType::unorderedListType(int size):arrayListType(size)
{
}
#endif 

#include <iostream>
#include "unorderedListType.h"

using namespace std;

int main()
{
	int xxx;
	unorderedListType myList(25);
	int num;
	cout<<"Enter 8 integers:  ";
	for(int i = 0; i < 8; i++)
	{
		cin>>num;
		myList.insertEnd(num);
	}
	cout<<"\nmyList values :"<<endl;
	myList.print();
	unorderedListType yourList(myList); // test copy constructor
	cout<<"\nyourList values: "<<endl;
	yourList.print();
	cout<<"\nEnter a number to be deleted:  ";
	cin>>num;
	myList.remove(num);
	cout<<"\nAfter removing "<<num<<" myList: ";
	myList.print();
	cout<<"\nEnter a number to be found:  ";
	cin>>num;
	cout<<endl;
	if(myList.seqSearch(num) != -1)
		cout<<num<<" found in myList."<<endl;
	else
		cout<<num<<" is mot in myList."<<endl;
	cin>>xxx; // read output
	return 0;
}

[yoked88]

And what is the point of private variables if we can manipulate the outside of the class?

#include <iostream>

using namespace std;

class test
{
public:
	void setX(int);
	void print() const;
	int& addressofX();
private:
	int x;
};

int main()
{
	int xxx;
	test me;
	int &y = me.addressofX();
	me.setX(50);
	cout<<"Value of x = ";
	me.print();
	cout<<endl;
	y = 25;
	cout<<"After assignment of y = 25, value of x = ";
	me.print();
	cout<<endl;
	cin>>xxx;
	return 0;
}

void test::setX(int num1)
{
	x = num1;
}

void test::print() const
{
	cout<<x<<endl;
}

int& test::addressofX()
{
	return x;
}

[Disch]

I only skimmed... but here's my input:

1) void retrieveAt(int,int&) const; = blech. Prefer return values to 'out' parameters for most tasks. int retrieveAt(int) const; would be a better way to make this function.

Out parameters require you to have a variable of that type, and also forbid you from using the function call as an r value:

int tmp;
obj.retrieveAt(5,tmp);
int foo = 10 + tmp;

// vs

int foo = 10 + obj.retrieveAt(5);

2) Great job being const correct. Well done.


3) Only inlined implementation should be in the header. If you #include this header in multiple cpp files you'll get linker errors. Move the function bodies to a cpp file.

4) Don't cout from a class like this. It assumes the user is using the console and that they want error messages printed to it. Better to throw an exception and have the program deal with it however it wants.

5)

And what is the point of private variables if we can manipulate the outside of the class?

There isn't one. That 'addressofX' function defeats the entire point of making x private. You might as well just make x public.

The whole idea of making variables private is that the user can't change them to screw things up. For example, if arrayListType::list was public the user might be able to accidentally corrupt the pointer and make the class malfunction. But because it's protected, such accidents are virtually impossible, your class will function properly and be easier to use correctly, and errors can be more easily found and corrected.

[yoked88]

Wow, that's awesome, making retrieveAt a return value of int makes so much more sense too. Thanks Disch. About the .cpp files, I thought that defining them, (#define, #endif) prevented the errors of multiple inclusions of the same header, so this is false? The program is totally functional as is, but if it's more efficient then yeah! I totally get what you are saying about using cout from a class too, it really makes sense, I just haven't gotten to recursion or exceptions yet; that's after templates and overloading, so soon, but I get the gist of what you are implying. And the reference operator makes accessing private variables a possibility from what I understand...is there a way to avoid this as in make them completely inaccessible from outside of the class? My book just isn't giving me the info that I want and neither are other online sources, or am I trying to get too technical for being a newbie?

[firedraco]

Yes, but it means that if you make any changes to the header file, you have to compile ALL the files that included it, but if you have the functions in separate .cpp files, then you only have to recompile that .cpp/object file.

[Disch]

I thought that defining them, (#define, #endif) prevented the errors of multiple inclusions of the same header, so this is false?

You misunderstand.

Include guards (#ifndef, #define, #endif), prevent the same header file from being #included multiple times in a SINGLE source file. IE if you do this:

// a.cpp
#include "a.h"
#include "a.h" 

The second #include will effectively be skipped because of the guard.

The program is totally functional as is,

Only because you only have one source file that includes this header. As soon as you have another source file #include that header, you'll have linker errors.

The problem is you're defining (what appears to be) multiple bodies for the same function.

#include is kind of like a copy/paste operation. The #include line is "replaced" with the contents of the file being included. So when you #include a header, it's basically putting that header at the top of the cpp file.

NOW... when a header contains a function body, this means it puts that function body in every cpp file that includes the header which means that your program has multiple bodies for the same function. Even though they all contain identical code, the linker will see them all as different functions.

So when you try to call the function... how can the linker know which version you're calling?

Only templates, inline, or globally static function bodies should be in header files.

And the reference operator makes accessing private variables a possibility from what I understand...is there a way to avoid this as in make them completely inaccessible from outside of the class?

Yeah.

Just make your member private and don't make a function that returns a reference to it.

[gcampton]

If you have get functions that just return value do they automatically inline being in the header?
I just tried to link my header to another .cpp and it seemed to compile no problems. I have 2 get functions, 2 operator overload, and ctor, dtor implemented in the header.

[yoked88]

Ooohhh I see whats going on here. And that's why the emphasis on .cpp files...and now it's all making sense now. You guys rule and could totally replace my programming instructor. Thanks a lot for the clarification!

[Disch]

If you have get functions that just return value do they automatically inline being in the header?

Not unless you use the inline keyword, or unless they're implicitly inlined by being in the body of a class:

// example.h

class Example
{
  void a() { }  // This is OK, it is implicitly inlined

  void b();
  void c();
};

inline void Example::a()
{
  // this is OK, it is inlined
}

void Example::c()
{
  // this will cause linker errors
  //  the linker will complain that Example::c is multiply defined
}

Templates, of course, are exempt from this rule and should always be in a header, even when not inlined.

globally static functions can also be put in header files, but I wouldn't recommend it. (I know I said "should" in my previous post, but that was a mistake. It's a bad idea)

You guys rule and could totally replace my programming instructor. Thanks a lot for the clarification!

Heh. No problem. ^^