4

ArrayListの内容全体をO（1）のArrayListの別のインスタンスに移動する方法はありますか？

つまり、バッキング配列への参照のみが1つのインスタンスから別のインスタンスに渡されます（要素は1つずつコピーされません）。

例えば：

ArrayList<String> a = new ArrayList<>(Arrays.asList("A", "B", "C"));
ArrayList<String> b = new ArrayList<>();
a.moveContentsTo(b);
// 'a' is now empty, while 'b' contains everything that 'a' did before and 'a != b'
// It is desired that the 'moveContentsTo' method is O(1)

さらに良いことに、ArrayList#swapContents(ArrayList)方法はありますか？

詳細な説明とユースケース：

詳細な説明1：「a」と「b」の参照を交換してはなりません。私はtmp = a; a = b; b = tmp;解決策の種類を探していません。

詳細な説明2：操作は時間内に〜O（1）でなければなりません。

ユースケース：これは、オブジェクトが外部で作成されたリストをカプセル化する場合に役立ちます。

public class A {
    private ArrayList<String> items = new ArrayList<>();

    /**
     * This method takes the sole ownership of the contents. Whoever
     * passed the list from the outside will not be able to modify
     * contents of 'this.items' from outside the class.
     */ 
    public AnImmutableObject(ArrayList<String> items) {
        if (items != null) {
            items.moveContentsTo(this.items);
        }
    }

    /**
     * Other collections that do not provide the 'move' functionality
     * must be copied. If we just stored the reference to 'items' we
     * would break encapsulation as whoever called the constructor
     * still have write capabilities to the collection.
     */ 
    public A(Collection<String> items) {
        if (items != null) {
            this.items.addAll(items);
        }
    }

    public List<String> getItems() {
        return Collections.unmodifiableList(items);
    }
}

（速度を上げてメモリ使用量を減らすために）コピーを作成しないようにしたいことに注意してください。重要な点は、呼び出し先が（現在カプセル化されている）を変更する機能を失う必要があるということArrayListです。

4

3 に答える 3

2

std::move()私の知る限り、参照の「所有権」を（少なくともプログラマー側で）追跡するのはJavaのようではないため、必要な-のような機能が見つかるとは思えません。Java ではあまり一般的には必要ありません。ガベージ コレクションがないため、C++ ではオブジェクトの所有権を明示的に追跡する必要があると思います。

最善の策は、コンストラクターで防御的なコピーを作成し、不変オブジェクトのコピー コンストラクターに依存してスペースを節約することだと思います。

public class AnImmutableObject {

    private final List<String> items;

    /**
     * Creates a new immutable object with the given list of items.
     * Always deep copy from an outside source, because we can't know if the
     * calling code will modify that collection later.
     */ 
    public AnImmutableObject(Collection<String> items) {
        // It's a constructor. We know items needs to be set.
        // We are creating a new array list, using its constructor which deep
        // copies the collection, and immediately wrapping it to make it truly
        // immutable. We are guaranteed that no one will hold a reference to the
        // mutable view of the new ArrayList.
        this.items = Collections.unmodifiableList(new ArrayList<String>(items));
    }

    /**
     * Creates a new immutable object with the same items as another.
     * Copying the reference here is completely safe because we
     * enforce the immutability of the items array.
     */ 
    public AnImmutableObject(AnImmutableObject source) {
        items = source.items;
    }

    public List<String> getItems() {
        return items;
    }
}

この時点で、独自の不変オブジェクト間で O(1) で「配列を渡す」(実際に共有する) ことができます。

ImmutableObject a = new ImmutableObject(Arrays.asList("A", "B", "C")); // O(n)
ImmutableObject b = new ImmutableObject(a); // O(1)

うまくいけば、このようなものがあなたの目的に合うでしょう。

もう 1 つの方法は、 GuavaのImmutableListを使用することです。これらは不変であるためImmutableList、コンストラクター内の への参照を安全にコピーできます。

主なアプローチは、リストの所有権を取得するのではなく、リストへの参照を安全にコピーできるようにすることです。

于 2012-04-05T04:55:18.283 に答える
2

@Lirikの答えは素晴らしい+1です。ただし、実際の を探している場合は、次のArrayList#swapContents(ArrayList)方法で実行できます。

public static void swapContents(ArrayList<String> listA, ArrayList<String> listB)
{
    List<String> temp = new ArrayList<String>(listA);
    listA.clear();
    listA.addAll(listB);
    listB.clear();
    listB.addAll(temp);
}
于 2012-04-05T04:08:23.797 に答える
2

これはそれを行う必要があります：

ArrayList<String> a = new ArrayList<>(Arrays.asList("A", "B", "C"));
ArrayList<String> b = a;
a = new ArrayList<>();

概念的に言えば、a現在は空で、以前にb含まれていたものが含まれてaいます。単一の割り当てがあり、データのコピーはありませんでした。これは、実行できる最速のものです。それはあなたの要件を満たしていますか、それとも実際にaは、指定された配列が空になることを除いて、同じ配列を参照したいですか?

アップデート

C++ では、移動操作の時間の複雑さも O(1) だとは思いません。また、「Java のクラスは参照セマンティクスを使用するため、これらの言語にはオブジェクトの暗黙的なコピーが存在することはありません。ムーブ セマンティクスが解決する問題は、Java には存在せず、存在したこともありません。」 (FredOverflow による回答を参照してください。C++ 右辺値参照と移動セマンティクス)

バッキング配列への参照のみが一方から他方に渡されるように (つまり、要素が 1 つずつコピーされないように)、ArrayList の内容全体を別の ArrayList に移動する方法はありますか。

上記のステートメントを考えると、 Java で配列から配列に何かをコピーすると、両方の配列が同じデータを参照しaます。bC++ で移動セマンティクスを使用して行うことは、そのようなコピーを作成するために作成する必要がある一時オブジェクトを保存することだけです。

X foo();
X x;
// perhaps use x in various ways
x = foo();

最後のものは次のことを行います：

destructs the resource held by x,
clones the resource from the temporary returned by foo,
destructs the temporary and thereby releases its resource.

移動セマンティクスは次のことを行います。

swap resource pointers (handles) between x and the temporary,
temporary's destructor destruct x's original resource.

1 つの destruct を保存しますが、C++ でのみ... 上記の問題は Java には存在しません! 移動セマンティクスの詳細については、次の記事を参照してください: http://thbecker.net/articles/rvalue_references/section_02.html

于 2012-04-05T03:56:30.357 に答える