표준 라이브러리: 컨테이너
표준 라이브러리: 컨테이너 (Standard library: Containers)
이전 장들에서 특정 데이터 타입의 여러 객체를 묶는 표준 방법으로 배열을 사용했어요. 많은 경우 배열이 그 객체들을 다루기에 충분해요. 하지만 더 많은 유연성과 고급 연산이 필요한 상황도 있어요. 그런 경우를 위해 Ada는 표준 라이브러리에 컨테이너(container) — 예를 들어 벡터나 집합 — 지원을 제공해요.
여기서는 컨테이너에 대한 소개를 할게요. Ada에서 사용 가능한 모든 컨테이너 목록은 부록 B를 참조하세요.
본문
벡터 (Vectors)
다음 절들에서 벡터의 일반적인 개요를 다룰게요. 인스턴스화, 초기화, 벡터 요소와 벡터에 대한 연산을 포함해요.
인스턴스화 (Instantiation)
벡터 V의 인스턴스화와 선언을 보여주는 예시예요:
with Ada.Containers.Vectors;
procedure Show_Vector_Inst is
package Integer_Vectors is new
Ada.Containers.Vectors
(Index_Type => Natural,
Element_Type => Integer);
V : Integer_Vectors.Vector;
begin
null;
end Show_Vector_Inst;
컨테이너는 제네릭 패키지에 기반하므로, 특정 타입의 배열을 선언하듯 단순히 벡터를 선언할 수는 없어요:
A : array (1 .. 10) of Integer;
대신 먼저 그 패키지 중 하나를 인스턴스화해야 해요. 컨테이너 패키지(이 경우 Ada.Containers.Vectors)를 with하고, 원하는 타입에 대한 제네릭 패키지의 인스턴스를 만들기 위해 인스턴스화해요. 그래야만 인스턴스화된 패키지의 타입을 사용해 벡터를 선언할 수 있어요. 이 인스턴스화는 표준 라이브러리의 어떤 컨테이너 타입에 대해서도 필요해요.
Integer_Vectors 인스턴스화에서 Element_Type으로 지정해 벡터가 Integer 타입의 요소를 담고 있음을 나타내요. Index_Type을 Natural로 설정하면 허용 범위가 모든 자연수를 포함하도록 지정하는 것이에요. 원한다면 더 제한적인 범위를 사용할 수도 있었어요.
초기화 (Initialization)
벡터를 초기화하는 한 가지 방법은 요소의 연결(concatenation)에서 얻는 것이에요. 다음 예시처럼 & 연산자를 사용해요:
with Ada.Containers; use Ada.Containers;
with Ada.Containers.Vectors;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Vector_Init is
package Integer_Vectors is new
Ada.Containers.Vectors
(Index_Type => Natural,
Element_Type => Integer);
use Integer_Vectors;
V : Vector := 20 & 10 & 0 & 13;
begin
Put_Line ("Vector has "
& Count_Type'Image (V.Length)
& " elements");
end Show_Vector_Init;
use Integer_Vectors를 지정해 인스턴스화된 패키지의 타입과 연산에 직접 접근할 수 있게 해요. 또한 이 예시는 벡터에 대한 또 다른 연산인 Length를 소개하는데, 이는 벡터의 요소 수를 검색해요. Vector가 태그 타입이라 점 표기법을 사용할 수 있어서 V.Length 또는 Length (V) 중 하나로 쓸 수 있어요.
요소 추가: Append와 Prepend (Appending and prepending elements)
Prepend와 Append 연산으로 벡터에 요소를 추가해요. 이름이 시사하듯 이 연산들은 각각 벡터의 시작이나 끝에 요소를 추가해요. 예를 들어:
with Ada.Containers; use Ada.Containers;
with Ada.Containers.Vectors;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Vector_Append is
package Integer_Vectors is new
Ada.Containers.Vectors
(Index_Type => Natural,
Element_Type => Integer);
use Integer_Vectors;
V : Vector;
begin
Put_Line ("Appending some elements "
& "to the vector...");
V.Append (20);
V.Append (10);
V.Append (0);
V.Append (13);
Put_Line ("Finished appending.");
Put_Line ("Prepending some elements"
& "to the vector...");
V.Prepend (30);
V.Prepend (40);
V.Prepend (100);
Put_Line ("Finished prepending.");
Put_Line ("Vector has "
& Count_Type'Image (V.Length)
& " elements");
end Show_Vector_Append;
이 예시는 다음 순서로 벡터에 요소를 넣어요: (100, 40, 30, 20, 10, 0, 13).
Reference Manual은 최악의 경우 복잡도가 다음과 같아야 한다고 지정해요:
Append연산: O(log N)Prepend연산: O(N log N)
첫·마지막 요소 접근 (Accessing first and last elements)
First_Element와 Last_Element 함수로 벡터의 첫·마지막 요소에 접근해요. 예를 들어:
with Ada.Containers; use Ada.Containers;
with Ada.Containers.Vectors;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Vector_First_Last_Element is
package Integer_Vectors is new
Ada.Containers.Vectors
(Index_Type => Natural,
Element_Type => Integer);
use Integer_Vectors;
function Img (I : Integer) return String
renames Integer'Image;
function Img (I : Count_Type) return String
renames Count_Type'Image;
V : Vector := 20 & 10 & 0 & 13;
begin
Put_Line ("Vector has "
& Img (V.Length)
& " elements");
-- V.First_Element로 첫 요소 검색
Put_Line ("First element is "
& Img (V.First_Element));
-- V.Last_Element로 마지막 요소 검색
Put_Line ("Last element is "
& Img (V.Last_Element));
end Show_Vector_First_Last_Element;
Swap 프로시저를 호출해 요소를 교환할 수 있고, First와 Last를 호출해 벡터의 첫·마지막 요소에 대한 참조(커서(cursor))를 얻을 수 있어요. 커서를 사용하면 컨테이너를 순회하며 개별 요소를 처리할 수 있어요.
이 연산들로 벡터의 첫·마지막 요소를 교환하는 코드를 작성할 수 있어요:
with Ada.Containers; use Ada.Containers;
with Ada.Containers.Vectors;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Vector_First_Last_Element is
package Integer_Vectors is new
Ada.Containers.Vectors
(Index_Type => Natural,
Element_Type => Integer);
use Integer_Vectors;
function Img (I : Integer) return String
renames Integer'Image;
V : Vector := 20 & 10 & 0 & 13;
begin
-- V.First와 V.Last로 첫·마지막 요소의
-- 커서를 검색하고, V.Swap으로 요소 교환
V.Swap (V.First, V.Last);
Put_Line ("First element is now "
& Img (V.First_Element));
Put_Line ("Last element is now "
& Img (V.Last_Element));
end Show_Vector_First_Last_Element;
순회 (Iterating)
컨테이너를 순회하는 가장 쉬운 방법은 for E of Our_Container 루프를 사용하는 것이에요. 이는 현재 위치의 요소에 대한 참조(E)를 제공해요. 그러면 E를 직접 사용할 수 있어요. 예를 들어:
with Ada.Containers.Vectors;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Vector_Iteration is
package Integer_Vectors is new
Ada.Containers.Vectors
(Index_Type => Natural,
Element_Type => Integer);
use Integer_Vectors;
function Img (I : Integer) return String
renames Integer'Image;
V : Vector := 20 & 10 & 0 & 13;
begin
Put_Line ("Vector elements are: ");
--
-- for ... of 루프로 순회:
--
for E of V loop
Put_Line ("- " & Img (E));
end loop;
end Show_Vector_Iteration;
이 코드는 벡터 V의 각 요소를 표시해요.
참조가 주어지므로 요소의 값을 표시할 뿐 아니라 수정할 수도 있어요. 예를 들어 벡터 V의 각 요소에 1을 더하는 루프를 쉽게 작성할 수 있어요:
for E of V loop
E := E + 1;
end loop;
인덱스를 사용해 벡터 요소에 접근할 수도 있어요. 형식은 배열 요소를 순회하는 루프와 유사해요: for I in <range> 루프를 사용해요. 범위는 V.First_Index와 V.Last_Index로 제공돼요. 현재 요소는 배열 인덱스처럼 사용해 접근할 수 있어요: V (I). 예를 들어:
with Ada.Containers.Vectors;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Vector_Index_Iteration is
package Integer_Vectors is new
Ada.Containers.Vectors
(Index_Type => Natural,
Element_Type => Integer);
use Integer_Vectors;
V : Vector := 20 & 10 & 0 & 13;
begin
Put_Line ("Vector elements are: ");
--
-- "for I in ..." 루프에서 인덱스로 순회:
--
for I in V.First_Index .. V.Last_Index loop
-- 현재 인덱스 I 표시
Put ("- ["
& Extended_Index'Image (I)
& "] ");
Put (Integer'Image (V (I)));
-- 현재 인덱스 I의 요소를 검색하는
-- V.Element (I) 함수도 사용 가능
New_Line;
end loop;
end Show_Vector_Index_Iteration;
여기서 벡터 요소를 표시하는 것 외에도 배열 인덱스에서처럼 각 인덱스 I도 표시해요. 또한 짧은 형식 V (I)나 긴 형식 V.Element (I)으로 요소에 접근할 수 있지만, V.I로는 불가능해요.
앞 절에서 언급했듯 커서를 사용해 컨테이너를 순회할 수 있어요. 이를 위해 벡터의 각 위치에 대한 커서를 검색하는 Iterate 함수를 사용해요. 해당 루프의 형식은 for C in V.Iterate loop이에요. 인덱스를 사용한 이전 예시처럼, 커서를 배열 인덱스처럼 사용해(V (C)) 현재 요소에 접근할 수 있어요. 예를 들어:
with Ada.Containers.Vectors;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Vector_Cursor_Iteration is
package Integer_Vectors is new
Ada.Containers.Vectors
(Index_Type => Natural,
Element_Type => Integer);
use Integer_Vectors;
V : Vector := 20 & 10 & 0 & 13;
begin
Put_Line ("Vector elements are: ");
--
-- 커서로 루프에서 순회:
--
for C in V.Iterate loop
-- 커서 위치의 인덱스를 검색하는
-- To_Index 함수 사용
Put ("- ["
& Extended_Index'Image (To_Index (C))
& "] ");
Put (Integer'Image (V (C)));
-- 커서 위치의 벡터 요소를 검색하는
-- Element (C) 사용 가능
New_Line;
end loop;
-- 대안으로 while-루프로 순회할 수도 있음:
--
-- declare
-- C : Cursor := V.First;
-- begin
-- while C /= No_Element loop
-- some processing here...
--
-- C := Next (C);
-- end loop;
-- end;
end Show_Vector_Cursor_Iteration;
루프에서 V (C)로 요소에 접근하는 대신 긴 형식 Element (C)를 사용할 수도 있었어요. 이 예시에서는 To_Index 함수를 사용해 현재 커서에 해당하는 인덱스를 검색해요.
루프 뒤의 주석에 나와 있듯이 while ... loop을 사용해 벡터를 순회할 수도 있어요. 이 경우 첫 요소의 커서(V.First 호출로 검색)로 시작한 다음 Next (C)를 호출해 후속 요소의 커서를 검색해요. 커서가 벡터 끝에 도달하면 Next (C)는 No_Element를 반환해요.
참조를 사용해 요소를 직접 수정할 수 있어요. 인덱스와 커서를 모두 사용할 때는 다음과 같아요:
-- 인덱스로 벡터 요소 수정
for I in V.First_Index .. V.Last_Index loop
V (I) := V (I) + 1;
end loop;
-- 커서로 벡터 요소 수정
for C in V.Iterate loop
V (C) := V (C) + 1;
end loop;
Reference Manual은 요소 접근의 최악 경우 복잡도가 O(log N)이어야 한다고 요구해요.
벡터 요소를 수정하는 또 다른 방법은 처리 프로시저(process procedure) 를 사용하는 것이에요. 이 프로시저는 개별 요소를 받아 그에 대한 처리를 해요. Update_Element를 호출하면서 커서와 처리 프로시저에 대한 접근(access)을 모두 전달할 수 있어요. 예를 들어:
with Ada.Containers.Vectors;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Vector_Update is
package Integer_Vectors is new
Ada.Containers.Vectors
(Index_Type => Natural,
Element_Type => Integer);
use Integer_Vectors;
procedure Add_One (I : in out Integer) is
begin
I := I + 1;
end Add_One;
V : Vector := 20 & 10 & 12;
begin
--
-- V.Update_Element로 요소 처리
--
for C in V.Iterate loop
V.Update_Element (C, Add_One'Access);
end loop;
end Show_Vector_Update;
요소 찾기와 변경 (Finding and changing elements)
벡터에서 특정 요소의 인덱스를 검색해 위치를 찾을 수 있어요. Find_Index는 찾고 있는 값과 일치하는 첫 요소의 인덱스를 검색해요. 또는 Find를 사용해 그 요소를 참조하는 커서를 검색할 수 있어요. 예를 들어:
with Ada.Containers.Vectors;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Find_Vector_Element is
package Integer_Vectors is new
Ada.Containers.Vectors
(Index_Type => Natural,
Element_Type => Integer);
use Integer_Vectors;
V : Vector := 20 & 10 & 0 & 13;
Idx : Extended_Index;
C : Cursor;
begin
-- Find_Index로 값 10을 가진 요소의
-- 인덱스 검색
Idx := V.Find_Index (10);
Put_Line ("Index of element with value 10 is "
& Extended_Index'Image (Idx));
-- Find로 값 13을 가진 요소의
-- 커서 검색
C := V.Find (13);
Idx := To_Index (C);
Put_Line ("Index of element with value 13 is "
& Extended_Index'Image (Idx));
end Show_Find_Vector_Element;
앞 절에서 봤듯이 인덱스나 커서를 사용해 벡터 요소에 직접 접근할 수 있어요. 하지만 잘못된 인덱스나 커서로 요소에 접근하려 하면 예외가 발생하므로, 요소에 접근하기 전에 인덱스나 커서가 유효한지 확인해야 해요. 예시에서 Find_Index나 Find가 벡터에서 요소를 찾지 못했을 수 있어요. 인덱스를 No_Index와, 커서를 No_Element와 비교해 이 가능성을 확인해요. 예를 들어:
-- 인덱스로 벡터 요소 수정
if Idx /= No_Index then
V (Idx) := 11;
end if;
-- 커서로 벡터 요소 수정
if C /= No_Element then
V (C) := 14;
end if;
V (C) := 14 대신 긴 형식 V.Replace_Element (C, 14)를 사용할 수도 있어요.
요소 삽입 (Inserting elements)
앞 절들에서 벡터에 요소를 추가하는 예시들을 봤어요:
- 벡터 선언에서 연결 연산자(
&)를 사용하거나 Prepend와Append프로시저를 호출하는 것
특정 위치, 예를 들어 벡터의 특정 요소 앞에 요소를 삽입하고 싶을 수 있어요. 이는 Insert를 호출해 해요. 예를 들어:
with Ada.Containers; use Ada.Containers;
with Ada.Containers.Vectors;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Vector_Insert is
package Integer_Vectors is new
Ada.Containers.Vectors
(Index_Type => Natural,
Element_Type => Integer);
use Integer_Vectors;
procedure Show_Elements (V : Vector) is
begin
New_Line;
Put_Line ("Vector has "
& Count_Type'Image (V.Length)
& " elements");
if not V.Is_Empty then
Put_Line ("Vector elements are: ");
for E of V loop
Put_Line ("- " & Integer'Image (E));
end loop;
end if;
end Show_Elements;
V : Vector := 20 & 10 & 12;
C : Cursor;
begin
Show_Elements (V);
New_Line;
Put_Line ("Adding element with value 9");
Put_Line (" (before 10)...");
--
-- V.Insert로 요소를 벡터에 삽입
--
C := V.Find (10);
if C /= No_Element then
V.Insert (C, 9);
end if;
Show_Elements (V);
end Show_Vector_Insert;
이 예시에서 값 10을 가진 요소를 찾아요. 찾으면 그 앞에 값 9를 가진 요소를 삽입해요.
요소 제거 (Removing elements)
Delete 프로시저에 유효한 인덱스나 커서를 전달해 벡터에서 요소를 제거할 수 있어요. 이를 앞 절의 Find_Index와 Find 함수와 결합하면, 특정 요소를 검색해 찾으면 삭제하는 프로그램을 작성할 수 있어요:
with Ada.Containers.Vectors;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Remove_Vector_Element is
package Integer_Vectors is new
Ada.Containers.Vectors
(Index_Type => Natural,
Element_Type => Integer);
use Integer_Vectors;
V : Vector := 20 & 10 & 0 & 13 & 10 & 13;
Idx : Extended_Index;
C : Cursor;
begin
-- Find_Index로 값 10의 요소 인덱스 검색
Idx := V.Find_Index (10);
-- 인덱스 유효성 확인
if Idx /= No_Index then
-- V.Delete로 요소 제거
V.Delete (Idx);
end if;
-- Find로 값 13의 요소 커서 검색
C := V.Find (13);
-- 인덱스 유효성 확인
if C /= No_Element then
-- V.Delete로 요소 제거
V.Delete (C);
end if;
end Show_Remove_Vector_Element;
이 접근 방식을 확장해 특정 값과 일치하는 모든 요소를 삭제할 수 있어요. 잘못된 인덱스나 커서를 얻을 때까지 루프에서 요소를 계속 찾으면 돼요. 예를 들어:
with Ada.Containers; use Ada.Containers;
with Ada.Containers.Vectors;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Remove_Vector_Elements is
package Integer_Vectors is new
Ada.Containers.Vectors
(Index_Type => Natural,
Element_Type => Integer);
use Integer_Vectors;
procedure Show_Elements (V : Vector) is
begin
New_Line;
Put_Line ("Vector has "
& Count_Type'Image (V.Length)
& " elements");
if not V.Is_Empty then
Put_Line ("Vector elements are: ");
for E of V loop
Put_Line ("- " & Integer'Image (E));
end loop;
end if;
end Show_Elements;
V : Vector := 20 & 10 & 0 & 13 & 10 & 14 & 13;
begin
Show_Elements (V);
--
-- 인덱스로 요소 제거
--
declare
E : constant Integer := 10;
I : Extended_Index;
begin
New_Line;
Put_Line
("Removing all elements with value of "
& Integer'Image (E) & "...");
loop
I := V.Find_Index (E);
exit when I = No_Index;
V.Delete (I);
end loop;
end;
--
-- 커서로 요소 제거
--
declare
E : constant Integer := 13;
C : Cursor;
begin
New_Line;
Put_Line
("Removing all elements with value of "
& Integer'Image (E) & "...");
loop
C := V.Find (E);
exit when C = No_Element;
V.Delete (C);
end loop;
end;
Show_Elements (V);
end Show_Remove_Vector_Elements;
이 예시에서 값 10을 가진 모든 요소를 인덱스를 검색해 벡터에서 제거해요. 마찬가지로 값 13을 가진 모든 요소를 커서를 검색해 제거해요.
기타 연산 (Other Operations)
벡터 요소에 대한 일부 연산을 봤어요. 여기서는 벡터 전체에 대한 연산을 볼게요. 가장 두드러진 것은 여러 벡터의 연결이지만, 벡터를 요소들의 시퀀스로 보고 요소들의 관계를 고려해 연산하는 정렬(sorting)과 정렬 병합(sorted merging) 같은 연산도 볼게요.
벡터 연결은 벡터에 대한 & 연산자로 해요. 두 벡터 V1과 V2를 고려할게요. V := V1 & V2로 연결할 수 있어요. V가 결과 벡터를 담아요.
제네릭 패키지 Generic_Sorting은 Ada.Containers.Vectors의 자식 패키지예요. 정렬과 병합 연산을 포함해요. 제네릭 패키지이므로 직접 사용할 수 없고 인스턴스화해야 해요. 정수 값의 벡터(예시의 Integer_Vectors)에 이 연산들을 사용하려면 Integer_Vectors의 자식으로 직접 인스턴스화해야 해요. 다음 예시가 방법을 명확히 보여줘요.
Generic_Sorting을 인스턴스화한 후 use 문으로 모든 연산을 사용할 수 있게 해요. 그런 다음 Sort로 벡터를 정렬하고 Merge로 한 벡터를 다른 벡터로 병합할 수 있어요.
다음 예시는 연결, 정렬, 병합 연산을 사용해 세 벡터(V1, V2, V3)를 조작하는 코드를 보여줘요:
with Ada.Containers; use Ada.Containers;
with Ada.Containers.Vectors;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Vector_Ops is
package Integer_Vectors is new
Ada.Containers.Vectors
(Index_Type => Natural,
Element_Type => Integer);
package Integer_Vectors_Sorting is
new Integer_Vectors.Generic_Sorting;
use Integer_Vectors;
use Integer_Vectors_Sorting;
procedure Show_Elements (V : Vector) is
begin
New_Line;
Put_Line ("Vector has "
& Count_Type'Image (V.Length)
& " elements");
if not V.Is_Empty then
Put_Line ("Vector elements are: ");
for E of V loop
Put_Line ("- " & Integer'Image (E));
end loop;
end if;
end Show_Elements;
V, V1, V2, V3 : Vector;
begin
V1 := 10 & 12 & 18;
V2 := 11 & 13 & 19;
V3 := 15 & 19;
New_Line;
Put_Line ("---- V1 ----");
Show_Elements (V1);
New_Line;
Put_Line ("---- V2 ----");
Show_Elements (V2);
New_Line;
Put_Line ("---- V3 ----");
Show_Elements (V3);
New_Line;
Put_Line
("Concatenating V1, V2 and V3 into V:");
V := V1 & V2 & V3;
Show_Elements (V);
New_Line;
Put_Line ("Sorting V:");
Sort (V);
Show_Elements (V);
New_Line;
Put_Line ("Merging V2 into V1:");
Merge (V1, V2);
Show_Elements (V1);
end Show_Vector_Ops;
Reference Manual은 Sort 호출의 최악 경우 복잡도가 O(N²)이고 평균 복잡도가 O(N²)보다 낮아야 한다고 요구해요.
집합 (Sets)
집합은 또 다른 컨테이너 클래스예요. 벡터는 중복 요소 삽입을 허용하는 반면, 집합은 중복 요소가 존재하지 않도록 보장해요.
다음 절들에서 집합에 수행할 수 있는 연산을 볼게요. 다만 집합에 대한 많은 연산이 벡터에 대한 것과 유사하므로 더 빠르게 다룰게요. 자세한 논의는 벡터 절을 다시 참조하세요.
초기화와 순회 (Initialization and iteration)
집합을 초기화하려면 Insert 프로시저를 호출할 수 있어요. 하지만 그렇게 하면 중복 요소가 삽입되지 않도록 해야 해요: 중복을 삽입하려 하면 예외가 발생해요. 삽입될 요소를 덜 통제해서 중복이 있을 수 있다면 다른 옵션을 사용할 수도 있어요:
- 삽입 성공 여부를 나타내는 Boolean 값을 반환하는
Insert버전 - 중복 요소 삽입 시도를 조용히 무시하는
Include프로시저
집합을 순회하려면 벡터에서 봤듯이 for E of S 루프를 사용할 수 있어요. 이는 집합의 각 요소에 대한 참조를 제공해요.
예시를 볼게요:
with Ada.Containers; use Ada.Containers;
with Ada.Containers.Ordered_Sets;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Set_Init is
package Integer_Sets is new
Ada.Containers.Ordered_Sets
(Element_Type => Integer);
use Integer_Sets;
S : Set;
-- Same as: S : Integer_Sets.Set;
C : Cursor;
Ins : Boolean;
begin
S.Insert (20);
S.Insert (10);
S.Insert (0);
S.Insert (13);
-- 이제 S.Insert(0)을 호출하면 이 요소가
-- 이미 집합에 있으므로 Constraint_Error가
-- 발생함. 대신 예외를 발생시키지 않고
-- 상태를 나타내는 Boolean을 반환하는
-- Insert 버전을 호출함
S.Insert (0, C, Ins);
if not Ins then
Put_Line
("Error while inserting 0 into set");
end if;
-- S.Include를 호출할 수도 있음
-- 요소가 이미 있으면 집합은 그대로
S.Include (0);
S.Include (13);
S.Include (14);
Put_Line ("Set has "
& Count_Type'Image (S.Length)
& " elements");
--
-- for .. of 루프로 집합 순회
--
Put_Line ("Elements:");
for E of S loop
Put_Line ("- " & Integer'Image (E));
end loop;
end Show_Set_Init;
요소에 대한 연산 (Operations on elements)
이 절에서는 집합에 대한 다음 연산들을 간단히 살펴볼게요:
- 요소를 제거하는
Delete와Exclude - 요소의 존재를 확인하는
Contains와Find
요소를 삭제하려면 Delete 프로시저를 호출해요. 하지만 위의 Insert 프로시저와 마찬가지로 Delete는 삭제할 요소가 집합에 없으면 예외를 발생시켜요. 요소가 존재하지 않을 가능성을 허용하려면 Exclude를 호출할 수 있는데, 이는 존재하지 않는 요소 삭제 시도를 조용히 무시해요.
Contains는 값이 집합에 포함되어 있는지를 나타내는 Boolean 값을 반환해요. Find는 집합에서 요소를 찾지만 커서를 반환하고, 요소가 없으면 No_Element를 반환해요. 두 함수 중 하나를 사용해 집합에서 요소를 검색할 수 있어요.
이 연산들을 사용하는 예시를 볼게요:
with Ada.Containers; use Ada.Containers;
with Ada.Containers.Ordered_Sets;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Set_Element_Ops is
package Integer_Sets is new
Ada.Containers.Ordered_Sets
(Element_Type => Integer);
use Integer_Sets;
procedure Show_Elements (S : Set) is
begin
New_Line;
Put_Line ("Set has "
& Count_Type'Image (S.Length)
& " elements");
Put_Line ("Elements:");
for E of S loop
Put_Line ("- " & Integer'Image (E));
end loop;
end Show_Elements;
S : Set;
begin
S.Insert (20);
S.Insert (10);
S.Insert (0);
S.Insert (13);
S.Delete (13);
-- S.Delete (13)을 다시 호출하면 요소가
-- 더 이상 집합에 없어 삭제할 수 없으므로
-- Constraint_Error가 발생함. 대신
-- V.Exclude를 호출할 수 있음:
S.Exclude (13);
if S.Contains (20) then
Put_Line ("Found element 20 in set");
end if;
-- S.Contains 대신 S.Find를 사용할 수도 있음
if S.Find (0) /= No_Element then
Put_Line ("Found element 0 in set");
end if;
Show_Elements (S);
end Show_Set_Element_Ops;
위 예시들에서 사용한 정렬 집합(ordered sets) 외에도 표준 라이브러리는 해시 집합(hashed sets)도 제공해요. Reference Manual은 각 연산의 평균 복잡도를 다음과 같이 요구해요:
| 연산 | Ordered_Sets |
Hashed_Sets |
|---|---|---|
| Insert / Include / Replace / Delete / Exclude / Find | O((log N)²) 또는 그 이하 | O(log N) |
| 커서를 사용하는 서브프로그램 | O(1) | O(1) |
기타 연산 (Other Operations)
앞 절들은 주로 집합의 개별 요소를 다뤘어요. 하지만 Ada는 전형적인 집합 연산도 제공해요: 합집합(union), 교집합(intersection), 차집합(difference), 대칭 차집합(symmetric difference)이에요. 이전에 본 일부 벡터 연산(예: Merge)과 달리 여기서는 - 같은 내장 연산자를 사용할 수 있어요. 다음 표는 연산과 그 연관 연산자를 나열해요:
| 집합 연산 | 연산자 |
|---|---|
| 합집합 (Union) | or |
| 교집합 (Intersection) | and |
| 차집합 (Difference) | - |
| 대칭 차집합 (Symmetric difference) | xor |
다음 예시는 이 연산자들을 사용해요:
with Ada.Containers; use Ada.Containers;
with Ada.Containers.Ordered_Sets;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Set_Ops is
package Integer_Sets is new
Ada.Containers.Ordered_Sets
(Element_Type => Integer);
use Integer_Sets;
procedure Show_Elements (S : Set) is
begin
Put_Line ("Elements:");
for E of S loop
Put_Line ("- " & Integer'Image (E));
end loop;
end Show_Elements;
procedure Show_Op (S : Set;
Op_Name : String) is
begin
New_Line;
Put_Line (Op_Name
& "(set #1, set #2) has "
& Count_Type'Image (S.Length)
& " elements");
end Show_Op;
S1, S2, S3 : Set;
begin
S1.Insert (0);
S1.Insert (10);
S1.Insert (13);
S2.Insert (0);
S2.Insert (10);
S2.Insert (14);
S3.Insert (0);
S3.Insert (10);
New_Line;
Put_Line ("---- Set #1 ----");
Show_Elements (S1);
New_Line;
Put_Line ("---- Set #2 ----");
Show_Elements (S2);
New_Line;
Put_Line ("---- Set #3 ----");
Show_Elements (S3);
New_Line;
if S3.Is_Subset (S1) then
Put_Line ("S3 is a subset of S1");
else
Put_Line ("S3 is not a subset of S1");
end if;
S3 := S1 and S2;
Show_Op (S3, "Intersection");
Show_Elements (S3);
S3 := S1 or S2;
Show_Op (S3, "Union");
Show_Elements (S3);
S3 := S1 - S2;
Show_Op (S3, "Difference");
Show_Elements (S3);
S3 := S1 xor S2;
Show_Op (S3, "Symmetric difference");
Show_Elements (S3);
end Show_Set_Ops;
무한 맵 (Indefinite maps)
앞 절들은 definite 타입의 요소를 위한 컨테이너를 제시했어요. 그 절들의 대부분 예시가 컨테이너의 요소 타입으로 Integer 타입을 제시했지만, 컨테이너는 무한(indefinite) 타입과도 사용할 수 있어요. 그 예시가 String 타입이에요. 하지만 indefinite 타입은 이를 위해 특별히 설계된 다른 종류의 컨테이너를 요구해요.
또한 다른 클래스의 컨테이너인 맵(map)도 살펴볼게요. 맵은 키를 특정 값과 연관시켜요. 맵의 예시는 사람과 나이 사이의 일대일 연관이에요. 사람 이름을 키로 간주하면 값은 그 사람의 나이예요.
해시 맵 (Hashed maps)
해시 맵은 키로 해시(hash)를 사용하는 맵이에요. 해시 자체는 여러분이 제공하는 함수로 계산돼요.
다른 언어에서 (In other languages) 해시 맵은 Python의 사전(dictionary)과 Perl의 해시(hash)와 유사해요. 주요 차이점 중 하나는 이런 스크립트 언어들은 단일 맵에 포함된 값에 서로 다른 타입을 사용할 수 있게 하지만, Ada에서는 키와 값 모두의 타입이 패키지 인스턴스화에 지정되고 그 특정 맵에서 일정하게 유지된다는 것이에요. 두 요소가 서로 다른 타입이거나 두 키가 서로 다른 타입인 맵을 가질 수 없어요. 여러 타입을 사용하려면 각각 별도의 맵을 만들고 각 맵에 한 타입만 사용해야 해요.
Ada.Containers.Indefinite_Hashed_Maps에서 해시 맵을 인스턴스화할 때 다음 요소를 지정해요:
Key_Type: 키의 타입Element_Type: 요소의 타입Hash:Key_Type에 대한 해시 함수Equivalent_Keys: 두 키가 같은 것으로 간주되는지 나타내는 동등 연산자(예:=)
Key_Type에 지정된 타입에 표준 연산자가 있으면 Equivalent_Keys의 값으로 그 연산자를 지정해 사용할 수 있어요.
다음 예시에서는 키 타입으로 문자열을 사용할게요. 표준 라이브러리가 문자열용으로 제공하는 Hash 함수(Ada.Strings 패키지)와 표준 동등 연산자를 사용할게요.
해시 맵에 요소를 추가하려면 Insert를 호출해요. 요소가 이미 맵 M에 포함되어 있으면 키를 사용해 직접 접근할 수 있어요. 예를 들어 M ("My_Key") := 10으로 요소의 값을 변경할 수 있어요. 키를 찾지 못하면 예외가 발생해요. 키가 사용 가능한지 확인하려면 Contains 함수를 사용해요(집합 절에서 위에서 봤듯이).
예시를 볼게요:
with Ada.Containers.Indefinite_Hashed_Maps;
with Ada.Strings.Hash;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Hashed_Map is
package Integer_Hashed_Maps is new
Ada.Containers.Indefinite_Hashed_Maps
(Key_Type => String,
Element_Type => Integer,
Hash => Ada.Strings.Hash,
Equivalent_Keys => "=");
use Integer_Hashed_Maps;
M : Map;
-- Same as:
--
-- M : Integer_Hashed_Maps.Map;
begin
M.Include ("Alice", 24);
M.Include ("John", 40);
M.Include ("Bob", 28);
if M.Contains ("Alice") then
Put_Line ("Alice's age is "
& Integer'Image (M ("Alice")));
end if;
-- Alice의 나이 갱신
-- 키는 M에 이미 존재해야 함.
-- 그렇지 않으면 예외 발생.
M ("Alice") := 25;
New_Line; Put_Line ("Name & Age:");
for C in M.Iterate loop
Put_Line (Key (C) & ": "
& Integer'Image (M (C)));
end loop;
end Show_Hashed_Map;
정렬 맵 (Ordered maps)
정렬 맵(ordered maps)은 해시 맵과 많은 기능을 공유해요. 주요 차이점은:
- 해시 함수가 필요 없어요. 대신 순서 함수(
<연산자)를 제공해야 해요. 정렬 맵은 이로 요소를 정렬하고 이진 탐색을 사용해 빠른 접근 O(log N)을 허용해요. Key_Type에 지정된 타입에 표준<연산자가 있으면 해시 맵에서Equivalent_Keys에 대해 했던 것과 유사한 방식으로 사용할 수 있어요.
예시를 볼게요:
with Ada.Containers.Indefinite_Ordered_Maps;
with Ada.Text_IO; use Ada.Text_IO;
procedure Show_Ordered_Map is
package Integer_Ordered_Maps is new
Ada.Containers.Indefinite_Ordered_Maps
(Key_Type => String,
Element_Type => Integer);
use Integer_Ordered_Maps;
M : Map;
begin
M.Include ("Alice", 24);
M.Include ("John", 40);
M.Include ("Bob", 28);
if M.Contains ("Alice") then
Put_Line ("Alice's age is "
& Integer'Image (M ("Alice")));
end if;
-- Alice의 나이 갱신
-- 키는 M에 이미 존재해야 함
M ("Alice") := 25;
New_Line; Put_Line ("Name & Age:");
for C in M.Iterate loop
Put_Line (Key (C) & ": "
& Integer'Image (M (C)));
end loop;
end Show_Ordered_Map;
위 예시와 이전 절의 예시 사이에 큰 유사성을 볼 수 있어요. 실제로 두 종류의 맵이 많은 연산을 공유하므로, 해시 맵 대신 정렬 맵을 사용하도록 예시를 바꿀 때 광범위한 수정이 필요 없었어요. 주요 차이는 예시를 실행할 때 드러나요: 해시 맵의 출력은 보통 순서가 없지만, 정렬 맵의 출력은 이름이 시사하듯 항상 정렬돼 있어요.
복잡도 (Complexity)
이질적인 키를 값과 연관시키고 빠르게 검색해야 한다면 해시 맵은 일반적으로 Ada에서 사용할 수 있는 가장 빠른 데이터 구조예요. 대부분의 경우 정렬 맵보다 약간 빠르죠. 따라서 정렬이 필요 없다면 해시 맵을 사용하세요.
Reference Manual은 다음의 평균 복잡도를 요구해요:
| 연산 | Ordered_Maps |
Hashed_Maps |
|---|---|---|
| Insert / Include / Replace / Delete / Exclude / Find | O((log N)²) 또는 그 이하 | O(log N) |
| 커서를 사용하는 서브프로그램 | O(1) | O(1) |