Best data structure?

[DumRat]

I need to find out the best data structures for A* algorithm. Well, it is not exactly A*, but I've changed it a bit. What I need is as follows. I am using Visual C++.

1. I am keeping a Map(not the STL map, but my own Map.), It is a 200*200 array.
2. i need to find the shortest paths between two locations.
3. I am keeping an Open list and a closed list for the implementation.
4. The basic operations on the Open list are by order of priority, Insertion, membership test and remove best.
5. The basic operations for the closed list are insertion and membership test. It only occationally needs a removal.

The efficiency is definitely a concern. So, what are the best data structures to be used? It would be nice if I can use the STL.

[sicarie]

I need to find out the best data structures for A* algorithm. Well, it is not exactly A*, but I've changed it a bit. What I need is as follows. I am using Visual C++.

1. I am keeping a Map(not the STL map, but my own Map.), It is a 200*200 array.
2. i need to find the shortest paths between two locations.
3. I am keeping an Open list and a closed list for the implementation.
4. The basic operations on the Open list are by order of priority, Insertion, membership test and remove best.
5. The basic operations for the closed list are insertion and membership test. It only occationally needs a removal.

The efficiency is definitely a concern. So, what are the best data structures to be used? It would be nice if I can use the STL.

So what do you want to store - those individual elements of the array, or arrays of 200x200 items? As you know the order of priority on your list, I would research the STL's options and decide from there...

[DumRat]

So what do you want to store - those individual elements of the array, or arrays of 200x200 items? As you know the order of priority on your list, I would research the STL's options and decide from there...

The individual elements of the array. An element of the array is an object of a class "MyNode", i can provide the overloaded operators <, > , == for this class. So, i want to store these nodes in the open list in descending order. the node with the lowest values is at the top. And I want good times for membership test on both the open list and the closed list. Thanx in advance.

[Ganon11]

Well, if you want fast performance during sorting, I'd recommend using a linked list, as insertion is very easy with the pointers. However, finding the node you want will be tedious compared to, say, a vector.

[DumRat]

Well, if you want fast performance during sorting, I'd recommend using a linked list, as insertion is very easy with the pointers. However, finding the node you want will be tedious compared to, say, a vector.

Yes, that is the problem. one of the main operations I need is to check for a node. So, isnt there anything better than those two data structures? The priority_queue class in the STL would have suited me fine if it offered any way of looking at it's members. But as far as i know, it only offers a peek at the top element which is most dissatisfyiing.

[Ganon11]

As far as I can remember,

VECTOR:

Random insertion (what is needed for sorted vector) is O(n) time
Random Selection is O(1) time
Insertion to front or back is O(1) time

LINKED LIST:

Random insertion is O(n) time (to find the place where the node belongs)
Random Selection is O(n) time
Insertion to front is O(1) time
Insertion to back is O(n) time (to traverse the entire list)

Now, if you wanted to build the vector/list before sorting, big-O times may vary. But from here, it looks like vector is a winner in my book.

[iLL]

If you need to find an element with minimum cost, use a binary tree. If you are going to be doing a lot of removing and adding, I’d use a hash table. It’s easier to maintain.

[Ganon11]

If you need to find an element with minimum cost, use a binary tree. If you are going to be doing a lot of removing and adding, I’d use a hash table. It’s easier to maintain.

A hash table would be difficult to keep sorted, since each string, integer pair would produce a unique hash value that wouldn't necessarily lend itself to sorting. A binary tree is a good idea - I had completely forgotten about it! If I'm not mistaken,

Adding an element is O(log n)
Finding an element is O(log n)
It's already sorted by definition

Looks like binary trees are the best way to go!

[DumRat]

A hash table would be difficult to keep sorted, since each string, integer pair would produce a unique hash value that wouldn't necessarily lend itself to sorting. A binary tree is a good idea - I had completely forgotten about it! If I'm not mistaken,

Adding an element is O(log n)
Finding an element is O(log n)
It's already sorted by definition

Looks like binary trees are the best way to go!

Seems like I have no choice. I was planning to use the priority_queue present in the STL, but it does not seerve my purpose. i think i will use the binary tree after all. thanx everyone for the help.