STL to Collection (Map, Set)

작성일 | In |

STL to Collection (1)

cpp에서 사용하는 Map, Set을 java로 치환해봅니다.

Map

기본 문법

cpp

1
2
3
4
5
6
unordered_map<int, bool> m;
map<int,bool> m; // key기준으로 정렬

m[key] = value; // input
m[key]; // output
if(used.find(3) != used.end()) // keyCheck

java

1
2
3
4
5
6
Map<Integer, Boolean> m = new HashMap<>();
Map<Integer, Integer> m = new TreeMap<>(); // key기준으로 정렬

used.put(key, value); // input
used.get(key); // output
if(used.containsKey(key)); // keyCheck

kotlin

1
2
3
4
5
val m = mutableMapOf<Int, Int>()
m[key] = value

m[key]
if(m.containsKey(key))

순회하기

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  unordered_map<int, string> used;
  used[1] = "apple";

  for (const auto&[k, v] : used) {
    cout << k << " " << v << "\n";
  }

  for (auto it : used) {
    cout << it.first << " " << it.second << "\n";
  }
}

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) {
    Map<Integer, String> m = new HashMap<Integer, String>() {
        {
            put(1, "apple");
        }
    };

    for (Map.Entry<Integer, String> entry : m.entrySet()) {
        System.out.println(entry.getKey() + " " + entry.getValue());
    }

    for (Integer k : m.keySet()) {  
        System.out.println(k + " " + m.get(k));
    }

    m.forEach((k, v) -> System.out.println(k + " " + v));
}
  • 개인적으로 keySet() 을 쓰는것이 제일 편하다고 느낍니다.
  • 참고로 java에서 Map은 Collection으로 취급하지 않습니다.
1
2
3
4
5
6
7
8
9
Map Interface
Why doesn't Map extend Collection?
This was by design. We feel that mappings are not collections and collections are not mappings. Thus, it makes little sense for Map to extend the Collection interface (or vice versa).

If a Map is a Collection, what are the elements? The only reasonable answer is "Key-value pairs", but this provides a very limited (and not particularly useful) Map abstraction. You can't ask what value a given key maps to, nor can you delete the entry for a given key without knowing what value it maps to.

Collection could be made to extend Map, but this raises the question: what are the keys? There's no really satisfactory answer, and forcing one leads to an unnatural interface.

Maps can be viewed as Collections (of keys, values, or pairs), and this fact is reflected in the three "Collection view operations" on Maps (keySet, entrySet, and values). While it is, in principle, possible to view a List as a Map mapping indices to elements, this has the nasty property that deleting an element from the List changes the Key associated with every element before the deleted element. That's why we don't have a map view operation on Lists.
  • 공식문서 링크
  • Map의 경우 Key와 value를 쌍으로 저장하기 떄문에, Collection 인터페이스의 의미가 모호해진다는 문제가 있기 때문입니다.

kotlin

1
2
3
4
5
6
7
val m = mutableMapOf(
    1 to "apple",
    2 to "banana",
)
m.forEach { (key, value) ->
    println("key = $key, value $value")
}

없는 값에 접근하는 경우

cpp

1
2
3
4
5
6
7
8
bool containsDuplicate(vector<int>& nums) {
    unordered_map<int, bool> used;
    for(int num : nums){
        if(used[num]) return true;
        used[num] = true;
    }
    return false;
}

java

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Map<Integer, Boolean> used = new HashMap<>();
        for (int num : nums) {
            if (used.containsKey(num)) {
                return true;
            }
            used.put(num, true);
        }
        return false;
    }
}
  • cpp의 경우 used[key]로 없는 key값에 접근하는경우, 디폴트값이 자동으로 들어가게 됩니다.
  • 하지만 java의 경우 Exception 이 발생하게 됩니다.

getOrDefefault(key, defaultValue)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public static void main(String[] args) {
        List<Integer> nums = Arrays.asList(1, 2, 1, 1);
        Map<Integer, Integer> usedCount = new HashMap<>();
        for (int num : nums) {
            usedCount.put(num, usedCount.getOrDefault(num, 0) + 1);
        }
        System.out.println(usedCount.get(1));   // 3
    }
}
  • getOrDefault() 를 이용해 공수를 좀 더 줄일 수 있습니다.

kotllin

1
2
3
4
5
6
private fun mapGetOrDefault() {
    val m = mutableMapOf<Int, Int>()
    m[1] = m.getOrDefault(1, 0) + 10
    m[1] = m.getOrDefault(1, 0) + 20
    println(m[1])   // 30
}

