Chọn một container STL với tính độc đáo và đó giữ chèn lệnh

Question

tôi không thể quyết định STL container để sử dụng trong các trường hợp sau đây:

1. Tôi muốn giữ gìn trật tự chèn trong những yếu tố
2. Các các phần tử trong vùng chứa phải là duy nhất.

Có sẵn bất kỳ vật chứa có sẵn nào không? Tôi không muốn sử dụng một vector và sau đó thực hiện một std::find trước khi thực hiện một push_back mỗi lần.

Answer 1

Boost MultiIndex sẽ có thể thực hiện chính xác những gì bạn muốn - bạn chỉ có thể sử dụng một chỉ mục được sắp xếp để nhận yêu cầu "đặt hàng bằng thứ tự chèn" và chỉ mục hashed_unique hoặc ordered_unique để nhận yêu cầu duy nhất.

Answer 2

Có thể có cách xây dựng tốt để thực hiện việc này, nhưng một cách khá đơn giản là sử dụng cả hash_map và danh sách. Kiểm tra hash_map trước mỗi lần chèn, sau đó chèn vào cả hai. Bạn sẽ muốn đóng gói điều này trong một lớp học, có lẽ.

Answer 3

Triển khai lớp trình bao bọc trên vùng chứa bạn chọn (ví dụ: danh sách, vectơ, deque) và viết lại phương thức chèn/push_back để kiểm tra xem phần tử được chèn có duy nhất không trước khi chèn phần tử.

Thật không may, tôi không biết bất kỳ vùng chứa STL nào phù hợp với tiêu chí của bạn.

Answer 4

Không có thư viện thư viện chuẩn nào cung cấp cho bạn những gì bạn muốn trực tiếp. Tôi sẽ bắt đầu với một std :: vector và viết một chức năng miễn phí để làm chèn mà không tìm và push_back cho bạn. Nếu điều này đủ, không đi xa hơn. Nếu bạn gặp vấn đề về hiệu suất, hãy nghĩ về một giải pháp phức tạp hơn.

Answer 5

Như những người khác đã nói, không có thùng chứa STL duy nhất nào có thể thực hiện việc này. Tôi thích câu trả lời của Neil Butterworth. Một tùy chọn khác là sử dụng cả tập hợp và vectơ. Khi bạn đi đến chèn, hãy kiểm tra xem liệu phần tử có nằm trong tập hợp hay không. Nếu có, bạn không thể chèn vì điều đó sẽ vi phạm yêu cầu duy nhất của bạn. Nếu không, hãy thêm nó vào bộ và sau đó chèn nó vào vectơ. Điều này rất dễ thực hiện và có thể được bao bọc thành một lớp duy nhất. Sự cân bằng được tăng chi phí bộ nhớ. Nhưng bạn giao dịch để tăng thời gian tính toán bằng cách tự tìm kiếm trên một véc tơ đơn. Tất cả phụ thuộc vào lượng dữ liệu bạn đang làm việc trong miền vấn đề và thời gian và hạn chế bộ nhớ của bạn (nếu có).

Answer 6

Nếu bạn đã cài đặt tăng cường, tôi thích tùy chọn đó. Nếu không, tại sao không chỉ sử dụng danh sách hoặc vectơ và thêm séc (find(k) == std::npos) khi chèn? Tôi cho rằng nó có thể trở nên chậm chạp trong một danh sách thực sự lớn, nhưng trong hầu hết các trường hợp, nó sẽ hoạt động tốt.

Answer 7

Bạn có thể làm điều này:

• Tạo một wrapper xung quanh lớp yếu tố của bạn với hai thành viên: yếu tố của bạn, và một chỉ mục. Hãy gọi nó là 'InsertedElement'. Chỉ mục sẽ là thứ tự chèn.

• Xác định toán tử so sánh cho lớp này, chỉ tính đến phần tử của bạn, nhưng không tính đến chỉ mục. Điều này sẽ đảm bảo tính duy nhất của các phần tử, trong khi ghi nhớ thứ tự chèn của chúng.

• Gói std :: set và bộ đếm chèn vào một lớp khác.Sau đó, khi bạn muốn chèn một phần tử mới, hãy:

• Nó đã tồn tại, không có gì để làm.
• Nó không: chèn nó trong bản đồ trong khi cho nó chỉ số tối đa hiện tại + 1.

Cái gì như:

class CMagicContainer 
{ 
    public: 
    std::set<InsertedElement> collection; 
    int indexGenerator; 

    ... 
}; 

Answer 8

