Cấu trúc dữ liệu hiệu quả để chèn

Question

Tôi đang tìm cấu trúc dữ liệu (giống mảng) cho phép chèn nhanh các giá trị vào trong cấu trúc (nhanh hơn O (N)). Cấu trúc dữ liệu phải có khả năng in ra các phần tử của nó theo cách chúng được chèn. Điều này tương tự như một cái gì đó như List.Insert() (mà là quá chậm vì nó phải thay đổi mọi phần tử trên), ngoại trừ tôi không cần truy cập hoặc xóa ngẫu nhiên. Chèn sẽ luôn nằm trong kích thước của 'mảng'. Tất cả các giá trị là duy nhất. Không cần thao tác nào khác.

Ví dụ: nếu Chèn (x, i) chèn giá trị x vào chỉ mục i (0-lập chỉ mục). Sau đó:

• Insert (1, 0) cho {1}
• Insert (3, 1) cho {1,3}
• Insert (2, 1) cho {1,2,3}
• Insert (5, 0) cho {5,1,2,3}

Và nó sẽ cần để có thể in ra {5,1,2,3} ở cuối.

Tôi đang sử dụng C++.

Answer 1

Sử dụng skip list. Một tùy chọn khác phải là tiered vector. Danh sách bỏ qua thực hiện chèn tại const O (log (n)) và giữ các số theo thứ tự. Vectơ tầng hỗ trợ chèn trong O (sqrt (n)) và một lần nữa có thể in các phần tử theo thứ tự.

EDIT: mỗi bình luận của amit tôi sẽ giải thích làm thế nào để bạn tìm thấy những yếu tố thứ k trong một danh sách bỏ qua:

Đối với mỗi yếu tố bạn có một tháp trên các liên kết đến các yếu tố tiếp theo và cho mỗi liên kết bạn biết bao nhiêu yếu tố nó nhảy qua. Vì vậy, tìm kiếm phần tử thứ k bạn bắt đầu với phần đầu của danh sách và đi xuống tháp cho đến khi bạn tìm thấy một liên kết nhảy qua không có nhiều phần tử k nữa. Bạn đi đến nút được trỏ đến bởi nút này và giảm k với số lượng phần tử bạn đã nhảy qua. Tiếp tục làm như vậy cho đến khi bạn có k = 0.

Answer 2

Bạn có cân nhắc sử dụng std::map hoặc std::vector?

Bạn có thể sử dụng số std::map với thứ hạng chèn là khóa. Và vector có chức năng thành viên reserve.

Answer 3

Trong C++ bạn chỉ có thể sử dụng bản đồ về vectơ, như vậy:

int main() { 
    map<int, vector<int> > data; 
    data[0].push_back(1); 
    data[1].push_back(3); 
    data[1].push_back(2); 
    data[0].push_back(5); 
    map<int, vector<int> >::iterator it; 
    for (it = data.begin(); it != data.end(); it++) { 
    vector<int> v = it->second; 
    for (int i = v.size() - 1; i >= 0; i--) { 
     cout << v[i] << ' '; 
    } 
    } 
    cout << '\n'; 
} 

này in:

5 1 2 3 

Cũng giống như bạn muốn, và chèn là O (log n).

Answer 4

Bạn có thể sử dụng các cặp ánh xạ (chỉ mục, thời gian chèn) std::map với giá trị, trong đó thời gian chèn là số nguyên "tự động" (trong thuật ngữ SQL).Trật tự trên các cặp nên

(i, t) < (i*, t*) 

iff

i < i* or t > t* 

Trong mã:

struct lt { 
    bool operator()(std::pair<size_t, size_t> const &x, 
        std::pair<size_t, size_t> const &y) 
    { 
     return x.first < y.first || x.second > y.second; 
    } 
}; 

typedef std::map<std::pair<size_t, size_t>, int, lt> array_like; 

void insert(array_like &a, int value, size_t i) 
{ 
    a[std::make_pair(i, a.size())] = value; 
} 

Answer 5

Về nhận xét của bạn:

List.Insert() (đó là quá chậm vì phải thay đổi mọi phần tử),

Danh sách không thay đổi giá trị của chúng, chúng lặp qua chúng để tìm vị trí bạn muốn chèn, hãy cẩn thận những gì bạn nói. Điều này có thể gây nhầm lẫn cho người mới như tôi.

Answer 6

Giải pháp được bao gồm trong GCC theo mặc định là cấu trúc dữ liệu dây. Đây là số documentation. Thông thường, dây thừng đến với tâm trí khi làm việc với các chuỗi ký tự dài. Ở đây chúng tôi có int s thay vì ký tự, nhưng nó hoạt động giống nhau. Chỉ cần sử dụng int làm thông số mẫu. (Cũng có thể là pair s, v.v.)

Đây là description of rope on Wikipedia. Về cơ bản, đó là cây nhị phân duy trì số lượng phần tử trong các subtrees trái và phải (hoặc thông tin tương đương, được gọi là thống kê đơn đặt hàng) và các số này được cập nhật một cách thích hợp khi các phụ đề được xoay khi các phần tử được chèn vào và loại bỏ. Điều này cho phép các hoạt động O (lg n).