Overview
Examples
Screenshots
Comparisons
Applications
Download
Documentation
Tutorials
Bazaar
Status & Roadmap
FAQ
Authors & License
Forums
Funding Ultimate++
Search on this site
Search in forums












SourceForge.net Logo
Home » Developing U++ » U++ Developers corner » Linear sorted array vs. tree
Linear sorted array vs. tree [message #7689] Mon, 15 January 2007 14:33
mirek is currently offline  mirek
Messages: 13975
Registered: November 2005
Ultimate Member
For some time I was thinking about adding something like this container to U++ Core:

template <class T>
class Order {
	Vector<T> data;

public:
	int  Find(const T& x);
	int  FindAdd(const T& x);
	void Add(const T& x);
	const T& operator[](int i) const { return data[i]; }
	int  GetCount()                  { return data.GetCount(); }
};

template <class T>
void Order<T>::Add(const T& x)
{
	data.Insert(FindLowerBound(data, x), x);
}

template <class T>
int Order<T>::Find(const T& x)
{
	return FindBinary(data, x);
}

template <class T>
int Order<T>::FindAdd(const T& x)
{
	int i;
	i = FindUpperBound(data, x);
	if(i && data[i - 1] == x)
		return i;
	data.Insert(i, x);
	return i;
}


basically, sorted array used as associative container.

- advantage: less data used, so it could be useful for storing small maps.

- disadvantage - gets slow if there is too much data inserted (Insert slows it down).

Today I decided to put the disadvantage to the test and benchmark it against tree (std::set).

To my surprise, if we consider rather unlikely 2:1 find:insert ratio, this trivial implementation keeps the pace with std::set up to about 2000 elements! I am surprised.

Mirek

P.S.: Does not mean that Order will be part of U++ Core soon, it was just experiment...
Previous Topic: Funny way how to get thread specific id
Next Topic: CJK woes
Goto Forum:
  


Current Time: Mon Apr 29 01:42:54 CEST 2024

Total time taken to generate the page: 0.02878 seconds