Map<T, List<T>> 형태를 를 다루는 경우

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
private fun mapList() {
    val m = mutableMapOf(
        3 to mutableListOf(30)
    )

    m[0]?.add(0) ?: run {
        m[0] = mutableListOf(0)
    }

    m[1]?.let {
        it.add(10)
    } ?: run {
        m[1] = mutableListOf(10)
    }

    // 가독성은 아래가 좋지만, m[1]?.add 와 같이 호출해야한다.
    // if null check는 다른 스레드에서 값을 변경할 수 있기 때문이다.
    if (m[2].isNullOrEmpty()) {
        m[2] = mutableListOf(20)
    } else {
        m[2]?.add(20)
    }

    println(m)  // {3=[30], 0=[0], 1=[10], 2=[20]}
}

Set

기본 문법

cpp

1
2
3
4
5
6
7
8
9
10
set<int> s;
s.insert(1);
cout << s.size() << "\n"; // 1

if (find(s.begin(), s.end(), 1) != s.end()) {
    cout << "exist" << "\n";    // exist
}

s.erase(1);
cout << s.size() << "\n"; // 0

java

1
2
3
4
5
6
7
8
9
10
Set<Integer> s = new HashSet<>();
s.add(1);
System.out.println(s.size());   // 1

if (s.contains(1)) {
    System.out.println("exist");    // exist
}

s.remove(1);
System.out.println(s.size());   // 0

kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
fun basicSet() {
    val s = mutableSetOf<Int>()
    s.add(5)
    s.add(3)
    s.add(10)
    s.add(7)

    println(s.first())  // 5
    println(s.last())   // 7


    val sortedSet = s.toSortedSet()
    println(sortedSet.first()) // 3
    println(sortedSet.last()) // 10

    val sortedSet2 = sortedSetOf<Int>()
    sortedSet2.add(10)
    sortedSet2.add(5)
    println(sortedSet2.first()) // 5

    if (s.contains(3)) {
        println("exist")
    }
    s.remove(1)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
data class SetMember(
    val age: Int,
    val grade: String,
)

fun main() {
    val s = sortedSetOf<SetMember>(
        compareBy ({ it.age }, {it.grade})
    )
    s.add(SetMember(5, "A"))
    s.add(SetMember(10, "B"))
    s.add(SetMember(1, "C"))
    s.add(SetMember(1, "A"))

    println(s.first())  //  SetMember(age=1, grade=A)
}

Array to Set

cpp

1
2
3
4
bool containsDuplicate(vector<int>& nums) {
    set<int> uniqueNums {nums.begin(), nums.end()};
    return nums.size() != uniqueNums.size();
}

java

1
2
3
4
public boolean containsDuplicate(int[] nums) {
    Set<Integer> uniqueNums = Arrays.stream(nums).boxed().collect(Collectors.toSet());
    return uniqueNums.size() != nums.length;
}
  • 일반적으로 많은 저지 사이트에서 cpp의 경우 vector를 인자로 제공하지만, Java의 경우 int[]를 인자로 제공합니다.
  • 즉 Java의 경우 boxing 작업이 추가적으로 필요해지는 경우가 종종 발생합니다.
  • Array(primitive) to List도 비슷한 방법으로 운영됩니다.
1
2
List<Integer> list = Arrays.asList(1,2,3);
Set<Integer> set = new HashSet<>(list);
  • List인 경우 심플하게 해결이 되는데, 좀 아쉬운 부분입니다.

kotlin

1
2
3
4
5
6
7
// array to set
val array = arrayOf(3, 1, 5, 7)
val set = array.toSet()

// list to set
val list = mutableListOf(3, 1, 5, 7)
val set = list.toSet()

MultiSet

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
multiset<int> ms;

ms.insert(1);
ms.insert(1);
cout << ms.size() << "\n"; // 2;

ms.erase(1);  // 모든 1을 지움
cout << ms.size() << "\n"; // 0;

ms.insert(1);
ms.insert(1);
auto iter = ms.find(1);
ms.erase(iter); // 이터레이터에 해당하는 1개만 지움
cout << ms.size() << "\n"; // 1;

java

1
2
3
4
// 없음 직접 구현해줘야함
Map<Integer, List<Integer>> ms = new TreeMap<>();
ms.put(1, Arrays.asList(1));
...

kotlin

1
2
3
4
5
6
7
8
9
fun main() {
    val multiset = TreeMap<Int, MutableList<Int>>()

    multiset[2] = mutableListOf(20)
    multiset[1] = mutableListOf(10)
    multiset[1]?.add(11)

    println(multiset) // {1=[10, 11], 2=[20]}
}