CODEWITHSUNDEEP
c++algorithmdata-structures
Satchmo Brown
Satchmo Brown

Reputation: 1437

C++ - Data structure/algorithm that can keep track of structures (x and y) and values avoiding duplicates

I am looking for a data structure to use for a program I am working on. It keeps track of x and y values and needs to set the Z only if the x,y location isn't already my array.

I tried using a dynamic array and as the list grows, it becomes very very slow to iterate over the data. Here is what my structure looks like.

struct pos { int x; int y; }

The corresponding value is an integer that is only set if the x,y pair doesn't exist.

Edit: I have been trying to use a map but couldn't figure out how to use an x, y coordinate has the index, i.e. how to .insert(pos, zValue);

Upvotes: 0

Views: 2158

Answers (4)

Escualo
Escualo

Reputation: 42072

I somewhat think that the correct data structure seems to be a set, rather than a map. The reason is that if you are dealing with Points or Positions, the data type contains the three coordinates (x, y, and z).

Now, you seem to be interested in updating a Position's z-coordinate only if another point with the same x- and y-coordinate has not been updated yet.

I created the following implementation using an unordered set. Notice that the hasher and comparator only use x and y.

#include<iostream>
#include<unordered_set>

template<typename T>
struct Position {
  Position(T x, T y, T z)
      : x(x),
        y(y),
        z(z) {}
  T x, y, z;
};

template<typename T>
std::ostream& operator<<(std::ostream& os, const Position<T>& p) {
  os<<"("<<p.x<<", "<<p.y<<", "<<p.z<<")";
  return os;
}

struct point_equal {
  template<typename T>    
  bool operator()(const Position<T>& p1, const Position<T>& p2) const {
    return (p1.x == p2.x) && (p1.y == p2.y);
  }
};

struct point_hash {
  template<typename T>    
  std::size_t operator()(const Position<T>& p) const {
    std::hash<T> hasher;
    return hasher(p.x) ^ hasher(p.y);
  }
};

template<typename T>
class Particles {
 public:
  bool add(T x, T y, T z) {
    return m_particles.emplace(x, y, z).second;
  }
  void show() const {
    for(auto p : m_particles) {
      std::cout<<p<<std::endl;
    }    
  }
 private:
  typedef std::unordered_set<Position<T>, point_hash, point_equal> Container;
  Container m_particles;
};


int main() {
  Particles<int> p;
  std::cout<<std::boolalpha;  
  std::cout<<"should show (1, 2, 3)"<<std::endl;
  std::cout<<"Added new point? "<<p.add(1, 2, 3)<<std::endl;  
  p.show();
  std::cout<<"should show (1, 2, 3) again"<<std::endl;
  std::cout<<"Added new point? "<<p.add(1, 2, 4)<<std::endl;
  p.show();
  std::cout<<"should show (1, 2, 3) and (3, 4, 5)"<<std::endl;
  std::cout<<"Added new point? "<<p.add(3, 4, 5)<<std::endl;  
  p.show();
  std::cout<<"should show (1, 2, 3) and (3, 4, 5) again"<<std::endl;
  std::cout<<"Added new point? "<<p.add(3, 4, 9)<<std::endl;    
  p.show();

  return 0;
}

Compiled with g++ example.cpp -std=c++11 (using GCC 4.7.2) I get the following result:

should show (1, 2, 3)
Added new point? true
(1, 2, 3)
should show (1, 2, 3) again
Added new point? false
(1, 2, 3)
should show (1, 2, 3) and (3, 4, 5)
Added new point? true
(3, 4, 5)
(1, 2, 3)
should show (1, 2, 3) and (3, 4, 5) again
Added new point? false
(3, 4, 5)
(1, 2, 3)

Upvotes: 0

Elliott
Elliott

Reputation: 1245

As andre said, to avoiding overloading operators on your struct you can use the following map:

std::map<std::pair<int, int>, int> a_map;

Insertion:

Insert into it with a_map.insert(std::pair<std::pair<int,int>, int>(std::pair<int,int>(x, y), z));

or

std::pair<int, int> index(x, y); a_map[index] = z;

or (neatest version, borrowed from andre's answer)

a_map[make_pair(x, y)] = z;

Access:

If you're only iterating through the elements and don't particularly care about accessing values by their index very often this method is fine. If you do want to do that then you can access them like so:

std::pair<int, int> index(x, y); int z = a_map[index];

or (neatest version)

int z = a_map[make_pair(x, y)];

You could also use find() but once again, you'll need to construct a pair for it (http://www.cplusplus.com/reference/map/map/find/).

You can use the make_pair() function from <utility> (http://www.cplusplus.com/reference/utility/make_pair/) to make constructing the pairs a bit easier but if you don't want to use a map with pairs as the indexes then you might want to revert to the original plan and use an std::map<pos, int> instead.

Alternative map:

If you decide to use std::map<pos, int> just remember to overload operator< on pos to allow your map to sort its keys (since you aren't actually making any use of the sorting feature, you can return the comparison of either pos::x or pos::y arbitrarily).

Unordered map:

If you want to avoid the need to overload the operator and the sorting entirely, you can use the new C++11 unordered_map which is a more efficient container for insertions and deletions anyway. Since you're only using the uniqueness and iterator properties of map, it would be worth considering using unordered_map if you can (they have very similar interfaces and I've used them in place of map just by changing the type of my variable before!)

Upvotes: 0

andre
andre

Reputation: 7249

To fully elaborate of how to insert into std::map<std::pair<int, int>, int> xy_to_z_mapping;

std::pair<std::pair<int, int>, int> point(int x, int y, int z) {
    return std::make_pair(std::make_pair(x,y),z);
}

xy_to_z_mapping.insert(point(x,y,z));

Or,

xy_to_z_mapping.insert(std::make_pair(std::make_pair(x,y),z));

Or,

xy_to_z_mapping[std::make_pair(x,y)] = z;

Upvotes: 1

Chris Taylor
Chris Taylor

Reputation: 53699

You could use a map or if you are using a C++ 11 compiler an unordered_map to keep an index of the points.

Upvotes: 4

Related Questions