0

我正在寻找一种用于我正在开发的程序的数据结构。它跟踪 x 和 y 值，并且仅当 x,y 位置还不是我的数组时才需要设置 Z。

我尝试使用动态数组，随着列表的增长，迭代数据变得非常非常慢。这是我的结构的样子。

结构 pos { int x; 整数y; }

相应的值是一个整数，仅当 x,y 对不存在时才设置。

编辑：我一直在尝试使用地图，但不知道如何使用 x, y 坐标有索引，即如何 .insert(pos, zValue);

4

4 回答 4

4

您可以使用地图，或者如果您使用的是 C++ 11 编译器，则可以使用 unordered_map 来保留点的索引。

于 2013-04-25T21:13:22.300 回答
1

详细说明如何插入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));

或者，

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

或者，

xy_to_z_mapping[std::make_pair(x,y)] = z;
于 2013-04-25T21:47:57.673 回答
0

正如 andre 所说，为了避免在结构上重载运算符，您可以使用以下映射：

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

插入：

插入其中a_map.insert(std::pair<std::pair<int,int>, int>(std::pair<int,int>(x, y), z));

或者

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

或（最新版本，借自安德烈的回答）

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

使用权：

如果您只是遍历元素并且不特别关心经常通过索引访问值，则此方法很好。如果您确实想这样做，那么您可以像这样访问它们：

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

或（最新版本）

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

您也可以使用find()，但再一次，您需要pair为它构建一个（http://www.cplusplus.com/reference/map/map/find/）。

您可以使用（http://www.cplusplus.com/reference/utility/make_pair/make_pair() ）中的函数来使构建对更容易一些，但是如果您不想使用带有对的地图作为索引，那么您可能想要恢复到原始计划并改用。<utility>std::map<pos, int>

替代地图：

如果您决定使用std::map<pos, int>只记得重载operator<以pos允许您map对其键进行排序（因为您实际上并没有使用排序功能，您可以返回任一pos::x或pos::y任意的比较）。

无序地图：

如果你想完全避免重载运算符和排序，你可以使用新的 C++11 unordered_map，它是一个更有效的插入和删除容器。由于您仅使用 的唯一性和迭代器属性map，因此值得考虑使用unordered_map（它们具有非常相似的接口，我之前已经使用它们来代替map更改变量的类型！）

于 2013-04-25T21:47:48.123 回答
0

我有点认为正确的数据结构似乎是一个集合，而不是一个映射。原因是如果你在处理Points 或Positions，数据类型包含三个坐标（x、y和z）。

现在，您似乎只有在另一个具有相同- 和 -坐标的点尚未更新时才对更新 aPosition的- 坐标感兴趣。zxy

我使用无序集创建了以下实现。请注意，哈希器和比较器仅使用xand 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;
}

编译g++ example.cpp -std=c++11（使用 GCC 4.7.2）我得到以下结果：

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)
于 2013-04-25T22:55:31.140 回答