C++ - 可以跟蹤結構（x和y）和值避免重複的數據結構/算法

Question

我正在尋找一個數據結構以用於我正在處理的程序。它跟蹤x和y值，只有當x，y位置不是我的數組時，才需要設置Z值。

我嘗試使用動態數組，並隨着列表的增長，迭代數據變得非常慢。這是我的結構看起來像。

struct pos int x; int y; }

對應的值是一個整數，只有在x，y對不存在時纔會設置。編輯：我一直在試圖使用一個地圖，但無法弄清楚如何使用x，y座標有索引，即如何.insert（pos，zValue）;

Answer 1

您可以使用地圖，或者如果您正在使用C++ 11編譯器unordered_map來保留點的索引。

Answer 2

安德烈說，爲了避免對你的結構運算符重載，你可以使用下面的地圖：

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/）。

可以使用make_pair()功能從<utility>（http://www.cplusplus.com/reference/utility/make_pair/），使構建對容易一點，但如果你不想使用地圖對爲指標，那麼你可能要恢復到原來的計劃，改爲使用std::map<pos, int>。

另類地圖：

如果你決定使用std::map<pos, int>只記得超負荷posoperator<，讓您的map其鍵排序（因爲你實際上並沒有做任何使用排序功能，你可以任意返回pos::x或pos::y的比較結果）。

無序地圖：

如果你想避免需要使用操作符重載和完全排序，您可以使用新的C++ 11 unordered_map這是插入和缺失更高效的集裝箱反正。由於您只使用map的唯一性和迭代器屬性，因此如果可以的話，使用unordered_map是值得考慮的（它們具有非常相似的接口，並且我只是在更改變量類型之前使用它們代替map！ ）

Answer 3

要充分精細如何插入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; 

Answer 4

我有些認爲正確的數據結構似乎是一個集合，而不是一個映射。原因是，如果您正在處理Point s或Position s，則數據類型包含三個座標（x,y和z）。

現在，你似乎是有意更新僅在具有相同x另一點Position的z - 協調 - 和y - 協調尚未更新。

我使用無序集創建了以下實現。請注意，散列器和比較器僅使用x和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)