Vâng, tôi đã từng có một tình huống tương tự. Một điều mà tôi nghĩ đến là 'tôi có thể sử dụng đa khóa' không? Tôi googled trong một thời gian, và tìm thấy một mẫu bằng cách sử dụng std :: set. Vì vậy, nếu bạn không có quyền truy cập để tăng (tôi khuyên bạn nên nó, không có điểm tái phát minh ra bánh xe); bạn có thể thử một cái gì đó giống như ví dụ dưới đây. Tôi nghĩ bạn có thể sử dụng khóa phụ làm vị trí chèn (tự động tăng). Từ ví dụ mà tôi tìm thấy trên internet; tôi đã điều chỉnh nó theo nhu cầu của tôi. Đây là một phiên bản sửa đổi của cùng một.

Cavaet: Nó đang sử dụng macro. Tôi biết họ là ác nói chung, nhưng việc sử dụng này là o.k. tôi đoán.

#include <set> 
#include <functional> 
#include <iostream> 
#include <algorithm> 
#include <iterator> 
#include <string> 

#define MULTIKEYDEF(NAME,TYPE) \ 
    inline TYPE const & NAME() const { return d_##NAME; } \ 
    inline void NAME(TYPE const & t) { d_##NAME = t; } \ 
    TYPE d_##NAME; \ 
class T##NAME \ 
    : public std::unary_function<Tmultikey*,bool> { \ 
private: \ 
    TYPE d_compare; \ 
public: \ 
    T##NAME(TYPE t) : d_compare(t) {} \ 
    T##NAME(T##NAME const & self) \ 
    : d_compare(self.d_compare) {} \ 
    bool operator()(Tmultikey * mk) { \ 
    return d_compare == mk->##NAME(); \ 
    } \ 
    inline TYPE const& name() const { return d_compare; } \ 
    } 

class Tmultikey { 
public: 
    // Actual keys 
    // Can be accessed through d_primary and d_secondary, 
    // or primary() and secondary() 
    MULTIKEYDEF(primary , std::string); 
    MULTIKEYDEF(secondary, unsigned int); 
    // Mandatory 
    bool operator < (Tmultikey const& mk) const { 
     if(primary() < mk.primary()) return true; 
     else if(primary() == mk.primary()) { 
      return secondary() < mk.secondary(); 
     } 
     return false; 
    } 
    // Constructor 
    Tmultikey(std::string p, unsigned int s) 
     : d_primary(p), d_secondary(s) {} 

    // Eraser for std::set 
    template<typename Compare> 
     static void erase(std::set<Tmultikey> & c, Compare op) { 
      typename std::set<Tmultikey>::iterator pos = c.begin(); 
      while(pos != c.end()) { 
       if(op(&(*pos))) { 
        c.erase(pos++); 
       } else ++pos; 
      } 
     } 
     // Eraser for std::set 
     template<typename Compare> 
     static std::set<Tmultikey>::iterator find_ex(std::set<Tmultikey> & c, Compare op) { 
     typename std::set<Tmultikey>::iterator pos = c.begin(); 
     while(pos != c.end()) { 
      if(op(&(*pos))) { 
       break; 
      } else ++pos; 
     } 
     return pos; 
     } 
}; 

int main(int argc, char* argv[]) 
{ 
    std::set<Tmultikey> mkset; 

    mkset.insert(Tmultikey("1",5)); 
    mkset.insert(Tmultikey("6",4)); 
    mkset.insert(Tmultikey("3",7)); 
    mkset.insert(Tmultikey("1",6)); 

    std::set<Tmultikey>::iterator bg = mkset.begin(); 
    for (;bg != mkset.end(); ++bg) 
    { 
     std::cout<<(*bg).primary()<<std::endl; 
    } 

    Tmultikey::erase(mkset,Tmultikey::Tsecondary(4)); 
    //Tmultikey::erase(mkset,Tmultikey::Tprimary("1")); 

    std::cout<<"After erase ....\n"; 
    bg = mkset.begin(); 
    for (;bg != mkset.end(); ++bg) 
    { 
     std::cout<<(*bg).primary()<<std::endl; 
    } 
    bg = mkset.find(Tmultikey("3",7)); 
    if (bg != mkset.end()) 
    { 
     std::cout<<"Absolute Find:"<<(*bg).primary()<<" "<<(*bg).secondary()<<std::endl; 
    } 
    //bg = Tmultikey::find_ex(mkset,Tmultikey::Tprimary("1")); 
    bg = Tmultikey::find_ex(mkset,Tmultikey::Tsecondary(5)); 
    if (bg != mkset.end()) 
    { 
     std::cout<<"Partial Find:"<<(*bg).primary()<<" "<<(*bg).secondary()<<std::endl; 
    } 
    else { 
     std::cout<<"Partial Find: FAILED\n"; 
    } 

    return 0; 
} 

HTH,