Trường hợp đặc biệt: Hoán giá trị của hai biến
(. Đối với các giải pháp chung, xem dưới đây)
Để trao đổi hai giá trị biến trong C++, bạn nên luôn luôn sử dụng swap
:
using std::swap;
swap(x, y); // Do NOT say: std::swap(x, y) -- Read about Koenig lookup!
Đừng bận tâm cách thức nó sẽ làm điều đó; nó sẽ làm điều đó rất nhanh. Việc thực hiện thư viện chuẩn C++ sẽ làm hết sức mình để tối ưu hóa điều này thành một hướng dẫn đơn nếu bộ xử lý hỗ trợ nó (nhưng tiêu chuẩn không cho biết việc triển khai thực hiện). Đối với các biến chỉ đăng ký, ví dụ như lệnh x86 xchg
sẽ thực hiện nhanh nhất có thể. Đừng cố gắng tinh chỉnh nó với một số "ba hoạt động xor", nó sẽ không nhanh hơn. Nếu bạn không may mắn, nó sẽ không được tối ưu hóa cho một cái gì đó như xchg
.
Thao tác chung swap
trong C++ 03 giới thiệu một biến tạm thời và thực hiện ba công trình sao chép. Trong C++ 11 có di chuyển-ngữ nghĩa và các đối tượng được thay di chuyển hơn sao chép.Đối với loại của riêng bạn, giả sử một số cấu trúc dữ liệu mà giữ chỉ là một con trỏ đến dữ liệu thực tế, bạn nên tối ưu hóa thủ tục này để làm cho nó thực hiện trong thời gian liên tục:
Trong C++ 03, bạn có thể chuyên std::swap
hoặc thực hiện chức năng swap
của riêng bạn trong không gian tên (see the two top answers on this question) để tối ưu hóa trao đổi: Chỉ cần trao đổi từng thành viên trong lớp của bạn để trao đổi dữ liệu của họ. Ví dụ về cấu trúc dữ liệu chỉ giữ một con trỏ, chỉ cần hoán đổi các con trỏ.
Trong C++ 11, có mới thái ngữ nghĩa, cho phép bạn thực hiện phong trào của các dữ liệu từ một đến một đối tượng, trong đó sẽ dẫn đến một hành vi rất giống nhau. (Di chuyển ngữ nghĩa đã được giới thiệu cho các vấn đề chung chung hơn như trao đổi hai đối tượng: Nếu một đối tượng không cần thiết nữa, nhưng một đối tượng khác phải là "bản sao" đầu tiên, nó có thể đơn giản được di chuyển.) Đọc về ngữ nghĩa di chuyển và di chuyển constructor để biết chi tiết.
Đối cả C++ 03 và C++ 11 có một cách khác: Bạn có thể thực hiện dữ liệu ngầm chia sẻ và copy-on-viết cho các lớp học nặng như cấu trúc dữ liệu. Trong ví dụ trên, nơi cấu trúc dữ liệu của bạn giữ con trỏ đến dữ liệu thực tế, hãy thực hiện đếm tham chiếu. Khi sao chép cấu trúc dữ liệu, chỉ cần tăng bộ đếm tham chiếu một. Khi sửa đổi dữ liệu, hãy chắc chắn rằng nó không được chia sẻ (ref count = 1), nếu không thì "tách" nó bằng cách sao chép nó chỉ sau đó. Điều này dẫn đến hoạt động sao chép và hoán đổi không đổi.
trường hợp chung: Nhiều biểu thức tùy ý
Đối với báo cáo khác có không đầu vào/đầu ra phụ thuộc, như (a, b) = (x, y)
, chỉ cần viết chúng "nguyên trạng", và nó sẽ chạy ít nhất là hoàn toàn pipelined vì họ không có bất kỳ sự phụ thuộc:
a = x;
b = y;
Nếu họ là phụ thuộc vào đầu vào/đầu ra, như ví dụ của bạn trong bản chỉnh sửa, bạn có thể chia nhỏ và giới thiệu thời gian. Bạn sẽ không làm cho mình một ưu tiên bằng cách cố gắng giải quyết như vậy với một số thủ thuật biểu hiện ưa thích như xor-ing. Trình biên dịch biết rất nhiều thủ thuật cho trình biên dịch (như xchg
), bạn chỉ biết các thủ thuật để diễn tả như vậy trong đồng bằng C++ (như xor).
Trong C++ 11, có std::tuple
và std::tie
cho phép bạn chỉ định nhiều biểu thức mà không giới thiệu thời gian (chúng sẽ được giới thiệu ở hậu trường để giữ các giá trị được lưu trữ trong bộ nhớ và cố gắng tối ưu hóa chúng một cách đầy đủ hoặc tại nhất chỉ sử dụng đăng ký để giữ họ nếu có thể):
using std::tie;
using std::make_tuple;
tie(ones, twos) = make_tuple((ones^n)^~twos, (ones & n) | (twos & ~n));
Lưu ý rằng các loại quyền phía bên tay cặp/tuple có để phù hợp với các giá trị mục tiêu ở phía bên tay trái như chuyển đổi là không tiềm ẩn ở đây.Nếu bạn gặp phải vấn đề này, thực hiện một static_cast
ở phía bên tay phải, nói std::make_tuple
các loại rõ ràng hoặc chỉ sử dụng các nhà xây dựng cho std::tuple
đòi hỏi loại rõ ràng, như:
using std::tie;
using std::tuple;
tie(ones, twos) = tuple<int,int>((ones^n)^~twos, (ones & n) | (twos & ~n));
'std :: swap (x, y); 'là cách ưa thích. – chris
@chris: Trên thực tế, 'std :: swap (x, y)' là *** sai *** cách. – Mehrdad
@Mehrdad, Good point. Sự nhấn mạnh của tôi là sử dụng phiên bản premade thay vì luôn luôn cố gắng để nội tuyến nó, nhưng đó là một vấn đề hợp lệ. – chris