Undefine size vector like class what goes -99..-1..0..1..99.. (Don't know how to explain or not sure if it exists)

[Gyiove]

Hello everyone!

I'm thinking about creating a class what would be like vector but works
very differently.

Here's example code:

spuvec<int> v;

// now instead of pushing items in like in vectors i do this:
v[0] = 10; // just setting random numbers, numbers or any other type of value can be anything.
v[4] = 14;
v[-8] = -18;
v[-1000] = 1234;
v[1000] = 4321;

// Before i did that, vector or darray size was 0 but now it is 5.
// class spuvec<v> darray holds: 10, 14, -18, 1234, 4321
// and cout should print those numbers
cout << "v[0]:" << v[0] << endl;
cout << "v[4]:" << v[4] << endl;
cout << "v[-8]:" << v[-8] << endl;
cout << "v[-1000]:" << v[-1000] << endl;
cout << "v[1000]:" << v[1000] << endl;

// how ever, if i try to print something what i didn't define:
cout << "v[-33]:" << v[-33] << endl;

// then it will return the first value what were pushed into
// in this case the first value was 10 or v[0]
// if v[0] doesn't exist anymore it will return the second number
// but when i define null value in class:
v.definenull(9876);
// it will always return 9876 if i try to print undefined index

// to delete a item in spuvec class i do this:
v[-8] %= 0; // operator % its just my creativity here, it is easier to use
// that operator instead of calling a function like:
v.clear( -8 );
// to clear whole class i just do this:
v.clear();
// but thats not really important here. 

As you can see here that the vector like class can grow in 2 directions.
It is 1 dimensional ulimited/undefined sized vector.


The question is now, does something like this exists?
If not, how could i create something like this?
How can i sort items and then find them fast if using [] operator?

2 ideas of mine right now:

1. ( i find that it is horrible way to do it )

// i shall create 2 variables:
template <class T>
T *data;
int datasize;
T *ndata;
int ndatasize;

// and handle them like this:
T &operator[](int in) const {
if( in >= 0 ) { // positive index
if( in > datasize )
{
T *temp;
temp = new T[datasize];
// and now copying data from data variable to temp
// not sure yet how would i do that.
// perhaps creating a vector class what is holding positions where
// the data exist and copy only those no the whole size of data variable
// because it may be half empty or only contain 1 item
delete [] data;
data = temp;
return (*(this->data + in));
}

}
// negative index
if( datasize < in ){] // i think you get the idea where am i going with this
// doing the same thing like for positive value but instead in *= -1;
return (*(this->data - in));
}

2.

T *data;
vector<int> index;
// i think you are already get the idea where this is going
T &operator[](int in) const {
int r = -1;
for( int a = 0; a < index.size(); a++ ){
if( index[a] == in ){
r = a;
break;
}
}

if( r == -1 )
{
T *temp = new T[index.size() + 1];
for( int a = 0; a < index.size(); a++ ) temp[a] = data[a];
delete [] data;
data = temp;
index.push_pack(in);
}
...
}

I think both my ways are horrible.
Any ideas?

Thanks!

[Ispil]

You have managed to invent a std::deque (http://www.cplusplus.com/reference/deque/deque/). Does exactly what you want, but it doesn't go to negative indices- it just shifts them right.

[Gyiove]

Made a simple example class of what i want:

template <class T>
class spvec1
{
public:
	vector<T> data;
	vector<int> index;
	T d;

	spvec1(T defaultvalue)
	{
		d = defaultvalue;
	}

	~spvec1()
	{
		data.clear();
		index.clear();
	}

	T &operator[](int id)
	{
		for (int a = 0; a < index.size(); a++) if (index[a] == id) return data[a];
		index.push_back(id);
		data.push_back(d);
		return data[data.size() - 1];
	}
};

int main() {
	spvec1<int> i(-99);
	i[0] = 0;
	i[-99] = -199;
	i[43] = 143;
	i[1000] = 10000;
	i[-1000] = -10000;
	cout << "i[0]:" << i[0] << endl;
	cout << "i[-99]:" << i[-99] << endl;
	cout << "i[43]:" << i[43] << endl;
	cout << "i[1000]:" << i[1000] << endl;
	cout << "i[-1000]:" << i[-1000] << endl;
	cout << "i[88]:" << i[88] << endl;
	return 0;
}

Is there better way to do what am i doing here?

[S G H]

#include <map>
#include <iostream>

int main()
{
    std::map<int,int> my_map;
    my_map[-1748] = 42;
    my_map[73] = 128;
    std::cout << my_map[-1748] << ' ' << my_map[73] << ' ' << my_map[54578] << std::endl;
    return 0;
}

[Gyiove]

@S G H
Thank you very much!

Anyways, i was doing some research about map.
I needed to find out how it works.
I found a new thing instead called unordered_map.

Now the question is, from my first main post.
Is the unordered_map same as my idea #1 and map same as my idea #2?
( basically same )

I looked at the header of map but i didn't understood quite how the sorting
is working there.

[Gamer2015]

Now the question is, from my first main post.
Is the unordered_map same as my idea #1 and map same as my idea #2?
( basically same )

unordered_map and map behave the same way, the only difference is that, when iterating over them, unordered_map's iterator doesn't access the elements in order

This is because those two are implemented differently, unordered_map is implemented as a hashmap and map as a binary tree (you don't really have to understand what this means)

I looked at the header of map but i didn't understood quite how the sorting
is working there.

the sorting takes place automatically. When inserting an element the container places it in the correct position.

(caution: this section might confuse you)
You can choose what kind of compare-function you want to have by setting the 3rd template parameter.
The default is less which means that you'll iterate your map like this:
... -2, -1, 0, 1, 2 ... (imagine the nodes -2 to 2 exist)

You could set it to greather like this:

#include <iostream> // std::cout, std::endl
#include <functional> // std::greater
#include <map> // std::map

int main()
{
    std::map<int, int, std::greater<int>> container;
    container[2] = 500;
    container[0] = 10;
    container[1] = 100;
    
    for(auto& i : container)
        std::cout << i.first << " => " << i.second << std::endl; 
}

http://cpp.sh/92qr
Anything else than less doesn't seem to be a good idea in your case so I'll not go in details here.

I hope I could help you to find out the answer yourself. ;)

[S G H]

Unordered_map is unneededly unordered (which makes things messy).
By having a defined order in your map, operator[] can perform better (note: CAN. there's no guarantees on unordered_map that I know of).

By default, map puts elements in a lowest-to-highest order (using std::less, aka operator< ).

They both work as in #2, but the ordered map allows you to skip the rest of the search when (item you are looking for) is less than (the item you're currently iterating).

Since it's guaranteed to be an ordered map, performance is better with lower elements (because -5 is less than 5, if you're searching for the 5 it must check -5 first).
With higher elements, it's obvious, performance is lower.
With missing elements, it's got the optimal performance.

In unordered_map, searching an element has a random cost (usually the items inserted first require less time to be found).
Searching a missing element requires the whole list to be checked.

If I were you, I'd use a std::map.
If you UNNEEDEDLY want to make things complex (why?? std::map was made for this purpose!), use a std::vector of std::pair<int,int>.


If you want to know how something works, check out the reference section of cplusplus.com.

[Peter87]

SHG, it's not how it works. As Gamer2015 already said map is implemented as a binary search tree and unordered_map as a hash table.

http://en.wikipedia.org/wiki/Binary_search_tree
http://en.wikipedia.org/wiki/Hash_table

Even though the elements are sorted from lowest-to-highest in a std::map it doesn't mean it's faster accessing a lower value. The value that's fastest to access will be whatever value happen to be stored at the root of the tree (this might change when you add and remove elements). Usually it's more important to look at the worst or average case.

std::unordered_map was added much later to C++ than std::map so they must have a good reason. I think they called it unordered_map because map was already used by another container, but unorderedness is not the most important feature of std::unordered_map, it just happens to be a consequence of the way it's implemented. It's more efficient than std::map in many cases, but if you really want to know you should profile your code and compare. Note that when using std::map with string keys there are other comparison functions that you can use that often have better performance than the default std::less.